B. AND 0, Sum Big-Codeforces Round ＃716 (Div. 2)

Problem - 1514B - Codeforces

B. AND 0, Sum Big

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Baby Badawy's first words were "AND 0 SUM BIG", so he decided to solve the following problem. Given two integers nn and kk, count the number of arrays of length nn such that:

• all its elements are integers between 00 and 2k−12k−1 (inclusive);
• the bitwise AND of all its elements is 00;
• the sum of its elements is as large as possible.

Since the answer can be very large, print its remainder when divided by 109+7109+7.

Input

The first line contains an integer tt (1≤t≤101≤t≤10) — the number of test cases you need to solve.

Each test case consists of a line containing two integers nn and kk (1≤n≤1051≤n≤105, 1≤k≤201≤k≤20).

Output

For each test case, print the number of arrays satisfying the conditions. Since the answer can be very large, print its remainder when divided by 109+7109+7.

Example

input

Copy

2
2 2
100000 20

output

Copy

4
226732710

Note

In the first example, the 44 arrays are:

• [3,0][3,0],
• [0,3][0,3],
• [1,2][1,2],
• [2,1][2,1].

==================================================================================================================================================

& The operation requires that only one of them be 0 The result must be 0, And if we want to maximize the results , The best way is, of course n individual 2^k-1, But this and the operation are not 0,. We can get n-1 All numbers 2^k-1, There's one left 0, That is to say k All places are 0 The situation of . But this k A place is 0 The case is randomly assigned to n A number does not affect the size of the answer , So the answer is n^k, It can be solved quickly

# include<iostream>
# define mod 1000000007
using namespace std;

typedef long long int ll;


ll quickpow(ll base, ll pow)
{

    ll ans=1;

    while(pow)
    {

        if(pow&1)
            ans=ans*base%mod;


        pow>>=1;

        base=base*base%mod;


    }

    return ans;

}
int main ()
{

      int t;

      cin>>t;


      while(t--)
      {
          ll n,k;

          cin>>n>>k;


          cout<<quickpow(n,k)<<endl;

      }
    return 0;

}