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]. 
 ... Give me a Python code to print its remainder when divided by 10^9+7?
assistant
#Here is Python code to print its remainder when divided by 10^9+7.

#python2
#from __future__ import print_function
mod=int(1e9+7)
#import resource
#resource.setrlimit(resource.RLIMIT_STACK, [0x100000000, resource.RLIM_INFINITY])
#import threading
#threading.stack_size(2**25)
#import sys
#sys.setrecursionlimit(10**5)
#fact=[1]
#for i in range(1,100001):
#    fact.append((fact[-1]*i)%mod)
#ifact=[0]*100001
#ifact[100000]=pow(fact[100000],mod-2,mod)
#for i in range(100000,0,-1):
#    ifact[i-1]=(i*ifact[i])%mod
from random import randint as rn
import bisect
from bisect import bisect_left as bl              #c++ lowerbound bl(array,element)
from bisect import bisect_right as br             #c++ upperbound
import itertools
import collections
import math
import heapq
from types import GeneratorType
def bootstrap(f, stack=[]):
    def wrappedfunc(*args, **kwargs):
        if stack:
            return f(*args, **kwargs)
        else:
            to = f(*args, **kwargs)
            while True:
                if type(to) is GeneratorType:
                    stack.append(to)
                    to = next(to)
                else:
                    stack.pop()
                    if not stack:
                        break
                    to = stack[-1].send(to)
            return to
    return wrappedfunc
def modinv(n,p):
    return pow(n,p-2,p)
def ncr(n,r,p):                        #for using this uncomment the lines calculating fact and ifact
    t=((fact[n])*((ifact[r]*ifact[n-r])%p))%p
    return t
def GCD(x,y):
    while(y):
        x, y = y, x % y
    return x
def ain():                           #takes array as input
    return list(map(int,sin().split()))
def sin():
    return input().strip()
intmax=10**18
intmin=-intmax
from itertools import permutations
"""*******************************************************"""
def main():
    for _ in range(int(sin())):
        n,k=ain()
        print pow(n,k,mod) 
######## Python 2 and 3 footer by Pajenegod and c1729
py2 = round(0.5)
if py2:
    from future_builtins import ascii, filter, hex, map, oct, zip
    range =...