human
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](https://en.wikipedia.org/wiki/Bitwise_operation#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]. 
Using python3 can you solve the prior task?
assistant
#Here is Python code to print its remainder when divided by 10^9+7.

import math
mod=10**9+7
# a=[i for i in range()]
# def ncr(n, r):
#     m=10**9+7
#     num = den = 1
#     for i in range(r):
#         num = (num * (n - i)) % m
#         den = (den * (i + 1)) % m
#     return (num * pow(den,m - 2, m)) % m
for _ in range(int(input())):
    n,k=map(int,input().split())
    print(pow(n,k,mod))