There are k galaxies that participate in the Galactical Wars, which have happened for the past n years. Each year there has been a victor. Further, a particular galaxy G has won the Wars an even number of times. Also, G didn't participate in the first year.

You are a member of the old and wise community of Daba. Even though it is the festive season of Galaxy going on, you prefer to sit in your room and do complicated (and senseless) calculations. For no reason, one day, you wonder in how many possible ways the victories in the previous years could have taken place (that is, the number of different sequences of victors possible). Output the result of this complicated (and senseless) calculation.

Input

First line contains a single integer T, denoting the number of Test Cases.

T lines follow, containing space separated integers: n and k, as described in the problem.

Output

T lines, each containing the number of ways in which victories during n years could have taken place, modulo 1000000007 (10^9 + 7).

Constraints

1 <= T <= 150,000

1 <= n, k <= 10^9

Example

Input:
1
1 4

Output:
3

Explanation

Any Galaxy except ‘G’ could have won. There are 3 such galaxies.