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 \le t \le 10$) — the number of test cases you need to solve.

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


-----Examples-----

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]$.

Difficulty: EASY
Tags: Bit manipulation

Combinatorics

Mathematics
Skill types: Bit manipulation

Starter code:

Solutions:
for _ in ' ' * int(input()):
	(n, k) = list(map(int, input().split()))
	print(pow(n, k, 10 ** 9 + 7))


mod = int(10 ** 9) + 7
for _ in range(int(input())):
	(n, k) = [int(x) for x in input().split()]
	print(pow(n, k, mod))


t = int(input())
m = 10 ** 9 + 7
for _ in range(t):
	(n, k) = map(int, input().split())
	print(n ** k % m)


for i in range(int(input())):
	(n, k) = map(int, input().split())
	print(n ** k % 1000000007)


import sys

def solve():
	(N, K) = map(int, input().split())
	r = 10 ** 9 + 7
	ans = 1
	for i in range(K):
		ans = ans * N % r
	print(ans)

def main():
	T = int(input())
	for i in range(T):
		solve()
main()


import os, sys
from io import BytesIO, IOBase
from collections import deque, Counter, defaultdict as dft
from heapq import heappop, heappush
from math import log, sqrt, factorial, cos, tan, sin, radians, log2, ceil, floor, gcd
from bisect import bisect, bisect_left, bisect_right
from decimal import *
import sys, threading
from itertools import permutations, combinations
from copy import deepcopy
input = sys.stdin.readline
ii = lambda : int(input())
si = lambda : input().rstrip()
mp = lambda : map(int, input().split())
ms = lambda : map(str, input().strip().split(' '))
ml = lambda : list(mp())
mf = lambda : map(float, input().split())
alphs = 'abcdefghijklmnopqrstuvwxyz'

def solve():
	(n, k) = mp()
	mxn = 10 ** 9 + 7
	print(pow(n, k, mxn))
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
tc = 1
tc = ii()
for i in range(tc):
	solve()


t = int(input())
tmp = []
for i in range(t):
	tmp.append(input().split(' '))
for i in tmp:
	a = int(i[0]) ** int(i[1])
	print(a % (1000000000 + 7))


import sys
input = sys.stdin.readline

def solve():
	(n, k) = map(int, input().split())
	print(pow(n, k, int(1000000000.0 + 7)))
for i in range(int(input())):
	solve()


import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	(n, k) = [int(x) for x in input().split()]
	print(n ** k % 1000000007)


n = int(input())
for i in range(n):
	(a, b) = map(int, input().split())
	print(pow(a, b, 1000000007))


for _ in range(int(input())):
	(n, k) = list(map(int, input().strip().split()))
	ans = n ** k % (10 ** 9 + 7)
	print(ans)


from sys import stdin, stdout
input = stdin.readline
mod = 10 ** 9 + 7
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	print(pow(n, k, mod))


MOD = int(1000000000.0 + 7)
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	print(n ** k % MOD)


t = int(input())
while t != 0:
	lst = [int(i) for i in input().split()]
	res = pow(lst[0], lst[1]) % 1000000007
	print(res)
	t -= 1


from sys import stdin, stdout
from math import sqrt
mod = int(1000000000.0) + 7
intn = lambda : int(stdin.readline())
strs = lambda : stdin.readline()[:-1]
lstr = lambda : list(stdin.readline()[:-1])
mint = lambda : map(int, stdin.readline().split())
lint = lambda : list(map(int, stdin.readline().split()))
out_ = lambda x: stdout.write(str(x) + ' ')
out = lambda x: stdout.write(str(x) + '\n')

def solve(n, k):
	ans = 1
	n = n % mod
	if n == 0:
		return 0
	while k > 0:
		if k & 1:
			ans = ans * n % mod
		k >>= 1
		n = n * n % mod
	return ans

def main():
	for _ in range(intn()):
		(n, k) = mint()
		ans = solve(n, k)
		out(ans)
main()


t = int(input())
while t != 0:
	(n, k) = map(int, input().split())
	print(n ** k % 1000000007)
	t -= 1


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	ans = n
	for i in range(k - 1):
		ans = ans * n % (1000000000.0 + 7)
	print(int(ans))


for i in range(int(input())):
	(n, m) = map(int, input().split())
	print(n ** m % (10 ** 9 + 7))


import math
p = 10 ** 9 + 7

