Problem Statement

Chef Diablo has set up a stall for selling his famous Modaks in the Trinity fest. He wants to earn as much profit as he can. So he has bought a chemical that increases the taste level of the Modaks. The tastier the Modaks the higher he can price them. This chemical is very costly hence he applies only certain amount of chemical on the Modaks(also he does not make it so costly that no one would buy it...:P). If Chef Diablo applies the chemical on the Modak having an initial of taste level TL, its taste level becomes TL^N where N is the number of drops of the chemical. Given TL and N, tell Chef Diablo the final Taste level of the Modak.

Input:

First line contains t, the number of test cases. Then t lines follow, each line containing 2 space separated integers denoting TL and N respectively.

Output:

It will consist of t lines having the final taste level of the Modak modulo 10^9+7.

Constraints:

1<=t<=100
1<=TL<=10^101
0<=N<=10^101

Input:

3
1 1
2 2
123123123123 2

Output:

1
4
293883007

见题面

见题面