Read problem statements in [Vietnamese],
[Bengali], [Mandarin Chinese], and [Russian] as well. 

Chef has two numbers $N$ and $M$. Help Chef to find number of integer $N$-tuples $(A_{1}, A_{2}, \ldots, A_{N})$ such that $0 ≤ A_{1}, A_{2}, \ldots, A_{N} ≤ 2^{M} - 1$ and $A_{1} \& A_{2} \& \ldots \& A_{N} = 0$, where $\&$ denotes the [bitwise AND] operator.

Since the number of tuples can be large, output it modulo $10^{9}+7$. 

------  Input ------
The first line contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first and only line of each test case contains two integers $N$ and $M$.

------  Output ------
For each test case, output in a single line the answer to the problem modulo $10^{9}+7$. 

------  Constraints ------
$1 ≤ T ≤ 10^{5}$
$1 ≤ N, M ≤ 10^{6}$

------ Subtasks ------
Subtask #1 (100 points): original constraints

----- Sample Input 1 ------ 
4

1 2

2 2

4 2

8 4
----- Sample Output 1 ------ 
1

9

225

228250597
----- explanation 1 ------ 
Test Case $1$: The only possible tuple is $(0)$.

Test Case $2$: The tuples are $(0, 0)$, $(0, 1)$, $(0, 2)$, $(0, 3)$, $(1, 0)$, $(2, 0)$, $(3, 0)$, $(1, 2)$, $(2, 1)$.

Source: codechef | Difficulty: MEDIUM_HARD
Tags: Bit manipulation

Combinatorics

Mathematics


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


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


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	p = pow(pow(2, n, 1000000007) - 1, m, 1000000007)
	print(p)


testcases = int(input())
for eachcase in range(testcases):
	(length, limit) = map(int, input().split())
	combos = pow(pow(2, length, 1000000007) - 1, limit, 1000000007)
	print(combos)


mod = 10 ** 9 + 7
for _ in range(int(input())):
	(N, M) = list(map(int, input().split()))
	print(pow(pow(2, N, mod) - 1, M, mod))


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


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
for _ in range(int(input())):
	[N, M] = [int(i) for i in input().split(' ')]
	ans = power(power(2, N, 1000000007) - 1, M, 1000000007)
	print(ans)


T = int(input())
for i in range(T):
	(N, M) = map(int, input().split())
	comp = pow(2, N, 10 ** 9 + 7) - 1
	res = pow(comp, M, 10 ** 9 + 7)
	print(res)


md = 10 ** 9 + 7
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	nm = pow(2, n, md) - 1
	ans = pow(nm, m, md)
	print(ans)


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


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


mod = 10 ** 9 + 7
n = int(input())
for i in range(n):
	(x, y) = map(int, input().split())
	print(pow(pow(2, x, mod) - 1, y, mod))


def solve():
	ans = pow(pow(2, n, mod) - 1, m, mod)
	print(ans)
t = int(input())
for _ in range(t):
	mod = 10 ** 9 + 7
	(n, m) = list(map(int, input().split()))
	solve()


M = 1000000007

def mpow(x, p):
	r = 1
	while p:
		if p % 2:
			r = r * x % M
		x = x * x % M
		p >>= 1
	return r
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	print(mpow(mpow(2, n) - 1, m))


from sys import stdin, stdout
import math
from collections import Counter
import functools
import time
import bisect

def tr():
	return range(int(line()))

def sm():
	return map(int, line().split())

def ln():
	return list(sm())

def nl():
	return int(line())

def ssm():
	return map(str, line().split())

def line():
	return stdin.readline().rstrip()

def b(x):
	return bin(x).replace('0b', '')

def o(x):
	if type(x) != type(''):
		x = str(x)
	stdout.write(x + '\n')

def osp(x):
	if type(x) != type(''):
		x = str(x)
	stdout.write(x + ' ')

def ol(x):
	stdout.write(' '.join(map(str, x)))

def wline():
	return stdin.read().split()