def ncr(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	ans = 0
	ans = pow(ncr(n, 1, p), k, p) % p
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	mod = 10 ** 9 + 7
	print(n ** k % mod)


t = int(input())
p = 1000000007
for _ in range(t):
	(n, k) = map(int, input().split())
	print(pow(n, k, p))


def main():
	t = int(input())
	for i in range(t):
		(n, k) = map(int, input().split())
		print(n ** k % (10 ** 9 + 7))
main()


import math

def solve(n, k):
	MOD = 10 ** 9 + 7
	return n ** k % MOD
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	ans = solve(n, k)
	print(ans)


mod = 1000000007
for _ in range(int(input())):
	(n, k) = [int(i) for i in input().split()]
	print(n ** k % mod)


for _ in range(int(input())):
	(n, p) = map(int, input().split())
	ans = n ** p % 1000000007
	print(ans)


import math
import sys
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input().strip()
	return list(s[:len(s)])

def invr():
	return map(int, input().split())
mx = 10 ** 9 + 7
for _ in range(inp()):
	(a, b) = invr()
	print(a ** b % mx)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	ans = 1
	for i in range(k):
		ans = ans * n % 1000000007
	print(ans)


def readArr():
	return [int(x) for x in input().split()]
m = 10 ** 9 + 7

def solve():
	(n, k) = readArr()
	print(pow(n, k, m))
T = int(input())
for t in range(T):
	solve()


def I():
	return map(int, input().split())
(t,) = I()
r = range
for _ in r(t):
	(n, p) = I()
	print(pow(n, p) % 1000000007)


from sys import stdin, stdout
(input, print) = (stdin.readline, stdout.write)
from math import *

def main():
	for _ in range(int(input())):
		(n, k) = list(map(int, input().split()))
		mod = 10 ** 9 + 7
		print(str(n ** k % mod) + '\n')
main()


t = int(input())
for iii in range(t):
	(n, k) = map(int, input().split())
	print(pow(n, k, int(1000000000.0 + 7)))


def getarray():
	return list(map(int, input().split()))

def getints():
	return map(int, input().split())

def getint():
	return int(input())
mod = 10 ** 9 + 7

def solve():
	(n, k) = getints()
	ans = 1
	for i in range(k):
		ans = ans * n % mod
	print(ans)
for t in range(getint()):
	solve()


from math import pow
m = int(1000000000.0 + 7)

def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res
t = int(input())
for _ in range(t):
	(a, b) = list(map(int, input().split()))
	ans = power(a, b, m)
	print(ans)


t = int(input())
for z in range(t):
	(n, k) = map(int, input().split())
	print(n ** k % 1000000007)


def main():
	T = int(input())
	mod = 1000000000.0 + 7
	while T:
		(n, k) = map(int, input().split())
		result = 1
		for _ in range(k):
			result *= n
			result = int(result % mod)
		print(result)
		T -= 1
main()


t = int(input())
for i in range(t):
	(n, k) = input().split()
	(n, k) = [int(n), int(k)]
	ans = pow(n, k, 1000000007)
	print(ans)


def read():
	(n, k) = map(int, input().split())
	solve(n, k)

def solve(n, k):
	ans = pow(n, k, mod=1000000007)
	print(ans)
t = int(input())
for tc in range(t):
	read()


t = int(input())
for i in range(t):
	line = input().split(' ')
	n = int(line[0])
	k = int(line[1])
	mod = 10 ** 9 + 7
	ans = n
	for i in range(k - 1):
		ans = n * ans % mod
	print(ans)


import math
for _ in range(int(input())):
	(n, k) = map(int, input().split(' '))
	print(n ** k % (10 ** 9 + 7))


import math

def solve():
	(n, k) = map(int, input().split())
	ans = 1
	for i in range(k):
		ans = ans * n % 1000000007
	print(ans)
tst = int(input())
for i in range(tst):
	solve()


m = 1000000007
n = int(input())
for _ in range(n):
	l = input().split()
	n = int(l[0])
	k = int(l[1])
	print(pow(n, k, m))


t = int(input())
for _ in range(t):
	(k, n) = map(int, input().split())
	m = n
	n = k
	p = 1000000000 + 7
	result = 1
	while m > 0:
		if m % 2 == 0:
			m //= 2
			n = n * n % p
		else:
			result = result * n % p
			m -= 1
	print(result)


t = int(input())
while t > 0:
	(n, k) = map(int, input().split())
	print(n ** k % (10 ** 9 + 7))
	t -= 1


mod = 1000000000.0 + 7
for _ in range(int(input())):
	(n, k) = [int(x) for x in input().split()]
	res = 1
	for __ in range(k):
		res = res * n % mod
	print(int(res % mod))


t = int(input())
MOD = 10 ** 9 + 7
for _ in range(t):
	(n, k) = map(int, input().split())
	print(pow(n, k, MOD))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = pow(n, k, pow(10, 9) + 7)
	if n == 1:
		a = 1
	a = a % (pow(10, 9) + 7)
	print(a)


mod = 1000000007
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	ans = 1
	for x in range(1, k + 1):
		ans = ans * n % mod
	print(ans)


div = 10 ** 9 + 7
test = int(input())
for i in range(test):
	(n, k) = map(int, input().split())
	res = 1
	for j in range(k):
		res = res * n % div
	print(res)


def solve(n, k):
	num = n ** k
	ans = num % (10 ** 9 + 7)
	return ans
t = int(input())
for i in range(t):
	a = list(map(int, input().strip().split()))[:2]
	n = a[0]
	k = a[1]
	result = solve(n, k)
	print(result)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	mod = 10 ** 9 + 7
	ans = 1
	for i in range(k):
		ans = ans * n % mod
	print(ans)


MOD = pow(10, 9) + 7

def Solve(n, k):
	return pow(n, k) % MOD
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	print(Solve(n, k))


t = int(input())
for i in range(0, t):
	(n, k) = list(map(int, input().split()))
	result = n ** k
	remainder = result % (10 ** 9 + 7)
	print(remainder)


import io, os
import sys
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def solve_tc():
	(n, k) = map(int, input().split())
	return str(n ** k % 1000000007)
t = int(input())
while t > 0:
	t -= 1
	sys.stdout.write(solve_tc())
	sys.stdout.write('\n')


t = int(input())
MOD = 1000000000.0 + 7
while t:
	t = t - 1
	(n, k) = map(int, input().split())
	val = 1
	for i in range(0, k):
		val = int(val * n % MOD)
	print(val)


T = int(input())
for _ in range(T):
	(N, K) = map(int, input().split())
	print(N ** K % (10 ** 9 + 7))


def solve(n, k):
	ans = 1
	for i in range(k):
		ans = ans * n
		ans = ans % 1000000007
	print(ans)
T = int(input())
for _ in range(T):
	(N, K) = map(int, input().split())
	solve(N, K)


import math

def main():
	for i in range(int(input())):
		(n, k) = map(int, input().split())
		print(n ** k % (10 ** 9 + 7))
main()


import os
import sys
import math
from io import BytesIO, IOBase
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())

