AKVQLD02 - Raise the Power 300 pts

no tags 

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


Added by:Ankit Kumar Vats
Date:2013-07-23
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Self