The city of Hackerland has formed a new football club and wants to participate in the upcoming Football League of their country. The coach is worried that they will not be able to qualify because they don't have a famous footballer in their team. The assistant coach suggests that the team should buy Cristiano Ronaldo as he can single-handedly get their team qualified.  

On day 1, today, the club has to pay 'A' HackerCoins in order to buy Ronaldo. After each passing day, the price of buying Ronaldo becomes A times the price on the previous day. Any normal person would buy him on the 1^{st} day itself as the price will be the lowest but since the coach always failed in high school Mathematics, he wants 'B' days to think before making him an offer.  

As the coach doesn't know how to calculate the price of Ronaldo on the B^{th} day, he has asked for your help.  

Your task is to tell the price of Ronaldo on the B^{th} day. Since, the price can be a very large number, please tell him the price modulo 10^{9} + 7.

Input Format 

The first line contains an integer T, the number of testcases. It's followed by T lines. 

Each testcase will contain two integers A & B separated by a space.  

Output Format 

Output T lines, each corresponding to the answer of the testcase.  

Constraints 

1 <= T <= 10 

1 <= A,B <= 10100000 

A % (10^{9} + 7) != 0

Note 

Both integers will have a maximum of 100000 digits.  

Sample Input #00:  

5
3 2
4 5
7 4
34534985349875439875439875349875 93475349759384754395743975349573495
34543987529435983745230948023948 3498573497543987543985743989120393097595572309482304

Sample Output #00:  

9
1024
2401
735851262
985546465

Explanation #00:  

As value of 3^{2} = 9, So output for first case will be 9. 

Similarly 4^{5} modulo (10^{9} + 7) = 1024 

Similarly 7^{4} modulo (10^{9} + 7) = 2401 

Similarly we can do for others.

Difficulty: MEDIUM
Tags: Number theory

Starter code:

Solutions:
import sys
T = int(sys.stdin.readline())
for _ in range(T):
	(A, B) = [int(x) for x in sys.stdin.readline().split()]
	print(pow(A, B, 1000000007))


import sys
from collections import deque
import heapq
from itertools import *
INF = 1000000000

def gl():
	return input()

def gs():
	return (x for x in input().split())

def gi():
	return int(input())

def gis():
	return (int(x) for x in input().split())

def gf():
	return float(input())

def gfs():
	return (float(x) for x in input().split())

def even(x):
	return x % 2 == 0

def odd(x):
	return x % 2 == 1

def dbg(s):
	print(s, file=sys.stderr)
mod = 1000000007
cases = gi()
for case in range(cases):
	(a, b) = gis()
	print(pow(a, b, int(mod)))


from sys import *
N = int(input())
for i in range(N):
	(a, b) = input().split(' ')
	print(pow(int(a), int(b), 1000000007))


[print((lambda x, y: pow(x % (10 ** 9 + 7), 10 ** 9 + 6 + y % (10 ** 9 + 6), 10 ** 9 + 7))(*map(int, input().strip().split()))) for i in range(int(input()))]


import sys