def dijkstra(start, distance, path, n):
	visited = [False for _ in range(n)]
	distance[start] = 0
	for i in range(n):
		v = -1
		for j in range(n):
			if not visited[v] and (v == -1 or distance[j] < distance[v]):
				v = j
		if distance[v] == math.inf:
			break
		visited[v] = True
		for edge in adj[v]:
			destination = edge[0]
			weight = edge[1]
			if distance[v] + weight < distance[destination]:
				distance[destination] = distance[v] + weight
				path[destination] = v

def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)

def lcm(a, b):
	return a * b // gcd(a, b)

def ncr(n, r):
	return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def npr(n, r):
	return math.factorial(n) // math.factorial(n - r)

def seive(n):
	primes = [True] * (n + 1)
	ans = []
	for i in range(2, n):
		if not primes[i]:
			continue
		j = 2 * i
		while j <= n:
			primes[j] = False
			j += i
	for p in range(2, n + 1):
		if primes[p]:
			ans += [p]
	return ans

def factors(n):
	factors = []
	x = 1
	while x * x <= n:
		if n % x == 0:
			if n // x == x:
				factors.append(x)
			else:
				factors.append(x)
				factors.append(n // x)
		x += 1
	return factors

def main():
	try:
		mod = 10 ** 9 + 7
		for _ in range(inp()):
			(n, k) = invr()
			ans = 1
			for i in range(k):
				ans *= n
				ans %= mod
			print(ans)
	except Exception as e:
		print(e)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


MOD = 1000000007
T = int(input())
for t in range(T):
	(n, k) = map(int, input().split())
	ans = 1
	for i in range(k):
		ans *= n
		ans %= MOD
	print(ans)


from sys import stdin
input = stdin.readline
from heapq import heapify, heappush, heappop, heappushpop
from collections import defaultdict as dd, deque as dq, Counter as C
from math import factorial as f, ceil, gcd, sqrt, log
from bisect import bisect_left as bl, bisect_right as br
from itertools import combinations as c, permutations as p
from math import factorial as f, ceil, gcd, sqrt, log
mi = lambda : map(int, input().split())
ii = lambda : int(input())
li = lambda : list(map(int, input().split()))
mati = lambda r: [li() for _ in range(r)]
lcm = lambda a, b: a * b // gcd(a, b)

def solve():
	MOD = 10 ** 9 + 7
	(n, k) = mi()
	ans = 1
	while k:
		if k % 2 == 1:
			ans *= n
		n = n ** 2 % MOD
		k //= 2
	print(ans % MOD)
for _ in range(ii()):
	solve()


def main():
	for _ in range(int(input())):
		(n, m) = tuple(map(int, input().split()))
		print(n ** m % 1000000007)
main()


for t in range(int(input())):
	(N, K) = map(int, input().split())
	print(N ** K % 1000000007)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split(' '))
	nr = n ** k
	sol = nr % (10 ** 9 + 7)
	print(sol)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	print(pow(n, m, 10 ** 9 + 7))


