AND 0, Sum Big

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

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

Since the answer can be very large, print its remainder when divided by 10^9+7.

Input

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

Each test case consists of a line containing two integers n and k (1 ≤ n ≤ 10^{5}, 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 10^9+7.

Example

Input

2 2 2 100000 20

Output

4 226732710

Note

In the first example, the 4 arrays are:

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

inputFormat

Input

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

Each test case consists of a line containing two integers n and k (1 ≤ n ≤ 10^{5}, 1 ≤ k ≤ 20).

outputFormat

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 10^9+7.

Example

Input

2 2 2 100000 20

Output

4 226732710

Note

In the first example, the 4 arrays are:

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

样例

2
2 2
100000 20

4
226732710

</p>