def main():
	modulo = 1000000007
	for _ in tr():
		(n, m) = sm()
		print(pow(pow(2, n, modulo) - 1, m, modulo))
main()


x = int(input())
for i in range(x):
	(n, m) = map(int, input().split())
	r = pow(2, n, 1000000007) - 1
	t = pow(r, m, 1000000007)
	print(t)


MOD = 10 ** 9 + 7
n_testcase = int(input())
for testcase in range(n_testcase):
	(n, m) = (int(x) for x in input().split())
	n_tuples = pow(pow(2, n, MOD) - 1, m, MOD)
	print(n_tuples)


large_prime = 1000000007
twopows = list()

def init_twopows(l=1000000):
	twopows.append(1)
	for _ in range(l):
		twopows.append(twopows[-1] * 2 % large_prime)

def fast_exp(a, p):
	ret = 1
	api = a
	while p > 0:
		if p & 1:
			ret = ret * api % large_prime
		p >>= 1
		api = api * api % large_prime
	return ret

def f(n, m):
	print(fast_exp(twopows[n] - 1, m) % large_prime)
t = int(input())
init_twopows()
for _ in range(t):
	(n, m) = input().split()
	f(int(n), int(m))


t = int(input())
NUM = 1000000007
while t:
	(N, M) = input().split()
	N = int(N)
	M = int(M)
	ans = pow(2, N, NUM) - 1
	print(pow(ans, M, NUM))
	t = t - 1
exit()


MOD = 1000000007
n_testcase = int(input())
for testcase in range(n_testcase):
	(n, m) = (int(x) for x in input().split())
	n_tuples = pow(pow(2, n, MOD) - 1, m, MOD)
	print(n_tuples)


for i in range(int(input())):
	l = list(map(int, input().split()))
	c = pow(2, l[0], 1000000007) - 1
	print(pow(c, l[1], 1000000007))


mod = pow(10, 9) + 7
for i in range(int(input())):
	(n, m) = map(int, input().split(' '))
	a = pow(2, n, mod) - 1
	b = pow(a, m, mod)
	print(int(b))


mo = 1000000007
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	b = pow(2, n, mo) - 1
	print(pow(b, m, mo))


for i in range(int(input())):
	(a, b) = map(int, input().split())
	c = pow(2, a, 1000000007) - 1
	print(pow(c, b, 1000000007))


tc = int(input())
while tc != 0:
	(n, m) = map(int, input().split())
	k = pow(2, n, 1000000007) - 1
	print(pow(k, m, 1000000007))
	tc -= 1


def power(a, b, m):
	a %= m
	res = 1
	while b:
		if b & 1:
			res = res * a % m
		a = a * a % m
		b >>= 1
	return res
t = int(input())
mod = 1000000007
while t > 0:
	t -= 1
	(n, m) = map(int, input().split())
	print(power(power(2, n, mod) - 1, m, mod))


p = 10 ** 9 + 7

def power(x, y):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y:
		if y & 1:
			res = res * x % p
		x = x * x % p
		y = y // 2
	return res
for t in range(int(input())):
	(n, m) = map(int, input().split())
	ans = power(power(2, n) - 1, m)
	print(ans)


MOD = 1000000007

def binExpo(a, n, mod):
	res = 1
	a %= mod
	while n > 0:
		if n & 1:
			res *= a % mod
		a *= a % mod
		n >>= 1
	return res
for _ in range(int(input())):
	(N, M) = map(int, input().split())
	ans = binExpo(2, N, MOD) - 1
	print(binExpo(ans, M, MOD) % MOD)


t = int(input())
for _ in range(t):
	(n, m) = [int(a) for a in input().split()]
	mod = 1000000007
	res = pow(pow(2, n, mod) - 1, m, mod)
	print(res)


t = int(input())
while t > 0:
	t -= 1
	(n, m) = tuple(map(int, input().split()))
	mod = 1000000007
	a = pow(2, n, mod) - 1
	print(pow(a, m, mod))


from math import log2

def bin_exp(a, b, EXP):
	lim = int(log2(b)) + 1
	val = 1
	for i in range(lim):
		if 2 ** i & b != 0:
			val = val * EXP[i + 1] % MOD
	return val