def some_random_function():
	x = 10
	x *= 100
	i_dont_know = x
	why_am_i_writing_this = x * x
	print(i_dont_know)
	print(why_am_i_writing_this)

def some_random_function5():
	x = 10
	x *= 100
	i_dont_know = x
	why_am_i_writing_this = x * x
	print(i_dont_know)
	print(why_am_i_writing_this)
import os, sys
from io import BytesIO, IOBase

def main():
	mod = 10 ** 9 + 7
	for _ in range(int(input())):
		(n, k) = map(int, input().split())
		print(pow(n, k, mod))
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def some_random_function1():
	x = 10
	x *= 100
	i_dont_know = x
	why_am_i_writing_this = x * x
	print(i_dont_know)
	print(why_am_i_writing_this)

def some_random_function2():
	x = 10
	x *= 100
	i_dont_know = x
	why_am_i_writing_this = x * x
	print(i_dont_know)
	print(why_am_i_writing_this)

def some_random_function3():
	x = 10
	x *= 100
	i_dont_know = x
	why_am_i_writing_this = x * x
	print(i_dont_know)
	print(why_am_i_writing_this)

def some_random_function4():
	x = 10
	x *= 100
	i_dont_know = x
	why_am_i_writing_this = x * x
	print(i_dont_know)
	print(why_am_i_writing_this)

def some_random_function6():
	x = 10
	x *= 100
	i_dont_know = x
	why_am_i_writing_this = x * x
	print(i_dont_know)
	print(why_am_i_writing_this)

def some_random_function7():
	x = 10
	x *= 100
	i_dont_know = x
	why_am_i_writing_this = x * x
	print(i_dont_know)
	print(why_am_i_writing_this)

def some_random_function8():
	x = 10
	x *= 100
	i_dont_know = x
	why_am_i_writing_this = x * x
	print(i_dont_know)
	print(why_am_i_writing_this)
main()


import math
for i in range(int(input())):
	(n, k) = map(int, input().split())
	b = 1
	for j in range(k):
		b = b * n % 1000000007
	print(b)


t = int(input())
for _ in range(0, t):
	inputs = [int(num) for num in input().split()]
	n = inputs[0]
	k = inputs[1]
	ans = n ** k
	print(ans % (10 ** 9 + 7))


x = int(input())
for i in range(x):
	(n, k) = [int(a) for a in input().split()]
	s = n ** k
	y = 10 ** 9
	y = y + 7
	t = s % y
	print(t)


for _ in range(int(input())):
	l = list(map(int, input().split()))
	print(pow(l[0], l[-1], 10 ** 9 + 7))


import os.path
from math import gcd, floor, ceil
from collections import *
import sys
mod = 1000000007
INF = float('inf')

def st():
	return list(sys.stdin.readline().strip())

def li():
	return list(map(int, sys.stdin.readline().split()))

def mp():
	return map(int, sys.stdin.readline().split())

def inp():
	return int(sys.stdin.readline())

def pr(n):
	return sys.stdout.write(str(n) + '\n')

def prl(n):
	return sys.stdout.write(str(n) + ' ')
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')

