Chef was feeling bored so he decided to create a pattern to play with. His pattern always has 1 as its first element. Then he chooses a number K as the second element. After selecting K as his second number he creates next element in the pattern by multiplying all previously existing elements of the pattern.

Now he asks for your help to find the Nth element in his pattern. As his number can be very large, so output modulo 10^9 + 7.

Input

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.

The only line of each test case contains two space separated integers K and N as described in the problem statement.

Output

For each test case, output a single line containing the answer to the corresponding test case.

Constraints

1 ≤ T ≤ 100,000
1 ≤ N ≤ 1,000,000,000(10^9)
1 ≤ K ≤ 100,000

Example
Input:
2
2 2
3 4
Output:
2
9

见题面

见题面