def main():
	t = int(input())
	for _ in range(t):
		(n, m) = map(int, input().split())
		a1 = (bin_exp(2, n, EXP) - 1) % MOD
		EXPT[1] = a1
		for i in range(2, P):
			EXPT[i] = EXPT[i - 1] ** 2 % MOD
		a2 = bin_exp(a1, m, EXPT) % MOD
		print(a2)
MOD = 10 ** 9 + 7
P = int(log2(10 ** 6)) + 2
EXP = [1] * P
EXPT = [1] * P
EXP[1] = 2
for i in range(2, P):
	EXP[i] = EXP[i - 1] ** 2 % MOD
main()


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	a = pow(2, n, 1000000007) - 1
	print(pow(a, m, 1000000007))


MOD = int(1000000000.0 + 7)
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	print(pow(pow(2, n, MOD) - 1, m, MOD))


MOD = 10 ** 9 + 7

def NoOfZeroBitwiseAndTuples(N, M):
	twoPowerN = pow(2, N, MOD)
	subOne = (twoPowerN - 1) % MOD if twoPowerN - 1 > 0 else MOD + twoPowerN - 1
	count = pow(subOne, M, MOD)
	return count
T = int(input())
for case in range(T):
	(N, M) = map(int, input().split())
	print(NoOfZeroBitwiseAndTuples(N, M))


