Do you know how to calculate "A" raised to the power "B"? Of course you know. What if "B" becomes very large? The answer will be huge, so just calculate the answer modulo 1,000,000,007. Can you do it? Let's see.

Input

First line will contain "T", the number of test cases. Each of the next "T" lines will contain two integers "A" and "B".

Output

For each test case, print "A" raised to the power "B" modulo 1,000,000,007 in a separate line. (Modulo operation gives the remainder, for example, 5 mod 3 = 2, 10 mod 2 = 0, etc.)

Constraints

1 <= T <= 10^4

0 <= A <= 10^18

0 <= B <= 10^18

A and B won't be 0 simultaneously.

Example

Input:
2
2 3
5 13

Output:
8
220703118