def solve():
	(n, k) = mp()
	pr(pow(n, k, mod))
for _ in range(inp()):
	solve()


for s in [*open(0)][1:]:
	print(pow(*map(int, s.split()), 10 ** 9 + 7))


m = 10 ** 9 + 7
q = int(input())
for i in range(q):
	w = input().split()
	n = int(w[0])
	k = int(w[1])
	ans = 1
	for j in range(k):
		ans = ans * n % m
	print(ans)


import sys
import math

def input():
	return sys.stdin.readline().strip('\n')

def I():
	return input()

def II():
	return int(input())

def MI():
	return map(int, input().split())

def LI():
	return list(map(int, input().split()))
mod = 10 ** 9 + 7
for _ in range(II()):
	(n, k) = MI()
	ans = n ** k % mod
	print(ans)


import sys, math, bisect
inf = float('inf')
mod = 10 ** 9 + 7

def lcm(a, b):
	return int(a / math.gcd(a, b) * b)

def gcd(a, b):
	return int(math.gcd(a, b))

def binarySearch(a, x):
	i = bisect.bisect_left(a, x)
	if i != len(a) and a[i] == x:
		return i
	else:
		return -1

def lowerBound(a, x):
	i = bisect.bisect_left(a, x)
	if i:
		return i - 1
	else:
		return -1

def upperBound(a, x):
	i = bisect.bisect_right(a, x)
	if i != len(a) + 1 and a[i - 1] == x:
		return i - 1
	else:
		return -1

def freq(a, x):
	z = upperBound(a, x) - lowerBound(a, x)
	if z <= 0:
		return 0
	return z
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	ans = 1
	for i in range(k):
		ans = ans * n % mod
	print(ans)


n = int(input())
for _ in range(n):
	(a, b) = map(int, input().split())
	print(a ** b % (10 ** 9 + 7))


from math import factorial, ceil, pow, sqrt, floor
from sys import stdin, stdout
mod = 1000000007
for _ in range(int(stdin.readline())):
	(n, k) = map(int, stdin.readline().split())
	shan = 1
	for i in range(k):
		shan = shan * n % mod
	print(shan)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	m = 1000000007
	x = n ** k % m
	print(x)


for _ in range(0, int(input())):
	(n, k) = map(int, input().split())
	print(pow(n, k) % (10 ** 9 + 7))


t = int(input())
while t > 0:
	t -= 1
	(n, k) = map(int, input().split())
	ans = n
	for i in range(1, k):
		ans = ans * n % 1000000007
	print(ans)


from math import gcd

def mlt():
	return map(int, input().split())
mod = int(1000000000.0 + 7)

def bnp(bs, pw):
	res = 1
	while pw:
		if pw & 1:
			res = res * bs % mod
		pw >>= 1
		bs = bs * bs % mod
	return res

def solv():
	(x, y) = mlt()
	print(bnp(x, y))
for _ in range(int(input())):
	solv()


for _ in ' ' * int(input()):
	print(pow(*map(int, input().split()), 10 ** 9 + 7))


for pratyush in range(int(input())):
	(n, k) = list(map(int, input().split()))
	print(n ** k % (10 ** 9 + 7))


from sys import stdin, stdout, setrecursionlimit
from collections import defaultdict as dd
from collections import deque
import math
input = stdin.readline
flush = stdout.flush
prime = int(1000000000.0 + 7)
tc = 1
tc = int(input())
for _ in range(tc):
	(n, k) = map(int, input().split())
	print(pow(n, k, prime))


from sys import stdin
input = stdin.readline
from collections import Counter
from itertools import accumulate
import operator
import math

def solve():
	(n, k) = [int(char) for char in input().split()]
	return n ** k % (10 ** 9 + 7)
for _ in range(int(input())):
	print(solve())


mod = 10 ** 9 + 7

