There are $N$ buildings in a row. Each of these buildings needs to be painted by one of the $K$ colors. Buildings look beautiful only if no adjacent buildings are painted with the same color. Find the number of ways to paint these buildings such that they are beautiful. Since the number could be very large output it modulo $10^9 + 7$.

Input Format

The first line of the input contains an integer $T$, the total number of test cases.
Then $T$ lines follow, each containing two space-separated integers $N$ and $K$, the total number of buildings and the number of colors available.

Output Format

For each test case output the number of ways to paint the buildings such that they are beautiful modulo $10^9 + 7$ .

Constraints

$1 \le T \le 10$
$1 \le N \le 10^5$
$2 \le K \le 10^5$