本文共 1682 字，大约阅读时间需要 5 分钟。

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−1 (inclusive);
• the  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≤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≤105, 1≤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+7

Example

input

Copy

22 2100000 20

output

Copy

4226732710

Note

In the first example, the 44 arrays are:

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

题目大意：给你n和k，n是数组的长度，现在给你构造一个长度为n 的序列的三个条件，一个是序列中每个元素的值在0到2^k-1，二是所有元素与的值为0，三是让序列元素的和尽可能地大，问满足上述三个条件的序列有几个

解题思路： 

题目告诉你数组中的每个数大于0小于2^k-1，又告诉你所以的结果玉等于零，那么我们很容易就想到将数转化为二进制思考问题，要是数组的和尽可能地大，那么数组中的每个数就尽可能地大，转化为二进制就是每个数的二进制位都是1.但是全为1就不满足相与为0，则我们就要将二进制位中的1位1转化为0，而且只能最多转化1位，因为转化的多了就不满足元素之和尽可能大了，我们现在有n个数，每个数有k位，那么答案就显而易见是 n^k

下面附上ac代码

#include <iostream>#include <cstdlib>#include <cstring>#include <algorithm>#include <cmath>#include <string>#include <queue>using namespace std;typedef long long ll;#define M 1000000const int mod=1e9+7;ll a[3];int main(){    std::ios::sync_with_stdio(false);    cin.tie(0),cout.tie(0);    ll t;    cin>>t;    while(t--)    {        ll n,k,ans=1;        cin>>n>>k;        for(ll i=1;i<=k;i++)        {            ans=(ans*n)%mod;        }        cout<<ans<<endl;    }    return 0;}