def p(base, pow):
	if pow == 1:
		return base
	elif pow % 2:
		return base * p(base, pow // 2) ** 2 % mod
	else:
		return p(base, pow // 2) ** 2 % mod
n = int(input())
for i in range(n):
	(a, b) = map(int, input().split())
	print(p(a, b) % mod)


mod = 10 ** 9 + 7

def func():
	print(pow(n, k, mod))
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	func()


t = int(input())
while t:
	t -= 1
	(n, k) = input().split()
	n = int(n)
	k = int(k)
	ans = n ** k
	ans = ans % 1000000007
	print(ans)


m = 1000000007
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	n %= m
	ans = 1
	while k:
		if k % 2 == 1:
			ans = ans * n % m
		n = n ** 2 % m
		k //= 2
	print(ans)


T = int(input())
for x in range(T):
	a = [int(y) for y in input().split()]
	n = a[0]
	k = a[1]
	b = n ** k
	print(b % 1000000007)


mod = 1000000007
for ik in range(int(input())):
	(n, k) = map(int, input().split())
	print(pow(n, k, mod))


MOD = 10 ** 9 + 7
t = int(input().strip())
for _ in range(t):
	(n, k) = input().strip().split()
	(n, k) = (int(n), int(k))
	r = 1
	for i in range(k):
		r = r * n % MOD
	print(r)


import math
T = int(input())
while T > 0:
	(N, K) = [int(x) for x in input().split()]
	mod = pow(10, 9) + 7
	print(pow(N, K) % mod)
	T -= 1


tst = int(input())
for t in range(tst):
	(n, k) = [int(i) for i in input().split()]
	result = n ** k % (10 ** 9 + 7)
	print(result)


list_ans = []
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	list_ans.append(n ** k % int(1000000000.0 + 7))
print(*list_ans, sep='\n')


for t in range(int(input())):
	(n, k) = list(map(int, input().split()))
	print(pow(n, k) % (pow(10, 9) + 7))


def proB(n, k):
	mod = 1000000000.0 + 7
	ans = 1
	while k:
		ans = int(ans * n % mod)
		k -= 1
	return ans
t = int(input())
for i in range(t):
	(n, k) = list(map(int, input().split()))
	print(proB(n, k))


T = int(input())
for tt in range(T):
	(n, k) = map(int, input().split())
	res = pow(n, k, 10 ** 9 + 7)
	print(res)


import sys
input = sys.stdin.readline

def main():
	t = int(input())
	for _ in range(t):
		(n, k) = map(int, input().split())
		mod = 10 ** 9 + 7
		ans = pow(n, k, mod)
		print(ans)
main()


mod = int(1000000000.0) + 7

def pow(a, b):
	prod = 1
	for i in range(b):
		prod = prod * a % mod
	return prod
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	print(pow(n, k))


for _ in range(int(input())):
	print(eval('**'.join(list(map(str, input().split(' '))))) % 1000000007)


import sys

def solve(n, k):
	res = 1
	for i in range(k):
		res = res * n % 1000000007
	return str(res)

def main():
	input = sys.stdin.readline
	print = sys.stdout.write
	res = ''
	t = int(input())
	for _ in range(t):
		(n, k) = map(int, input().split())
		sub_res = solve(n, k)
		res += sub_res + '\n'
	print(res)
main()


t = int(input())
while t:
	(n, k) = list(map(int, input().split()))
	MOD = pow(10, 9) + 7
	print(pow(n, k) % MOD)
	t -= 1


MOD = 10 ** 9 + 7

def sol(n, k):
	return pow(n, k, MOD)

def main():
	n = int(input())
	for _ in range(n):
		(n, k) = [int(i) for i in input().split()]
		print(sol(n, k))
main()


t = int(input())
modulo = 10 ** 9 + 7
for _ in range(t):
	(n, k) = [int(i) for i in input().split(' ')]
	result = 1
	for i in range(k):
		result = result * n % modulo
	print(result)


T = int(input())
for TT in range(T):
	aaa = input().split(' ')
	n = int(aaa[0])
	k = int(aaa[1])
	print(pow(n, k, int(1000000000.0 + 7)))


import math

def main_function():
	test_cases = range(int(input()))
	for test_case in test_cases:
		(n, k) = [int(i) for i in input().split(' ')]
		const = 10 ** 9 + 7
		print(n ** k % const)
main_function()


def main():
	t = int(input())
	while t > 0:
		(n, k) = map(int, input().split())
		ways = n ** k
		ans = ways % 1000000007
		print(ans)
		t -= 1
main()


t = int(input())
while t > 0:
	(n, k) = [int(i) for i in input().split(' ')]
	i = 1
	max = 1000000000.0 + 7
	result = 1
	while i <= k:
		result = result * n % max
		i += 1
	print(int(result))
	t -= 1


for x in range(int(input())):
	(n, k) = map(int, input().split())
	print(pow(n, k, 1000000007))


ll = lambda : map(int, input().split())
t = lambda : int(input())
ss = lambda : input()
lx = lambda x: map(int, input().split(x))
for _ in range(t()):
	(n, k) = ll()
	print(n ** k % (10 ** 9 + 7))


for _ in range(int(input())):
	l = list(map(int, input().split(' ')))
	c = 1
	for i in range(l[1]):
		c = c * l[0]
		c = c % (1000000000.0 + 7)
	print(int(c))


import sys
import math
import bisect
from sys import stdin, stdout
from math import gcd, floor, sqrt, log2, ceil
from collections import defaultdict as dd
from bisect import bisect_left as bl, bisect_right as br
from bisect import insort
from collections import Counter
from collections import deque
from heapq import heappush, heappop, heapify
from itertools import permutations, combinations
from itertools import accumulate as ac
mod = int(1000000000.0) + 7
ip = lambda : int(stdin.readline())
inp = lambda : map(int, stdin.readline().split())
ips = lambda : stdin.readline().rstrip()
out = lambda x: stdout.write(str(x) + '\n')
t = ip()
for _ in range(t):
	(n, k) = inp()
	ans = pow(n, k, mod)
	ans %= mod
	print(ans)


t = int(input())
for i in range(t):
	(n, k) = str(input()).split()
	print(int(n) ** int(k) % (10 ** 9 + 7))


def decimalToBinary(n):
	return bin(n).replace('0b', '')
trails = int(input())
answer_list = []
for d in range(trails):
	numbers = input().split()
	n = int(numbers[0])
	k = int(numbers[1])
	s = len(str(decimalToBinary(2 ** k - 1)))
	answer = n ** s
	answer_list.append(answer)
for z in answer_list:
	print(z % (10 ** 9 + 7))


import math
from collections import Counter, defaultdict
import sys
input = sys.stdin.readline
readInt = lambda : int(input().strip())
readfloat = lambda : float(input().strip())
readStr = lambda : input().strip()
intList = lambda : list(map(int, input().strip().split()))
intMap = lambda : map(int, input().strip().split())
floatList = lambda : list(map(float, input().strip().split()))
floatMap = lambda : map(float, input().strip().split())
strList = lambda : list(input().strip().split())
mod = 10 ** 9 + 7

def solve(n, k):
	res = n ** k
	return res % mod
for _ in range(readInt()):
	(n, k) = intMap()
	print(solve(n, k))


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	mod = 1000000007
	ans = pow(n, k, mod)
	print(ans)


P = 1000000007

def solve(n, k):
	if n == 2:
		return 2 * 2 ** (k - 1)
	else:
		prod = 1
		for _ in range(k):
			prod = prod * n % P
		return prod
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split(' '))
	print(solve(n, k))


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	ans = n ** k % 1000000007
	print(ans)


import math
n_tests = int(input())
for test in range(n_tests):
	(n, k) = input().split()
	n = int(n)
	k = int(k)
	reseni = 1
	for kek in range(0, k):
		reseni *= n
	reseni = reseni % (10 ** 9 + 7)
	print(reseni)


import sys
import math
mod = 10 ** 9 + 7
LI = lambda : [int(k) for k in input().split()]
input = lambda : sys.stdin.readline().rstrip()
IN = lambda : int(input())
S = lambda : input()
for t in range(IN()):
	(n, k) = LI()
	ans = 1
	for i in range(k):
		ans *= n
		ans %= mod
	print(ans)


m = int(1000000000.0 + 7)
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = 1
	for i in range(k):
		s = s * n % m
	print(s)


T = int(input())
for ii in range(T):
	a = list(map(int, input().split()))
	n = a[0]
	m = a[1]
	ans = 1
	for i in range(m):
		ans = ans * n % 1000000007
	print(ans)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	zxc = n + 1 - 1
	mod = 10 ** 9 + 7
	for i in range(k - 1):
		n = n * zxc % mod
	print(n)


import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
input = lambda : sys.stdin.readline().rstrip()
import bisect, string, math, time, functools, random, fractions
from bisect import *
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
from itertools import permutations, combinations, groupby
rep = range
R = range

def I():
	return int(input())

def LI():
	return [int(i) for i in input().split()]

def LI_():
	return [int(i) - 1 for i in input().split()]

def AI():
	return map(int, open(0).read().split())

def S_():
	return input()

def IS():
	return input().split()

def LS():
	return [i for i in input().split()]

def NI(n):
	return [int(input()) for i in range(n)]

def NI_(n):
	return [int(input()) - 1 for i in range(n)]

def NLI(n):
	return [[int(i) for i in input().split()] for i in range(n)]

def NLI_(n):
	return [[int(i) - 1 for i in input().split()] for i in range(n)]

def StoLI():
	return [ord(i) - 97 for i in input()]

def ItoS(n):
	return chr(n + 97)

def LtoS(ls):
	return ''.join([chr(i + 97) for i in ls])

def RLI(n=8, a=1, b=10):
	return [random.randint(a, b) for i in range(n)]

def RI(a=1, b=10):
	return random.randint(a, b)

def INP():
	N = 10
	n = random.randint(1, N)
	a = RLI(n, 0, n - 1)
	return (n, a)

def Rtest(T):
	(case, err) = (0, 0)
	for i in range(T):
		inp = INP()
		a1 = naive(*inp)
		a2 = solve(*inp)
		if a1 != a2:
			print(inp)
			print('naive', a1)
			print('solve', a2)
			err += 1
		case += 1
	print('Tested', case, 'case with', err, 'errors')

def GI(V, E, ls=None, Directed=False, index=1):
	org_inp = []
	g = [[] for i in range(V)]
	FromStdin = True if ls == None else False
	for i in range(E):
		if FromStdin:
			inp = LI()
			org_inp.append(inp)
		else:
			inp = ls[i]
		if len(inp) == 2:
			(a, b) = inp
			c = 1
		else:
			(a, b, c) = inp
		if index == 1:
			a -= 1
			b -= 1
		aa = (a, c)
		bb = (b, c)
		g[a].append(bb)
		if not Directed:
			g[b].append(aa)
	return (g, org_inp)

def GGI(h, w, search=None, replacement_of_found='.', mp_def={'#': 1, '.': 0}, boundary=1):
	mp = [boundary] * (w + 2)
	found = {}
	for i in R(h):
		s = input()
		for char in search:
			if char in s:
				found[char] = (i + 1) * (w + 2) + s.index(char) + 1
				mp_def[char] = mp_def[replacement_of_found]
		mp += [boundary] + [mp_def[j] for j in s] + [boundary]
	mp += [boundary] * (w + 2)
	return (h + 2, w + 2, mp, found)

def TI(n):
	return GI(n, n - 1)

def accum(ls):
	rt = [0]
	for i in ls:
		rt += [rt[-1] + i]
	return rt

def bit_combination(n, base=2):
	rt = []
	for tb in R(base ** n):
		s = [tb // base ** bt % base for bt in R(n)]
		rt += [s]
	return rt

def gcd(x, y):
	if y == 0:
		return x
	if x % y == 0:
		return y
	while x % y != 0:
		(x, y) = (y, x % y)
	return y

def YN(x):
	print(['NO', 'YES'][x])

def Yn(x):
	print(['No', 'Yes'][x])

def show(*inp, end='\n'):
	if show_flg:
		print(*inp, end=end)
mo = 10 ** 9 + 7
inf = float('inf')
FourNb = [(-1, 0), (1, 0), (0, 1), (0, -1)]
EightNb = [(-1, 0), (1, 0), (0, 1), (0, -1), (1, 1), (-1, -1), (1, -1), (-1, 1)]
compas = dict(zip('WENS', FourNb))
cursol = dict(zip('LRUD', FourNb))
alp = [chr(ord('a') + i) for i in range(26)]

def gcj(c, x):
	print('Case #{0}:'.format(c + 1), x)
show_flg = False
show_flg = True
ans = 0
for _ in range(I()):
	(n, k) = LI()
	print(pow(n, k, mo))


t = int(input())
CONST = 10 ** 9 + 7
for i in range(t):
	(n, k) = [int(i) for i in input().split()]
	ans = n ** k
	print(ans % CONST)


import sys

def readnum():
	input = sys.stdin.readline
	a = list(map(int, input().split()))
	return a

def printf(val):
	sys.stdout.write(str(val) + '\n')

def power(a, b, mod):
	if b == 1:
		return a
	if b == 0:
		return 1
	ans = power(a, b // 2, mod)
	ans *= ans
	if b % 2:
		ans *= a
	ans = ans % mod
	return ans
t = readnum()[0]
for _ in range(t):
	(n, k) = readnum()
	print(power(n, k, 10 ** 9 + 7))