def powMod(a, p, m):
	if p < 2:
		if p == 1:
			return a % m
		else:
			return 1
	else:
		v = powMod(a, p // 2, m)
		v *= v
		v = v % m
		if p % 2 == 0:
			return v
		else:
			return v * a % m

def PowMod(a, b, m):
	if a % m == 0:
		return 0
	else:
		return powMod(a % m, b % (m - 1), m)
n = int(sys.stdin.readline())
for i in range(0, n):
	m = sys.stdin.readline().split(' ')
	print(PowMod(int(m[0]), int(m[1]), 1000000007))


mod = 10 ** 9 + 7

def calc(a, b):
	print(pow(a, b, mod))
count = int(input())
ar = []
for i in range(count):
	ar.append(tuple((int(x) for x in input().split(' '))))
for a in ar:
	calc(a[0], a[1])


import sys
T = int(sys.stdin.readline())
cases = [list(map(int, line.split())) for line in sys.stdin.readlines()]
M = 10 ** 9 + 7
for case in cases:
	(A, B) = case
	print(pow(A, B, M))


mod = 1000000007
T = int(input())
while T:
	T -= 1
	(A, B) = map(int, input().split(' '))
	A %= mod
	B %= mod - 1
	res = 1
	while B > 0:
		if B % 2 == 1:
			res = res * A % mod
		A = A * A % mod
		B //= 2
	print(res)


mod = 10 ** 9 + 7

def pow(x, n):
	a = x
	ans = 1
	while n > 0:
		if n % 2 != 0:
			ans *= a
			ans %= mod
		a *= a
		a %= mod
		n >>= 1
	return ans
T = int(input())
for tt in range(T):
	(a, b) = map(int, input().split())
	b %= mod - 1
	a %= mod
	print(pow(a, b))


import math
for i in range(int(input())):
	(a, b) = input().split()
	a = int(a)
	b = int(b)
	ans = pow(a, b, 1000000007)
	print(ans)


t = int(input())
for i in range(t):
	tmp = input()
	(a, b) = tmp.split(' ')
	a = int(a)
	b = int(b)
	print(pow(a, b, 1000000007))


def expmod(g, u, p):
	s = 1
	while u != 0:
		if u & 1:
			s = s * g % p
		u >>= 1
		g = g * g % p
	return s
a = int(input())
while a > 0:
	(x, y) = input().split()
	(x, y) = [int(x), int(y)]
	x = x % 1000000007
	y = y % 1000000006
	print(expmod(x, y, 1000000007))
	a = a - 1


def main():
	T = int(sys.stdin.readline())
	MOD = 1000000007
	while T > 0:
		(A, B) = [int(x) for x in sys.stdin.readline().split()]
		print(pow(A, B, MOD))
		T = T - 1
import sys
main()


__author__ = 'bozo'
import sys
import math
import fractions

def cut_number(A, m):
	while len(A) > 10:
		tmp = int(A[:-(len(A) - 10)]) % m
		A = A[-(len(A) - 10):]
		A = str(tmp) + A
	return int(A) % m

def main():
	T = int(sys.stdin.readline())
	for i in range(0, T):
		AB = sys.stdin.readline()
		s = AB.split(' ')
		A = int(s[0])
		B = int(s[1])
		print(pow(A, B, 1000000007))
main()


T = int(input())
while T > 0:
	T -= 1
	[A, B] = input().split()
	print(pow(int(A), int(B), 10 ** 9 + 7))


MODULO = 1000000007

def solve():
	[a, b] = input().split()
	a = int(a) % MODULO
	b = int(b) % (MODULO - 1)
	price = 1
	while b != 0:
		if b & 1 == 1:
			price = price * a % MODULO
		a = a * a % MODULO
		b >>= 1
	print(price)

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


n = int(input())
result = 0.0
t = 1000000007
for i in range(n):
	m = input().split(' ')
	a = int(m[0])
	b = int(m[1])
	print(pow(a, b, t) % t)


from decimal import Decimal

def main():
	n = int(input())
	mod = 10 ** 9 + 7
	for i in range(0, n):
		arrData = input().split()
		num1 = int(arrData[0])
		num2 = int(arrData[1])
		result = pow(num1, num2, mod)
		print(result)
main()


import sys
t = int(sys.stdin.readline())
for _ in range(t):
	(a, b) = list((int(x) for x in sys.stdin.readline().split()))
	print(pow(a, b, 1000000007))


from sys import stdin
T = int(stdin.readline())
M = 10 ** 9 + 7
for _ in range(T):
	(A, B) = (int(s) for s in stdin.readline().split())
	ans = acc = A % M
	B = B % (M - 1) - 1
	i = 1
	while i <= B:
		if i & B:
			B -= i
			ans = ans * acc % M
		(acc, i) = (acc * acc % M, i + i)
	print(ans)


def modexp(a, b, div):
	x = 1
	y = a
	while b > 0:
		if b % 2 == 1:
			x = x * y % div
		y = y * y % div
		b = b // 2
	return x % div
T = int(input())
div = 10 ** 9 + 7
for i in range(T):
	(a, b) = [int(j) for j in input().split()]
	print(modexp(a % div, b % (div - 1), div))


lstOut = []

def degree(a, b):
	dicRem = {0: 1}
	for i in range(1, 11):
		dicRem[i] = dicRem[i - 1] * a % 1000000007
	if b < 10:
		return dicRem[b]
	else:
		return dicRem[b % 10] * degree(dicRem[10], b // 10) % 1000000007
for case in range(int(input())):
	c = [int(i) for i in input().split()]
	lstOut.append(degree(c[0] % 1000000007, c[1] % 1000000006))
for i in lstOut:
	print(i)


T = int(input())
for i in range(T):
	(A, B) = input().split()
	print(pow(int(A), int(B), 1000000007))


t = int(input())
while t > 0:
	t = t - 1
	(a, b) = input().split()
	(a, b) = [int(a), int(b)]
	s = pow(a, b, 1000000007)
	print(s)


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


t = int(input())
for i in range(t):
	l = input().split(' ')
	a = int(l[0])
	b = int(l[1])
	print(pow(a, b, 1000000007))


import random
n = int(input())
for i in range(0, n):
	st = input()
	l = st.split(' ')
	x = int(l[0])
	y = int(l[1])
	print(pow(x, y, 1000000007))


N = int(input())
for i in range(N):
	line = input()
	tokens = line.split()
	a = int(tokens[0])
	b = int(tokens[1])
	print(pow(a, b, 1000000007))


t = int(input())
mod = 1000000007
i = 0
while i < t:
	i += 1
	line = input().strip().split()
	(a, b) = (int(line[0]), int(line[1]))
	a = a % mod
	b = b % (mod - 1)
	print(pow(a, b, mod))


num_tests = int(input())
mod = 10 ** 9 + 7
for _ in range(num_tests):
	(base, exponent) = map(int, input().split())
	result = 1
	bits = '{0:b}'.format(exponent)[::-1]
	for bit in bits:
		if bit == '1':
			result = result * base % mod
		base = base * base % mod
	print(result)
pass


T = int(input())
modval = 10 ** 9 + 7
for _ in range(T):
	(num, power) = [int(n) for n in input().split(' ')]
	print(pow(num, power, modval))


import math
import sys
T = int(input())
while T > 0:
	S = input()
	l = S.split()
	b = int(l[0])
	e = int(l[1])
	print(pow(b, e, 1000000007))
	T = T - 1


testCase = int(input())
for i in range(testCase):
	baseAndExponent = input().split(' ')
	base = int(baseAndExponent[0])
	exponent = int(baseAndExponent[1])
	price = pow(base, exponent, 1000000007)
	print(price)


def main():
	t = int(input())
	i = 0
	mod = 10 ** 9 + 7
	while i < t:
		line = input()
		a = int(line.split()[0])
		b = int(line.split()[1])
		j = 1
		l = list()
		i += 1
		m = pow(a, b, mod)
		print(m)
main()


N = int(input())
mod = 10 ** 9 + 7
for i in range(0, N):
	(A, B) = map(int, input().split())
	print(pow(A, B, mod))


import sys
mod = 1000000007
count = int(next(sys.stdin))
for line in sys.stdin:
	(base, power) = map(int, line.split())
	print(pow(base, power, mod))


for eachCase in range(0, int(input())):
	(a, b) = input().split(' ')
	(a, b) = (int(a), int(b))
	n = 10 ** 9 + 7
	b = b % (n - 1)
	a = a % n
	m = 1
	c = a
	while b > 0:
		if b % 2 == 1:
			m = m * c % n
		c = c * c % n
		b //= 2
	print(m)


import sys
mod = int(1000000000.0 + 7)
phi = mod - 1

def qmod(a, b):
	result = 1
	while b > 0:
		if b & 1:
			result = result * a % mod
		a = a ** 2 % mod
		b >>= 1
	return result
t = int(sys.stdin.readline())
for case in range(t):
	(a, b) = sys.stdin.readline().split(' ')[:]
	(a, b) = (int(a), int(b))
	if b <= phi:
		print(qmod(a, b))
	else:
		print(qmod(a, b % phi + phi))


def bin_pow(a, pow, MOD):
	res = 1
	while pow > 0:
		if pow % 2 == 1:
			pow -= 1
			res = res * a % MOD
		else:
			pow //= 2
			a = a * a % MOD
	return res
N = int(input())
for i in range(0, N):
	(a, b) = map(int, input().split())
	print(bin_pow(a, b % 1000000006, 1000000007))


def Solve(A, B):
	Solution = pow(A, B, 1000000007)
	print(Solution)
NumberOfCases = int(input())
for Cases in range(NumberOfCases):
	(A, B) = input().split()
	Solve(int(A), int(B))


T = int(input())
modval = 10 ** 9 + 7
for _ in range(T):
	(num, power) = [int(n) for n in input().split(' ')]
	print(pow(num, power, modval))


T = int(input())
for t in range(T):
	(A, B) = input().split()
	A = int(A)
	B = int(B)
	M = pow(A, B, 1000000007)
	print(M)


T = int(input())
while T != 0:
	T = T - 1
	num = input().split()
	print(pow(int(num[0]), int(num[1]), 1000000007))


import math
t = int(input())
for i in range(1, t + 1):
	(n, m) = input().split(' ')
	n = int(n)
	m = int(m)
	ans = pow(n, m, 1000000007)
	print(ans)
	i = i + 1


t = int(input())
while t:
	(a, b) = input().split(' ')
	print(pow(int(a), int(b), 1000000007))
	t = t - 1


t = int(input())
for i in range(t):
	(a, b) = input().split()
	(a, b) = [int(a), int(b)]
	print(pow(a, b, 10 ** 9 + 7))


t = int(input())
while t:
	(a, b) = input().split(' ')
	c = pow(int(a), int(b), 1000000007)
	print(c)
	t = t - 1


def pow_mod(a, b, m):
	r = 1
	while 1:
		if b % 2:
			r = r * a % m
		b >>= 1
		if b == 0:
			break
		a = a * a % m
	return r
m = 1000000007
N = int(input().strip())
for _ in range(N):
	(a, b) = map(int, input().split(' '))
	print(pow_mod(a, b % (m - 1), m))


t = int(input())
for t in range(t):
	line = input().split()
	a = int(line[0])
	b = int(line[1])
	print(pow(a, b, 1000000007))


M = 10 ** 9 + 7
for t in range(int(input())):
	(A, B) = [int(e) for e in input().strip().split(' ')]
	print(pow(A, B, M))


T = int(input())
for t in range(T):
	(A, B) = [int(x) for x in input().split(' ')]
	print(pow(A, B, 10 ** 9 + 7))


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


import sys
MOD = 1000000007
T = int(sys.stdin.readline())
for _ in range(T):
	(A, B) = list(map(int, sys.stdin.readline().split()))
	print(pow(A, B, MOD))


t = int(input())
c = 0
while t > c:
	w = input().split(' ')
	a = int(w[0])
	b = int(w[1])
	print(pow(a, b, 1000000007))
	c += 1


t = int(input())
for i in range(t):
	(a, b) = [int(i) for i in input().split()]
	print(pow(a, b, 1000000007))


from fractions import gcd
MOD = 10 ** 9 + 7
caseCnt = int(input())
for caseNr in range(caseCnt):
	(a, b) = [int(x) for x in input().split()]
	a = a % MOD
	print(pow(a, b, MOD))


m = 1000000007
for t in range(int(input())):
	(b, p) = map(int, input().split())
	print(pow(b, p, m))


t = int(input())
for i in range(t):
	s = input().strip().split()
	a = int(s[0])
	b = int(s[1])
	p = int(1000000000.0 + 7)
	print(pow(a, b, p))


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


def modexp(g_base, a):
	x = 1
	p_mod = 10 ** 9 + 7
	a = a % (p_mod - 1)
	bits = '{0:b}'.format(a)
	for (i, bit) in enumerate(bits):
		if bit == '1':
			x = x ** 2 * g_base % p_mod
		elif bit == '0':
			x = x ** 2 % p_mod
	return x % p_mod
max = int(input())
for i in range(0, max):
	tempstring = input()
	templist = tempstring.split()
	result = modexp(int(templist[0]), int(templist[1]))
	print(result)


for case in range(int(input())):
	(a, b) = [int(x) for x in input().split(' ')]
	print(pow(a, b, 10 ** 9 + 7))


import sys

def fast_pow(a, b):
	ans = 1
	while b > 0:
		if b & 1:
			ans = ans * a % (10 ** 9 + 7)
		a = a * a % (10 ** 9 + 7)
		b >>= 1
	return ans
test = int(input())
for i in range(test):
	(a, b) = map(int, sys.stdin.readline().split())
	b = b % 1000000006
	print(fast_pow(a, b))


casenum = int(input())
mod = 10 ** 9 + 7
for cases in range(casenum):
	(a, b) = input().split()
	(a, b) = (int(a), int(b))
	print(pow(a, b, mod))


import sys
import math
n = int(sys.stdin.readline().strip())
mod = 10 ** 9 + 7
while n != 0:
	n = n - 1
	(a, b) = [int(x) for x in sys.stdin.readline().strip().split()]
	print(pow(a, b, mod))


import sys

def powMod(a, p, m):
	if p < 2:
		if p == 1:
			return a % m
		else:
			return 1
	else:
		v = powMod(a, p // 2, m)
		v *= v
		v = v % m
		if p % 2 == 0:
			return v
		else:
			return v * a % m

def PowMod(a, b, m):
	if a % m == 0:
		return 0
	else:
		return powMod(a % m, b % (m - 1), m)
n = int(sys.stdin.readline())
for i in range(0, n):
	m = sys.stdin.readline().split(' ')
	print(PowMod(int(m[0]), int(m[1]), 1000000007))


t = int(input())
for _ in range(t):
	(a, b) = [int(i) for i in input().split()]
	mod = 10 ** 9 + 7
	ret = 1
	a %= mod
	b %= mod - 1
	while b > 0:
		if b % 2 == 1:
			ret = ret * a % mod
		b >>= 1
		a = a ** 2 % mod
	print(ret)


import sys
import math

def main():
	tc = int(input())
	for cs in range(tc):
		(a, b) = map(int, sys.stdin.readline().split())
		print(pow(a, b, 1000000007))
main()


for i in range(int(input())):
	(a, b) = [int(e) for e in input().split()]
	print(pow(a, b, 10 ** 9 + 7))


numCases = int(input())
for case in range(numCases):
	(a, b) = map(int, input().split())
	result = pow(a, b, 1000000007)
	print(result)


import sys
mod1 = 1000000007
t = int(sys.stdin.readline())
for i in range(t):
	(a, b) = list(map(int, sys.stdin.readline().split()))
	print(pow(a, b, mod1))


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


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


mod = 1000000007
for i in range(int(input())):
	(a, b) = [int(x) for x in input().split()]
	print(pow(a, b % (mod - 1), mod))


import sys
MOD = 1000000007
T = int(sys.stdin.readline())
for _ in range(T):
	(A, B) = list(map(int, sys.stdin.readline().split()))
	print(pow(A, B, MOD))


import sys
MOD = 1000000007
T = int(sys.stdin.readline())
for _ in range(T):
	(A, B) = list(map(int, sys.stdin.readline().split()))
	print(pow(A, B, MOD))


t = int(input())
for i in range(t):
	values = [int(num) for num in input().split()]
	print(pow(values[0], values[1], 1000000007))


t = int(input())
for _ in range(t):
	(a, b) = [int(x) for x in input().split()]
	print(pow(a, b, 1000000007))


def findpow(base, power):
	ans = 1
	basepower = base
	while power > 0:
		if power & 1 == 1:
			ans = ans * basepower % 1000000007
		basepower = basepower * basepower % 1000000007
		power >>= 1
	return ans
t = int(input())
while t > 0:
	t -= 1
	[a, b] = input().split()
	a = int(a) % 1000000007
	b = int(b) % 1000000006
	ans = findpow(a, b)
	print(ans)


MOD = 10 ** 9 + 7

def calculate(str_a, str_b):
	a = int(str_a) % MOD
	res = 1
	remainder = 0
	for char in str_b:
		remainder = int(char)
		res = res ** 10 * a ** remainder % MOD
	return res
for _ in range(int(input())):
	(a, b) = input().split()
	print(calculate(a, b))


for i in range(int(input())):
	(A, B) = map(int, input().split())
	print(pow(A, B, 1000000007))


modulus = 1000000007
Phi = modulus - 1

def binary_exp(N):
	exp = []
	while N > 0:
		exp.append(N % 2)
		N = N // 2
	return exp
T = int(input())
for i in range(T):
	(A, B) = map(int, input().split())
	B %= Phi
	A %= modulus
	res = 1
	binary_power = A
	B_exp = binary_exp(B)
	for e in B_exp:
		if e != 0:
			res *= binary_power
			res %= modulus
		binary_power *= binary_power
		binary_power %= modulus
	print(res)


import sys
MOD = 1000000007
T = int(sys.stdin.readline())
for _ in range(T):
	(A, B) = list(map(int, sys.stdin.readline().split()))
	print(pow(A, B, MOD))


import sys
MOD = 1000000007
T = int(sys.stdin.readline())
for _ in range(T):
	(A, B) = list(map(int, sys.stdin.readline().split()))
	print(pow(A, B, MOD))


import sys
MOD = 1000000007
T = int(sys.stdin.readline())
for _ in range(T):
	(A, B) = list(map(int, sys.stdin.readline().split()))
	print(pow(A, B, MOD))


def div(lis, d):
	res = lis[:]
	temp = 0
	for (i, x) in enumerate(res):
		temp *= 10
		temp += x
		res[i] = temp // d
		temp = temp % d
	return [res, temp]

def modPow(x, y, m):
	if y == 0:
		return 1
	if y == 1:
		return x
	temp = modPow(x, y // 2, m)
	if y % 2 == 0:
		return temp * temp % m
	else:
		return temp * temp % m * x % m
t = int(input())
for _ in range(t):
	(x, y) = input().split()
	x = div(list(map(int, x)), 10 ** 9 + 7)[1]
	y = div(list(map(int, y)), 10 ** 9 + 6)[1]
	print(modPow(x, y, 10 ** 9 + 7))


t = int(input())
for i in range(t):
	(a, b) = [int(j) for j in input().split()]
	print(int(pow(a, b, 1000000007)))


MODULO = 1000000007
t = int(input())

def PowMod(a, n):
	x = 1
	while n > 0:
		if n & 1 == 1:
			x = x * a % MODULO
		a = a * a % MODULO
		n >>= 1
	return x % MODULO
for i in range(t):
	(a, b) = map(int, input().split())
	print(PowMod(a % MODULO, b % (MODULO - 1)))


def fast_ex(n, mod, p):
	if p == 0:
		return 1
	if p & 1 == 1:
		return n * fast_ex(n, mod, p - 1) % mod
	else:
		return fast_ex(n, mod, p >> 1) ** 2 % mod

def cal_mod(l, mod):
	n = 0
	for i in l:
		n = (n * 10 % mod + i) % mod
	return n

def main():
	mod = 10 ** 9 + 7
	for i in range(int(input())):
		(n, p) = input().split()
		n = cal_mod(list(map(int, list(n))), mod)
		p = cal_mod(list(map(int, list(p))), mod - 1)
		print(fast_ex(n % mod, mod, p))
main()


def main():
	t = int(input())
	for _ in range(t):
		(a, b) = list(map(int, input().split()))
		print(pow(a, b, 10 ** 9 + 7))
main()


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


t = int(input())
while t:
	s = input()
	l = s.split()
	a = int(l[0])
	b = int(l[1])
	print(pow(a, b, 1000000007))
	t -= 1


t = int(input())
for i in range(t):
	(a, b) = (int(j) for j in input().split())
	print(pow(a, b, 10 ** 9 + 7))


t = int(input())
for _ in range(t):
	(a, b) = [int(elem) for elem in input().split()]
	print(pow(a, b, 1000000007))


from sys import stdin
import math

def delimitedInts(delimiter=' '):
	return [int(e) for e in stdin.readline().strip().split(delimiter)]

def charsToInts():
	return [int(e) for e in list(stdin.readline().strip())]

def charsToBools():
	return [bool(e) for e in charsToInts()]

def initIntArray(a, b, val=0):
	return [[val for x in range(b)] for x in range(a)]

def singleInt():
	return int(stdin.readline())

def module_exp(b, e, m):
	res = 1
	b = b % m
	while e > 0:
		if e % 2 == 1:
			res = res * b % m
		e = e >> 1
		b = b * b % m
	return res % m
t = singleInt()
for c in range(t):
	[a, b] = delimitedInts()
	print(pow(a, b, 1000000007))


Modulo = 10 ** 9 + 7
T = int(input())
for i in range(T):
	stream = input()
	stream = stream.split(' ')
	A = int(stream[0])
	B = int(stream[1])
	print(pow(A, B, Modulo))


from functools import reduce
M = 1000000007
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	exponent = '{0:b}'.format(b % (M - 1))
	n_powers = len(exponent)
	power_table = [a] * n_powers
	for i in range(1, n_powers):
		power_table[i] = power_table[i - 1] ** 2 % M
	print(reduce(lambda x, y: x * y % M, [power_table[i] for i in range(n_powers) if exponent[n_powers - i - 1] == '1'], 1))


t = int(input(''))
mod = 1000000007
for i in range(t):
	(a, b) = map(int, input('').split())
	a %= mod
	print(pow(a, b, mod))


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


m = 10 ** 9 + 7
for _ in range(int(input())):
	(a, b) = [int(ns) for ns in str(input()).split()]
	print(pow(a, b, m))