def modular_exponentiation(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
try:
	t = int(input())
	p = 10 ** 9 + 7
	while t:
		t -= 1
		(n, m) = map(int, input().split())
		a = pow(2, n, p) - 1
		b = pow(a, m, p)
		print(b)
except:
	pass


import sys
t = int(sys.stdin.readline())
for i in range(t):
	listed = sys.stdin.readline().strip().split(' ')
	N = int(listed[0])
	M = int(listed[1])
	print(pow(pow(2, N, 1000000007) - 1, M, 1000000007) % 1000000007)


t = int(input())
mod = 1000000007
for _ in range(t):
	(a, b) = map(int, input().split())
	tmp = pow(2, a, mod) - 1
	res = pow(tmp, b, mod)
	print(res)


t = int(input())
ans = []
for _ in range(t):
	mod = 1000000007
	(n, m) = map(int, input().split())
	base = pow(2, n, mod) - 1
	count = pow(base, m, mod)
	ans.append(count)
for _ in ans:
	print(_)


def pow(x, n):
	if n == 1:
		return x
	elif n == 0:
		return 1
	else:
		ans = pow(x, n // 2) % (10 ** 9 + 7)
		ans = ans * ans % (10 ** 9 + 7)
		if n % 2 != 0:
			ans = ans * x % (10 ** 9 + 7)
		return ans
for i in range(int(input())):
	(n, m) = map(int, input().split())
	print(pow((pow(2, n) - 1) % (10 ** 9 + 7), m))


t = int(input())
while t > 0:
	(aval, bval) = map(int, input().split())
	cval = pow(2, aval, 1000000007)
	dval = cval - 1
	xval = pow(dval, bval, 1000000007)
	print(xval)
	t -= 1


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	va = pow(2, n, 1000000007) - 1
	ans = pow(va, m, 1000000007)
	print(ans)


t = int(input())
for _ in range(t):
	(n, m) = [int(x) for x in input().split()]
	ans = int(pow(2, n, 1000000007)) - 1
	ans = int(pow(ans, m, 1000000007))
	print(ans)


t = int(input())
mod = 1000000007
while t:
	(n, m) = input().split()
	n = int(n)
	m = int(m)
	base = pow(2, n, mod) - 1
	print(pow(base, m, mod))
	t -= 1


testcase = int(input())
for ele in range(testcase):
	(N, M) = list(map(int, input().rstrip().split()))
	mod = 10 ** 9 + 7
	x = pow(2, N, mod) - 1
	ans = pow(x, M, mod)
	print(ans)


import sys
from os import path
if path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output1.txt', 'w')
from heapq import heappop, heappush, heapify
from math import ceil
mod = 10 ** 9 + 7
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	ans = pow(2, n, mod) - 1
	print(pow(ans, m, mod))


t = int(input())
mod = 1000000007
while t > 0:
	(N, M) = input().split()
	N = int(N)
	M = int(M)
	i = pow(2, N, mod) - 1
	i = pow(i, M, mod)
	print(i)
	t -= 1


def binexp(N, M, K):
	if M == 1:
		return N
	res = binexp(N * N % K, M // 2, K)
	if M % 2 == 1:
		res = N * res % K
	return res

def run_one_test_case():
	(N, M) = list(map(int, input().split()))
	K = 10 ** 9 + 7
	B = binexp(2, N, K)
	B = (B - 1) % K
	print(binexp(B, M, K))

def run_one_test_case1():
	(N, M) = list(map(int, input().split()))
	K = 10 ** 9 + 7
	P = (2 ** N - 1) % K
	print(P ** M % K)

def main():
	for _ in range(int(input())):
		run_one_test_case()
main()


mod = 10 ** 9 + 7
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	f = 1
	x = 2
	while n > 0:
		if n & 1 == 1:
			f = f * x % mod
		n = n >> 1
		x = x * x % mod
	f = f - 1
	f = f % mod
	x = f
	ans = 1
	while m > 0:
		if m & 1 == 1:
			ans = ans * x % mod
		m = m >> 1
		x = x * x % mod
	ans = ans % mod
	print(ans)


def power(x, y):
	x %= 10 ** 9 + 7
	res = 1
	while y:
		if y % 2:
			res = res * x % (10 ** 9 + 7)
		y >>= 1
		x *= x % (10 ** 9 + 7)
	return res
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	print(power(power(2, n) - 1, m) % (10 ** 9 + 7))


for i in range(int(input())):
	(n, m) = map(int, input().split())
	total = pow(2, n, 1000000007) - 1
	total = pow(total, m, 1000000007)
	print(total)


T = int(input())
while T > 0:
	arr = list(map(int, input().split()))
	n = arr[0]
	m = arr[1]
	a = pow(2, n, 1000000007) - 1
	b = pow(a, m, 1000000007)
	print(b)
	T -= 1


from sys import stdin, stdout

def power(a, b, mod=1000000007):
	res = 1
	while b > 0:
		if b & 1:
			res = res * a % mod
		b = b >> 1
		a = a * a % mod
	return res
for _ in range(int(stdin.readline())):
	(N, M) = map(int, stdin.readline().split())
	print(power(power(2, N) - 1, M))


test = int(input())
mod = 1000000007
while test:
	(N, M) = input().split()
	N = int(N)
	M = int(M)
	base = pow(2, N, mod) - 1
	print(pow(base, M, mod))
	test -= 1


import collections
from collections import defaultdict
import math
from math import gcd
from collections import Counter
mod = 1000000007
for _ in range(int(input())):
	(n, m) = [int(x) for x in input().split()]
	temp = pow(2, n, mod) - 1
	print(pow(temp, m, mod))


t = int(input())
mod = 1000000007
for _ in range(t):
	(n, m) = list(map(int, input().split()))
	print(pow(pow(2, n, mod) - 1, m, mod) % mod)


import sys

def modexpo1(base, power, mod):
	if power == 0:
		return 1
	elif power % 2 == 0:
		v = modexpo1(base, power // 2, mod) % mod
		return v * v % mod
	elif power % 2 != 0:
		return base % mod * modexpo1(base, power - 1, mod) % mod % mod
for k in range(int(input())):
	(n, m) = map(int, sys.stdin.readline().split())
	mod = pow(10, 9) + 7
	va = 1
	va1 = modexpo1(2, n, mod) - 1
	va2 = modexpo1(va1, m, mod)
	print(va2)


try:
	for i in range(int(input())):
		(a, b) = map(int, input().split())
		c = pow(2, a, 1000000007) - 1
		print(pow(c, b, 1000000007))
except:
	pass