Moamen and Ezzat are playing a game. They create an array $a$ of $n$ non-negative integers where every element is less than $2^k$.

Moamen wins if $a_1 \,\&\, a_2 \,\&\, a_3 \,\&\, \ldots \,\&\, a_n \ge a_1 \oplus a_2 \oplus a_3 \oplus \ldots \oplus a_n$.

Here $\&$ denotes the bitwise AND operation , and $\oplus$ denotes the bitwise XOR operation .

Please calculate the number of winning for Moamen arrays $a$.

As the result may be very large, print the value modulo $1000000\,007$ ($10^9 + 7$).


-----Input-----

The first line contains a single integer $t$ ($1 \le t \le 5$)— the number of test cases.

Each test case consists of one line containing two integers $n$ and $k$ ($1 \le n\le 2\cdot 10^5$, $0 \le k \le 2\cdot 10^5$).


-----Output-----

For each test case, print a single value — the number of different arrays that Moamen wins with.

Print the result modulo $1000000\,007$ ($10^9 + 7$).


-----Examples-----

Input
3
3 1
2 1
4 0
Output
5
2
1


-----Note-----

In the first example, $n = 3$, $k = 1$. As a result, all the possible arrays are $[0,0,0]$, $[0,0,1]$, $[0,1,0]$, $[1,0,0]$, $[1,1,0]$, $[0,1,1]$, $[1,0,1]$, and $[1,1,1]$.

Moamen wins in only $5$ of them: $[0,0,0]$, $[1,1,0]$, $[0,1,1]$, $[1,0,1]$, and $[1,1,1]$.

Difficulty: MEDIUM_HARD
Tags: Bit manipulation

Combinatorics

Dynamic programming

Mathematics

Matrices
Skill types: Dynamic programming

Bit manipulation

Starter code:

Solutions:
pri = pow(10, 9) + 7
import sys
input = sys.stdin.readline
a = int(input())
for i in range(a):
	(n, k) = map(int, input().split())
	g1 = pow(2, n, pri)
	g2 = pow(2, n, pri)
	if k == 0:
		print(1)
		continue
	ans = [0 for i in range(k)]
	if n % 2 == 0:
		ways = pow(2, n - 1, pri)
	else:
		ways = pow(2, n - 1, pri)
		ways += 1
	ans[0] = ways
	for i in range(1, k):
		if n % 2 == 0:
			ways = pow(2, n - 1, pri)
		else:
			ways = pow(2, n - 1, pri)
			ways += 1
		ways %= pri
		if n % 2 == 0:
			ans[i] = ans[i - 1] * (ways - 1) % pri
			ans[i] += g2
			ans[i] %= pri
			g2 = g2 * g1
			g2 %= pri
		else:
			ans[i] = ans[i - 1] * ways
			ans[i] %= pri
	print(ans[-1])


import heapq
import sys
import math
from collections import deque
from bisect import bisect_left, bisect_right
I = sys.stdin.readline
II = lambda : int(I())
IN = lambda x: map(int, x.split())
FN = lambda x: map(float, x.split())
L = lambda x: list(IN(x))
M = 1000000007
P = print
T = True
F = False
for _ in range(II()):
	(n, k) = IN(I())
	tot = pow(2, n - 1, M)
	g = 0
	eq = 0
	st = 0
	if n & 1 == 1:
		eq = (tot + 1) % M
	else:
		g = 1
		st = tot * 2 % M
		eq = (tot - 1) % M
	res = 0
	t = 1
	powers = [1]
	if g == 1:
		i = 1
		while i < k:
			powers.append(powers[-1] * st % M)
			i += 1
	i = k - 1
	while i >= 0:
		if g == 1:
			res = (res + powers[i] * t % M) % M
		t = t * eq % M
		i -= 1
	res = (res + t) % M
	print(res)


class Dsu:

	def __init__(self, n):
		self.parent = list(range(n))
		self.rank = [1] * n

	def find(self, x):
		while x != self.parent[x]:
			self.parent[x] = self.parent[self.parent[x]]
			x = self.parent[x]
		return x

	def union(self, x, y):
		(px, py) = (self.find(x), self.find(y))
		if px == py:
			return 0
		if self.rank[py] > self.rank[px]:
			(px, py) = (py, px)
		self.parent[py] = px
		self.rank[px] += self.rank[py]
		return 1

	def get_size(self, x):
		return self.rank[self.find(x)]

class SegTree:

	def __init__(self, n, array):
		self.n = n
		self.tree = [0] * (2 * n)
		for i in range(n, 2 * n):
			self.tree[i] = array[i - n]
		for i in range(n - 1, -1, -1):
			self.tree[i] = self.tree[2 * i] + self.tree[2 * i + 1]

	def update(self, i, val):
		i += self.n
		self.tree[i + self.n] = val
		while i:
			self.tree[i // 2] = self.tree[i] + self.tree[i ^ 1]
			i //= 2

	def query(self):
		pass

	def top(self):
		return self.tree[0]

class Comba:

	def __init__(self, mod):
		self.fact = array.array('i', [0] * MX)
		self.fact[0] = 1
		self.fact_inv = array.array('i', [0] * MX)
		self.mod = mod
		for i in range(1, MX):
			self.fact[i] = self.fact[i - 1] * i % self.mod
		self.fact_inv[MX - 1] = pow(self.fact[MX - 1], self.mod - 2, self.mod)
		for i in range(MX - 2, -1, -1):
			self.fact_inv[i] = self.fact_inv[i + 1] * (i + 1) % self.mod

	def ncr(self, n, r):
		if r > n or n < 0 or r < 0:
			return 0
		return self.fact[n] * self.fact_inv[r] % self.mod * self.fact_inv[n - r] % self.mod

	def npr(self, n, r):
		if r > n or n < 0 or r < 0:
			return 0
		return self.fact[n] * self.fact_inv[n - r] % self.mod

def prime(n):
	for div in range(2, int(n ** 0.5) + 1):
		if n % div == 0:
			return False
	return True

def lcm(x, y):
	return x * y // gcd(x, y)

def rw_file(confirm):
	if confirm:
		sys.stdin = open('', 'r')
		sys.stdout = open('', 'w')

def re(data=str):
	return data(sys.stdin.readline().rstrip())

def mp(data=str):
	return map(data, sys.stdin.readline().split())
import sys, array
from bisect import bisect_left, bisect_right, insort_left
from math import ceil, floor, log, sqrt, gcd
from collections import Counter, deque, defaultdict
from heapq import heappush, heappop, heapify
(mod, mod9, inf, nl, MX) = (1000000007, 998244353, 1e+18, '\n', 200003)
fact = array.array('i', [0] * MX)
fact[0] = 1
fact_inv = array.array('i', [0] * MX)
for i in range(1, MX):
	fact[i] = fact[i - 1] * i % mod
fact_inv[MX - 1] = pow(fact[MX - 1], mod - 2, mod)
for i in range(MX - 2, -1, -1):
	fact_inv[i] = fact_inv[i + 1] * (i + 1) % mod

def ncr(n, r):
	if r > n or n < 0 or r < 0:
		return 0
	return fact[n] * fact_inv[r] % mod * fact_inv[n - r] % mod

def solve(tc):
	(n, k) = mp(int)
	(even, odd) = (0, 0)
	for i in range(n):
		if i & 1:
			odd = (odd + ncr(n, i)) % mod
		else:
			even = (even + ncr(n, i)) % mod
	dp = [[0, 0] for i in range(k + 1)]
	dp[0][0] = 1
	for i in range(1, k + 1):
		dp[i][1] += dp[i - 1][1] * odd
		dp[i][1] += dp[i - 1][1] * even
		dp[i][0] += dp[i - 1][0] * even
		dp[i][1] += dp[i - 1][1]
		if n & 1:
			dp[i][0] += dp[i - 1][0]
		else:
			dp[i][1] += dp[i - 1][0]
		dp[i][1] %= mod
		dp[i][0] %= mod
	print((dp[-1][0] + dp[-1][1]) % mod)
	return None

def main():
	rw_file(False)
	cases = 1
	cases = re(int)
	for case in range(cases):
		solve(case + 1)
main()


MOD = 10 ** 9 + 7

def f(n, k):
	good = n - 1 & 1
	maybe = (pow(2, n - 1, MOD) + 1 - 2 * good) % MOD
	all_ = pow(2, n, MOD)
	return (good * (pow(all_, k, MOD) - pow(maybe, k, MOD)) * pow(all_ - maybe, MOD - 2, MOD) + pow(maybe, k, MOD)) % MOD
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	print(f(n, k))


import sys
import os.path
from collections import *
import math
import bisect
import heapq as hq
from fractions import Fraction
from random import randint
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
mod = 10 ** 9 + 7

def modExp(x, y):
	if y == 0:
		return 1
	if y % 2 == 0:
		return modExp(x * x % mod, y // 2)
	return x * modExp(x * x % mod, (y - 1) // 2) % mod
t = int(input())
while t:
	t -= 1
	(n, k) = [int(x) for x in input().split()]
	if k == 0:
		print(1)
		continue
	res = 0
	z = modExp(2, n - 1)
	y = z * 2
	p = 1
	if n % 2 == 0:
		for i in range(k):
			x = 1
			x = x * modExp(y, k - i - 1) % mod
			x = x * p % mod
			res = (res + x) % mod
			p = p * (z - 1) % mod
		res = (res + p) % mod
	else:
		res = modExp(z + 1, k)
	print(res)


import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
M = 10 ** 9 + 7

def main(t):
	(n, k) = map(int, input().split())
	if n % 2 == 1:
		equal = pow(2, n - 1, M) + 1
		ans = pow(equal, k, M)
	else:
		equal = pow(2, n - 1, M) - 1
		bigger = 1
		ans = 0
		for i in range(k):
			part1 = pow(2, k - i - 1, M)
			part = pow(part1, n, M)
			ans += pow(equal, i, M) * part % M
			ans = ans % M
		ans += pow(equal, k, M)
		ans = ans % M
	print(ans)
T = int(input())
t = 1
while t <= T:
	main(t)
	t += 1


t = int(input())
mod = 1000000007
for i in range(t):
	(n, k) = map(int, input().split())
	K = pow(2, n - 1, mod)
	if n & 1:
		ans = pow(K + 1, k, mod)
	else:
		R = pow(K + 1, mod - 2, mod)
		s = (pow(2, n * k, mod) - pow(K - 1, k, mod)) % mod * R % mod
		s += pow(K - 1, k, mod)
		ans = s % mod
	print(ans)


import sys
import io, os
import math
from heapq import *
gcd = math.gcd
sqrt = math.sqrt

def ceil(a, b):
	a = -a
	k = a // b
	k = -k
	return k
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def strinp(testcases):
	k = 5
	if testcases == -1 or testcases == 1:
		k = 1
	f = str(input())
	f = f[2:len(f) - k]
	return f
p = 1000000007

def fun(n, k):
	f = pow(2, n - 1, p)
	for i in range(2, k + 1):
		f = (pow(pow(2, n, p), i - 1, p) + (pow(2, n - 1, p) - 1) % p * f % p) % p
	return f

def main():
	t = int(input())
	for _ in range(t):
		arr = list(map(int, input().split()))
		n = arr[0]
		k = arr[1]
		if k == 0:
			print(1)
			continue
		if n % 2 == 1:
			a = pow(2, n - 1, p)
			a += 1
			a = a % p
			a = pow(a, k, p)
			print(a)
		else:
			print(fun(n, k))
main()


MOD = 10 ** 9 + 7
t = int(input())
for _ in range(t):
	(N, k) = map(int, input().split())
	x = pow(2, N - 1, MOD)
	y = pow(2, N, MOD)
	if N % 2 == 1:
		print(pow(x + 1, k, MOD))
	else:
		res = pow(x - 1, k, MOD)
		for i in range(k):
			res = (res + pow(x - 1, i, MOD) * 1 * pow(y, k - i - 1, MOD)) % MOD
		print(res)


import sys
import collections
infile = sys.stdin.buffer

def gs():
	return infile.readline().rstrip()

def gi():
	return int(gs())

def gss():
	return gs().split()

def gis():
	return [int(x) for x in gss()]
MOD = 10 ** 9 + 7
INF = 10 ** 10
p = [1 for i in range(2 * 10 ** 5 + 2)]
for i in range(1, len(p)):
	p[i] = p[i - 1] * 2
	p[i] %= MOD

def pow(a, n):
	return p[n]

def compute(n):
	return p[n - 1] - (1 - n & 1)

def dfs(i, k, n, s, mem):
	if i == k:
		return 1
	prev = 1
	p = pow(2, n)
	c = 1
	for i in range(k - 1, -1, -1):
		cur = 0
		cur = c if n & 1 == 0 else prev
		c *= p
		c %= MOD
		cur += s * prev % MOD
		cur %= MOD
		prev = cur
	return cur

def f(n, k):
	return dfs(0, k, n, compute(n), [])

def main(infn=''):
	global infile
	infile = open(infn, 'r') if infn else open(sys.argv[1], 'r') if len(sys.argv) > 1 else sys.stdin
	cn = int(input())
	for u in range(cn):
		(n, k) = map(int, input().split())
		print(f(n, k))
main()


import sys
import collections
infile = sys.stdin.buffer

def gs():
	return infile.readline().rstrip()

def gi():
	return int(gs())

def gss():
	return gs().split()

def gis():
	return [int(x) for x in gss()]
MOD = 10 ** 9
MOD += 7
INF = 10 ** 10
pw = [1 for i in range(2 * 10 ** 5 + 3)]
for i in range(1, len(pw)):
	pw[i] *= pw[i - 1]
	pw[i] *= 2
	pw[i] %= MOD
fact = [i for i in range(2 * 10 ** 5 + 3)]
fact[0] = 1
for i in range(2, len(fact)):
	fact[i] *= fact[i - 1]
	fact[i] %= MOD
factinv = [1 for _ in range(len(fact))]
factinv[len(fact) - 1] = pow(fact[len(fact) - 1], MOD - 2, MOD)
for ii in range(len(fact) - 2, -1, -1):
	factinv[ii] = factinv[ii + 1] * (ii + 1)
	factinv[ii] %= MOD

def nCr(n, r):
	return fact[n] * factinv[r] * factinv[n - r] % MOD

def compute(n):
	s = 0
	for t in range(0, n, 2):
		s += nCr(n, t)
		s %= MOD
	return s

def dfs(i, k, n, s, mem):
	if i == k:
		return 1
	prev = 1
	p = pw[n]
	c = 1
	for i in range(k - 1, -1, -1):
		ans = 0
		if n & 1 == 0:
			ans += pow(p, k - 1 - i, MOD)
			c *= p
			c %= MOD
			ans %= MOD
		else:
			ans += prev
			ans %= MOD
		ans += s * prev
		ans %= MOD
		prev = ans
	return ans

def f(n, k):
	return dfs(0, k, n, compute(n), [])

def main(infn=''):
	global infile
	infile = open(infn, 'r') if infn else open(sys.argv[1], 'r') if len(sys.argv) > 1 else sys.stdin
	cn = int(input())
	for u in range(cn):
		(n, k) = map(int, input().split())
		print(f(n, k))
main()


P = 10 ** 9 + 7
Q = P - 1
i2 = 1 + P >> 1
T = int(input())
for _ in range(T):
	(n, k) = map(int, input().split())
	if n % 2:
		print(pow(pow(2, n - 1, P) + 1, k, P))
	else:
		i2n = pow(i2, n, P)
		p2n1 = pow(2, n - 1, P) - 1
		print((pow(2, n * (k - 1) % Q, P) * (1 - pow(p2n1 * i2n, k, P)) % P * pow((1 - p2n1 * i2n) % P, P - 2, P) + pow(p2n1, k, P)) % P)


import sys
input = sys.stdin.readline
INF = int(1000000000.0) + 7

def power(x, y):
	if y == 0:
		return 1
	semi_result = power(x, y // 2) % INF
	if y % 2 == 0:
		return semi_result * semi_result % INF
	else:
		return x * semi_result * semi_result % INF
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	dp = [1] * (k + 1)
	g = power(2, n - 1)
	a = g * 2 % INF
	cache = [1] * (k + 1)
	for i in range(2, k + 1):
		cache[i] = cache[i - 1] * a % INF
	for i in range(1, k + 1):
		if n % 2 == 0:
			dp[i] = (cache[i] + dp[i - 1] * (g - 1)) % INF
		else:
			dp[i] = (dp[i - 1] + g * dp[i - 1]) % INF
	print(dp[k])


from math import *
import sys
input = sys.stdin.readline
print = sys.stdout.write
t = int(input())
mod = 1000000007

def power(x, y):
	x %= mod
	res = 1
	while y > 0:
		if y & 1:
			res *= x
			res %= mod
		y >>= 1
		x *= x
		x %= mod
	return res
for q in range(t):
	dp = []
	z = 1
	dp.append(1)
	s = input().split()
	n = int(s[0])
	k = int(s[1])
	for i in range(1, k + 1):
		dp.append(0)
		if n & 1:
			dp[i] = (power(2, n - 1) * dp[i - 1] % mod + dp[i - 1]) % mod
		else:
			dp[i] = (z + (power(2, n - 1) - 1) * dp[i - 1]) % mod
		z *= power(2, n)
		z %= mod
	print(str(int(dp[k])) + '\n')


mod = int(1000000000.0 + 7)
t = int(input())
for _ in range(t):
	(n, k) = [int(i) for i in input().split()]
	if n & 1:
		print(pow(pow(2, n - 1) + 1, k, mod))
	else:
		equal = pow(pow(2, n - 1, mod) - 1, k, mod)
		al = pow(2, n * k, mod) - equal
		al *= pow(pow(2, n - 1, mod) + 1, mod - 2, mod)
		al += equal
		al %= mod
		print(al)


MOD = 10 ** 9 + 7
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	ans = 1
	if n % 2:
		ans = pow(1 + 2 ** (n - 1), k, MOD)
	else:
		for i in range(k):
			ans = (pow(2, n - 1, MOD) - 1) * ans
			ans %= MOD
			ans += pow(pow(2, i, MOD), n, MOD)
			ans %= MOD
	print(ans)


def powmod(b, e, n):
	accum = 1
	i = 0
	bpow2 = b
	while e >> i > 0:
		if e >> i & 1:
			accum = accum * bpow2 % n
		bpow2 = bpow2 * bpow2 % n
		i += 1
	return accum

def memoize(function):
	cache = {}

	def decorated_function(*args):
		try:
			return cache[args]
		except KeyError:
			val = function(*args)
			cache[args] = val
			return val
	return decorated_function

@memoize
def inverseMod(n, mod):
	if 1 == n:
		return 1
	return (mod - mod // n) * inverseMod(mod % n, mod) % mod
M = 10 ** 9 + 7
F = [1, 1]
for n in range(2, 2 * 10 ** 5 + 1):
	F.append(F[-1] * n % M)
RF = [1, 1]
for n in range(2, 2 * 10 ** 5 + 1):
	RF.append(RF[-1] * inverseMod(n, M) % M)

def C(n, k):
	return F[n] * (RF[n - k] * RF[k] % M) % M

def count(n, k):
	if k == 0:
		return 1
	if n == 1:
		return powmod(2, k, M)
	r0 = powmod(2, n - 1, M) + (1 if n % 2 == 1 else 0) - 1
	r = 1 + r0
	b = powmod(2, n, M)
	bn = b
	for e in range(2, k + 1):
		if n % 2 == 0:
			r = r0 * r % M + bn
			bn = bn * b % M
		else:
			r = r + r0 * r % M
		r %= M
	return r % M
T = int(input())
for _ in range(T):
	(n, k) = map(int, input().split(' '))
	print(count(n, k))


class Dsu:

	def __init__(self, n):
		self.parent = list(range(n))
		self.rank = [1] * n

	def find(self, x):
		while x != self.parent[x]:
			self.parent[x] = self.parent[self.parent[x]]
			x = self.parent[x]
		return x

	def union(self, x, y):
		(px, py) = (self.find(x), self.find(y))
		if px == py:
			return 0
		if self.rank[py] > self.rank[px]:
			(px, py) = (py, px)
		self.parent[py] = px
		self.rank[px] += self.rank[py]
		return 1

	def get_size(self, x):
		return self.rank[self.find(x)]

class SegTree:

	def __init__(self, n, array):
		self.n = n
		self.tree = [0] * (2 * n)
		for i in range(n, 2 * n):
			self.tree[i] = array[i - n]
		for i in range(n - 1, -1, -1):
			self.tree[i] = self.tree[2 * i] + self.tree[2 * i + 1]

	def update(self, i, val):
		i += self.n
		self.tree[i + self.n] = val
		while i:
			self.tree[i // 2] = self.tree[i] + self.tree[i ^ 1]
			i //= 2

	def query(self):
		pass

	def top(self):
		return self.tree[0]

class Combinations:

	def __init__(self) -> None:
		self.facs = [0] * MX
		self.facInvs = [0] * MX
		self.facs[0] = 1
		for i in range(1, MX):
			self.facs[i] = self.facs[i - 1] * i % mod
		self.facInvs[MX - 1] = pow(self.facs[MX - 1], mod - 2, mod)
		for i in range(MX - 2, -1, -1):
			self.facInvs[i] = self.facInvs[i + 1] * (i + 1) % mod

	def ncr(self, n, r):
		if r > n or n < 0 or r < 0:
			return 0
		cur = self.facs[n]
		cur = cur * self.facInvs[r] % mod
		cur = cur * self.facInvs[n - r] % mod
		return cur

def is_prime(n):
	for div in range(2, int(2, n ** 0.5) + 1):
		if n % div == 0:
			return False
	return True
(mod, inf, MX, nl) = (1000000007, 1e+18, 210001, '\n')

def lcm(x, y):
	return x * y // gcd(x, y)

def rw_file(confirm):
	if not confirm:
		return None
	sys.stdin = open('', 'r')
	sys.stdout = open('', 'w')

def re(data=str):
	return data(sys.stdin.readline().rstrip())

def mp(data=str):
	return map(data, sys.stdin.readline().split())
import sys
from bisect import bisect_left, bisect_right, insort_left
from math import ceil, floor, log, gcd, sqrt
from collections import Counter, deque
from heapq import heappush, heappop, heapify

def solve(tc):
	(n, k) = mp(int)
	(even, odd) = (0, 0)
	for i in range(n):
		if i & 1:
			odd += c.ncr(n, i)
		else:
			even += c.ncr(n, i)
	dp = [[0, 0] for i in range(k + 1)]
	dp[0][0] = 1
	for i in range(1, k + 1):
		dp[i][1] += dp[i - 1][1] * odd
		dp[i][1] += dp[i - 1][1] * even
		dp[i][0] += dp[i - 1][0] * even
		dp[i][1] += dp[i - 1][1]
		if n & 1:
			dp[i][0] += dp[i - 1][0]
		else:
			dp[i][1] += dp[i - 1][0]
		dp[i][1] %= mod
		dp[i][0] %= mod
	print((dp[-1][0] + dp[-1][1]) % mod)
	return None

def main():
	rw_file(False)
	global c
	c = Combinations()
	cases = 1
	cases = re(int)
	for tc in range(cases):
		solve(tc + 1)
main()


from sys import stdin, stdout, setrecursionlimit
from bisect import bisect_left, bisect_right
from math import ceil, floor, log, gcd, sqrt, factorial
from collections import Counter, deque
from heapq import heappush, heappop, heapify

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

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

def test(cases):
	for _ in range(cases):
		solve()
mod = 1000000007
MOD = 10 ** 9 + 7

class Factorial:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorials = [1, 1]
		self.invModulos = [0, 1]
		self.invFactorial_ = [1, 1]

	def calc(self, n):
		if n <= -1:
			print('Invalid argument to calculate n!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.factorials):
			return self.factorials[n]
		nextArr = [0] * (n + 1 - len(self.factorials))
		initialI = len(self.factorials)
		prev = self.factorials[-1]
		m = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * i % m
		self.factorials += nextArr
		return self.factorials[n]

	def inv(self, n):
		if n <= -1:
			print('Invalid argument to calculate n^(-1)')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		p = self.MOD
		pi = n % p
		if pi < len(self.invModulos):
			return self.invModulos[pi]
		nextArr = [0] * (n + 1 - len(self.invModulos))
		initialI = len(self.invModulos)
		for i in range(initialI, min(p, n + 1)):
			next = -self.invModulos[p % i] * (p // i) % p
			self.invModulos.append(next)
		return self.invModulos[pi]

	def invFactorial(self, n):
		if n <= -1:
			print('Invalid argument to calculate (n^(-1))!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.invFactorial_):
			return self.invFactorial_[n]
		self.inv(n)
		nextArr = [0] * (n + 1 - len(self.invFactorial_))
		initialI = len(self.invFactorial_)
		prev = self.invFactorial_[-1]
		p = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p
		self.invFactorial_ += nextArr
		return self.invFactorial_[n]

class Combination:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorial = Factorial(MOD)

	def ncr(self, n, k):
		if k < 0 or n < k:
			return 0
		k = min(k, n - k)
		f = self.factorial
		return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD

class Dsu:

	def __init__(self, n):
		self.parent = list(range(n))
		self.rank = [1] * n

	def find(self, x):
		while x != self.parent[x]:
			self.parent[x] = self.parent[self.parent[x]]
			x = self.parent[x]
		return x

	def union(self, x, y):
		(px, py) = (self.find(x), self.find(y))
		if px == py:
			return 0
		if self.rank[py] > self.rank[px]:
			(px, py) = (py, px)
		self.parent[py] = px
		self.rank[px] += self.rank[py]
		return 1

	def get_size(self, x):
		return self.rank[self.find(x)]
c = Combination(mod)

def solve():
	(n, k) = ints()
	even = 0
	odd = 0
	for i in range(n):
		if i & 1:
			odd += c.ncr(n, i) % mod
		else:
			even += c.ncr(n, i) % mod
	dp = [[0, 0] for i in range(k + 1)]
	dp[0][0] = 1
	for i in range(1, k + 1):
		dp[i][1] += dp[i - 1][1] * odd % mod
		dp[i][1] += dp[i - 1][1] * even % mod
		dp[i][0] += dp[i - 1][0] * even % mod
		dp[i][1] += dp[i - 1][1] % mod
		if n & 1:
			dp[i][0] += dp[i - 1][0] % mod
		else:
			dp[i][1] += dp[i - 1][0] % mod
	print((dp[-1][0] + dp[-1][1]) % mod)
	return
test(int(re()))


MOD = 1000000007

def solve(n, k):
	if n % 2:
		ks = pow(2, n - 1, MOD) + 1
		return pow(ks, k, MOD)
	else:
		ks = pow(2, n - 1, MOD) - 1
		if k == 0:
			return 1
		else:
			ans = 1 + ks
			cg = pow(2, n, MOD)
			binn = cg
			for i in range(1, k):
				ans = (ans * ks % MOD + binn) % MOD
				binn = binn * cg % MOD
				ans %= MOD
			return ans
t = int(input())
for alskfjlakfja in range(t):
	(n, k) = [int(i) for i in input().split()]
	print(solve(n, k))


def power(base, num):
	bin_num = bin(num)[2:]
	store = [base]
	for _ in range(len(bin_num) - 1):
		store.append(store[-1] ** 2 % (10 ** 9 + 7))
	curr = 1
	for (idx, ch) in enumerate(bin_num[::-1]):
		if ch == '1':
			curr = curr * store[idx] % (10 ** 9 + 7)
	return curr
t = int(input())
for i in range(1, t + 1):
	(n, k) = list(map(int, input().split()))
	if k == 0:
		print(1)
	else:
		if n % 2 == 0:
			perm = power(2, n - 1) - 1
			perf = power(2, n)
		else:
			perm = power(2, n - 1) + 1
		res = 1
		if n % 2 == 1:
			print(power(perm, k))
		else:
			curr = 1
			curr_perf = 1
			for i in range(k):
				curr = curr * perm + curr_perf
				curr_perf *= perf
				curr = curr % (10 ** 9 + 7)
				curr_perf = curr_perf % (10 ** 9 + 7)
			print(curr)


from collections import *
import os, sys
from io import BytesIO, IOBase

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, 8192))
			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, 8192))
			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')
r = lambda dtype: dtype(input().strip())
rd = lambda dtype: [dtype(x) for x in input().split()]
r2d = lambda dtype, n: [r(dtype) for _ in range(n)]
rs2d = lambda dtype, n: [rd(dtype) for _ in range(n)]
r_enu = lambda dtype: [(i, x) for (i, x) in enumerate(rd(dtype))]
rs_enu = lambda dtype, n: [[i, rd(dtype)] for i in range(n)]
(ceil1, mod) = (lambda a, b: (a + b - 1) // b, 10 ** 9 + 7)
add = lambda a, b: (a + b) % mod
mult = lambda a, b: a * b % mod
for _ in range(r(int)):
	(n, k) = rd(int)
	(cur, ans, parity) = (1, 0, n & 1 == 0)
	for i in range(k - 1, -1, -1):
		ans = add(ans, mult(cur * parity, pow(pow(2, i, mod), n, mod)))
		cur = mult(cur, add(pow(2, n - 1, mod), -parity if parity else 1))
	print(add(ans, cur))


import sys
import math
from collections import deque, Counter
from sys import stdin
int1 = lambda x: int(x) - 1
inp = lambda : int(input())
mi = lambda : map(int, input().split())
li = lambda : list(mi())
mi1 = lambda : map(int1, input().split())
li1 = lambda : list(mi1())
mis = lambda : map(str, input().split())
lis = lambda : list(mis())
stinput = lambda : stdin.readline()[:-1]
stinp = lambda : int(stinput())
stmi = lambda : map(int, stdin.readline().split())
stli = lambda : list(stmi())
stmi1 = lambda : map(int1, stdin.readline().split())
stli1 = lambda : list(stmi1())
stmis = lambda : stdin.readline()[:-1]
pr = print
from collections import defaultdict
mod = 10 ** 9 + 7
Mod = 998244353
INF = 10 ** 18
ans = 0
pmod = mod
bignum = 10 ** 5 * 2 + 5
fac = [1] * bignum
ninv = [1] * bignum
finv = [1] * bignum
for i in range(2, bignum):
	fac[i] = fac[i - 1] * i % pmod
	ninv[i] = -(pmod // i) * ninv[pmod % i] % pmod
	finv[i] = finv[i - 1] * ninv[i] % pmod

def comb(n, k):
	if k > n:
		return 0
	return fac[n] * finv[k] % pmod * finv[n - k] % pmod
b = [1] * bignum
for i in range(1, bignum):
	b[i] = b[i - 1] * 2 % mod
t = inp()
for _ in range(t):
	(n, k) = mi()
	if n % 2 == 1:
		num = 1
		for i in range(0, n, 2):
			num += comb(n, i)
			num %= mod
		print(pow(num, k, mod))
	else:
		num = 0
		for i in range(0, n, 2):
			num += comb(n, i)
			num %= mod
		ans = 0
		a = [1] * (k + 1)
		for i in range(1, k + 1):
			a[i] = a[i - 1] * num % mod
		for i in range(k):
			if i == 0:
				x = b[k - 1]
				ans += pow(x, n, mod)
			else:
				x = a[i]
				y = b[k - i - 1]
				ans += x * pow(y, n, mod)
				ans %= mod
		ans += a[k]
		print(ans % mod)


import sys
input = sys.stdin.readline
MAX = 2 * 10 ** 5 + 100
MOD = 10 ** 9 + 7
fact = [0] * MAX
inv = [0] * MAX
finv = [0] * MAX
fact[0] = 1
fact[1] = 1
finv[0] = 1
finv[1] = 1
inv[1] = 1
for i in range(2, MAX):
	fact[i] = fact[i - 1] * i % MOD
	inv[i] = MOD - inv[MOD % i] * (MOD // i) % MOD
	finv[i] = finv[i - 1] * inv[i] % MOD

def C(n, r):
	if n < r:
		return 0
	if n < 0 or r < 0:
		return 0
	return fact[n] * (finv[r] * finv[n - r] % MOD) % MOD
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	dp = [[0] * 2 for _ in range(k + 1)]
	dp[0][0] = 1
	coef00 = 0
	for i in range(0, n, 2):
		coef00 += C(n, i)
		coef00 %= MOD
	coef01 = 0
	for i in range(1, n, 2):
		coef01 += C(n, i)
		coef01 %= MOD
	coef10 = 1 if n % 2 == 0 else 0
	coef11 = 1 if n % 2 == 1 else 0
	for i in range(k):
		dp[i + 1][0] += dp[i][0] * coef00 % MOD
		dp[i + 1][0] %= MOD
		dp[i + 1][1] += dp[i][1] * coef00 % MOD
		dp[i + 1][1] %= MOD
		dp[i + 1][1] += dp[i][1] * coef01 % MOD
		dp[i + 1][1] %= MOD
		dp[i + 1][1] += dp[i][0] * coef10
		dp[i + 1][1] %= MOD
		dp[i + 1][1] += dp[i][1] * coef10
		dp[i + 1][1] %= MOD
		dp[i + 1][0] += dp[i][0] * coef11
		dp[i + 1][0] %= MOD
		dp[i + 1][1] += dp[i][1] * coef11
		dp[i + 1][1] %= MOD
	print(sum(dp[k]) % MOD)


import sys, os
from io import BytesIO, IOBase
from math import floor, gcd, fabs, factorial, fmod, sqrt, inf, log
from collections import defaultdict as dd, deque
from heapq import merge, heapify, heappop, heappush, nsmallest
from bisect import bisect_left as bl, bisect_right as br, bisect
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')
(stdin, stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
mod = pow(10, 9) + 7
mod2 = 998244353

def inp():
	return stdin.readline().strip()

def iinp():
	return int(inp())

def out(var, end='\n'):
	stdout.write(str(var) + '\n')

def outa(*var, end='\n'):
	stdout.write(' '.join(map(str, var)) + end)

def lmp():
	return list(mp())

def mp():
	return map(int, inp().split())

def l1d(n, val=0):
	return [val for i in range(n)]

def l2d(n, m, val=0):
	return [l1d(m, val) for j in range(n)]

def ceil(a, b):
	return (a + b - 1) // b
S1 = 'abcdefghijklmnopqrstuvwxyz'
S2 = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'

def isprime(x):
	if x <= 1:
		return False
	if x in (2, 3):
		return True
	if x % 2 == 0:
		return False
	for i in range(3, int(sqrt(x)) + 1, 2):
		if x % i == 0:
			return False
	return True
N = 200000
pow2 = l1d(N + 1, 1)
for i in range(1, N + 1):
	pow2[i] = 2 * pow2[i - 1] % mod
for _ in range(iinp()):
	(n, k) = mp()
	if n % 2:
		x = (1 + pow2[n - 1]) % mod
		print(pow(x, k, mod))
	else:
		dp = l1d(k + 1)
		y = (pow2[n - 1] - 1 + mod) % mod
		dp[0] = 1
		x = 1
		for i in range(1, k + 1):
			dp[i] = (x + dp[i - 1] * y % mod) % mod
			x = x * pow2[n] % mod
		print(dp[k])


(KMAX, NMAX, MOD) = (2 * 10 ** 5, 2 * 10 ** 5, 10 ** 9 + 7)
powers = [1] * (NMAX + 1)
for j in range(1, NMAX + 1):
	powers[j] = 2 * powers[j - 1] % MOD
t = int(input())
for _ in range(t):
	(n, k) = (int(x) for x in input().split())
	if k:
		npowers = [1] * (k + 1)
		for j in range(1, k + 1):
			npowers[j] = npowers[j - 1] * powers[n] % MOD
		ways = [0] * k
		ways[0] = (powers[n - 1] + n % 2) % MOD
		for j in range(1, k):
			if n % 2 == 0:
				ways[j] = (powers[n - 1] - 1) * ways[j - 1] % MOD
				ways[j] = (ways[j] + npowers[j]) % MOD
			else:
				ways[j] = (powers[n - 1] + 1) * ways[j - 1] % MOD
		print(ways[-1])
	else:
		print(1)


mod = 1000000007
T = int(input())
fpow = pow
for i in range(T):
	ans = 1
	(n, k) = map(int, input().split())
	if n % 2 != 0:
		ans = fpow(2, n - 1, mod) + 1
		ans = fpow(ans, k, mod)
	else:
		ans = 1
		pow_ = 1
		_2_n_1 = pow(2, n - 1, mod)
		for i in range(k):
			ans = ans * (_2_n_1 - 1) % mod
			ans = (ans + pow_) % mod
			pow_ = pow_ * _2_n_1 * 2 % mod
	print(ans)


t = int(input())
modval = int(1000000000.0 + 7)
for _ in range(t):
	(n, k) = [int(x) for x in input().split(' ')]
	if not k:
		print('1')
		continue
	dp = [1 for _ in range(k + 1)]
	ndigsequal = pow(2, n - 1, modval)
	allopts = pow(2, n, modval)
	st = 1
	if n & 1:
		isodd = True
		ndigsequal += 1
	else:
		isodd = False
		ndigsequal -= 1
	for i in range(1, k + 1):
		ans = ndigsequal * dp[i - 1]
		ans %= modval
		if not isodd:
			ans += st
			ans %= modval
			st *= allopts
			st %= modval
		dp[i] = ans
	print(dp[k])


import math
import heapq
import string
from collections import deque
import sys
input = sys.stdin.readline
S = lambda : input()
I = lambda : int(S())
M = lambda : map(int, S().split())
L = lambda : list(M())
H = 1000000000 + 7
for _ in range(I()):
	(n, k) = M()
	s = 0
	if n % 2 == 1:
		s = pow(pow(2, n - 1, H) + 1, k, H)
	else:
		d = (pow(2, n - 1, H) - 1) % H
		p = pow(2, n, H) * pow(d, -1, H) % H
		z = pow(d, k - 1, H)
		m = pow(p, k, H) - 1
		q = p - 1
		s = m % H * pow(q, -1, H) * z
		s += pow(d, k, H)
	print(s % H)


def ksm(a, b, c=int(1000000000.0 + 7)):
	if b == 0:
		return 1
	a = a % c
	res = 1
	while b:
		if b % 2 == 1:
			res = res * a % c
		a = a * a % c
		b = b // 2
	return res
p = int(1000000000.0 + 7)
mi = [1]
for i in range(211111):
	mi.append(mi[i] * 2 % p)
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	if n % 2 == 1:
		da = 0
		den0 = ksm(2, n - 1)
		den1 = 1
	else:
		da = 1
		den0 = ksm(2, n - 1) - 1
		den1 = 0
	res = 0
	if n % 2 == 0:
		cz0 = 1
		cz1 = ksm(2, n)
		for i in range(1, k + 1):
			res = (res + ksm(cz1, k - i) * cz0) % p
			cz0 = cz0 * den0 % p
	res = (res + ksm(den1 + den0, k)) % p
	if k == 0:
		print(1)
	else:
		print(res)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	(m, ans) = (10 ** 9 + 7, 1)
	if n % 2:
		ans = pow(pow(2, n - 1, m) + 1, k, m)
	else:
		for i in range(k):
			ans = pow(pow(2, i, m), n, m) + (pow(2, n - 1, m) - 1) * ans
			ans %= m
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	m = 10 ** 9 + 7
	if k == 0:
		print(1)
		continue
	if n % 2 == 0:
		dp = [0 for i in range(k)]
		dp[0] = pow(2, n - 1, m)
		c = pow(2, n, m)
		for i in range(1, k):
			dp[i] = (pow(c, i, m) + dp[i - 1] * (pow(2, n - 1, m) - 1) % m) % m
		print(dp[-1])
	else:
		q = (pow(2, n - 1, m) + 1) % m
		print(pow(q, k, m))


MODULO = 1000000007

def calc(n, k):
	K = pow(2, n - 1, MODULO)
	if n & 1:
		return pow(K + 1, k, MODULO)
	else:
		R = pow(K + 1, MODULO - 2, MODULO)
		s = (pow(2, n * k, MODULO) - pow(K - 1, k, MODULO)) % MODULO * R % MODULO
		s += pow(K - 1, k, MODULO)
		return s % MODULO
for i in range(int(input())):
	(n, k) = input().split()
	print(calc(int(n), int(k)))


import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(2 * 10 ** 5 + 10)
write = lambda x: sys.stdout.write(x + '\n')
debug = lambda x: sys.stderr.write(x + '\n')
writef = lambda x: print('{:.12f}'.format(x))
M = 10 ** 9 + 7
N = 2 * 10 ** 5 + 10
g1 = [0] * (N + 1)
g2 = [0] * (N + 1)
inverse = [0] * (N + 1)
g1[0] = g1[1] = g2[0] = g2[1] = 1
(inverse[0], inverse[1]) = [0, 1]
for i in range(2, N + 1):
	g1[i] = g1[i - 1] * i % M
	inverse[i] = -inverse[M % i] * (M // i) % M
	g2[i] = g2[i - 1] * inverse[i] % M

def cmb(n, r, M=M):
	if r < 0 or r > n:
		return 0
	r = min(r, n - r)
	return g1[n] * g2[r] % M * g2[n - r] % M

def perm(n, r, M=M):
	if r < 0 or r > n:
		return 0
	return g1[n] * g2[n - r] % M

def sub(n, k):
	ans = 0
	for v in range(1 << k):
		for v2 in range(1 << k):
			if v & v2 >= v ^ v2:
				ans += 1
	return ans

def sub3(n, k):
	ans = 0
	for v in range(1 << k):
		for v2 in range(1 << k):
			for v3 in range(1 << k):
				if v & v2 & v3 >= v ^ v2 ^ v3:
					ans += 1
	return ans

def sub2(n, k):
	val = 0
	for i in range(0, n + 1, 2):
		val += cmb(n, i)
		if val > M:
			val -= M
	if k == 0:
		ans = 1
	elif n % 2 == 1:
		ans = pow(1 + val, k, M)
	else:
		ans = 0
		v = 1
		v2 = pow(2, n * (k - 1), M)
		inv = pow(pow(2, n, M), M - 2, M)
		for i in range(k):
			ans += v * v2 % M
			v *= val - 1
			v %= M
			v2 *= inv
			v2 %= M
			if ans > M:
				ans -= M
		ans += pow(val - 1, k, M)
	return ans
t = int(input())
res = []
for _ in range(t):
	(n, k) = list(map(int, input().split()))
	ans = sub2(n, k)
	res.append(ans % M)
write('\n'.join(map(str, res)))


MOD = 1000000007

def power(a, n):
	res = 1
	while n > 0:
		if n & 1:
			res = res * a % MOD
		a = a * a % MOD
		n >>= 1
	return res
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	if k == 0:
		print(1)
		continue
	poww = power(2, n - 1)
	if n % 2:
		print(power(poww + 1, k) % MOD)
	else:
		ans = poww
		y = poww * 2
		poww -= 1
		for i in range(1, k):
			ans = (ans * poww % MOD + y % MOD) % MOD
			y = 2 * y * (poww + 1) % MOD
		print(ans)


import sys
input = sys.stdin.readline
mod = 10 ** 9 + 7
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	ans = 0
	x = pow(2, n - 1, mod)
	if n % 2:
		ans = pow(x + 1, k, mod)
		print(ans)
	else:
		cur = 1
		for i in range(k):
			r = k - i - 1
			ans += pow(pow(2, r, mod), n, mod) * cur % mod
			ans %= mod
			cur = cur * (x - 1) % mod
		print((ans + cur) % mod)


import sys
input = sys.stdin.readline

def comb(n, r, mod):
	if r < 0 or r > n:
		return 0
	return g1[n] * g2[r] * g2[n - r] % mod
mod = 10 ** 9 + 7
N = 2 * 10 ** 5 + 1
g1 = [1, 1]
g2 = [1, 1]
inv = [0, 1]
for i in range(2, N + 1):
	g1.append(g1[-1] * i % mod)
	inv.append(-inv[mod % i] * (mod // i) % mod)
	g2.append(g2[-1] * inv[-1] % mod)
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	dp = [[0] * 2 for i in range(k + 1)]
	dp[0][0] = 1
	p2 = pow(2, n, mod)
	s = 0
	for j in range(0, n, 2):
		s += comb(n, j, mod)
		s %= mod
	if n % 2:
		s += 1
	for i in range(1, k + 1):
		if n % 2 == 0:
			dp[i][1] = (dp[i - 1][1] * p2 + dp[i - 1][0]) % mod
		else:
			dp[i][1] += dp[i - 1][1] * p2 % mod
		dp[i][0] = dp[i - 1][0] * s % mod
	print(sum(dp[k]) % mod)


t = int(input())

def tavan(a, b):
	global div
	nat = 1
	for i in range(b):
		nat = nat * a % div
	return nat % div
for i in range(t):
	(n, k) = list(map(int, input().split()))
	div = 1000000007
	two = pow(2, n - 1, div)
	if n % 2 == 1:
		print(pow(two + 1, k, div))
	else:
		two1 = pow(two - 1, k, div)
		nat = two1
		for i in range(k):
			nat = (nat + pow(two - 1, i, div) * pow(two * 2, k - i - 1, div) % div) % div
		print(nat % div)


import sys
input = sys.stdin.readline
rem = 1000000007
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	ans = 0
	if k == 0:
		print(1)
	elif n % 2 == 0:
		dp = [0] * k
		dp[0] = pow(2, n - 1, rem)
		xx = pow(2, n - 1, rem) - 1
		yy = pow(2, n, rem)
		for i in range(1, k):
			dp[i] = (dp[i - 1] * xx % rem + pow(yy, i, rem)) % rem
		print(dp[-1])
	else:
		dp = [0] * k
		dp[0] = (pow(2, n - 1, rem) + 1) % rem
		xx = pow(2, n - 1, rem) + 1
		for i in range(1, k):
			dp[i] = dp[i - 1] * xx % rem
		print(dp[-1])


t = int(input())
for i in range(t):
	[n, k] = [int(x) for x in input().split()]
	p = 10 ** 9 + 7
	pow2 = pow(2, n - 1, p)
	prev = 1
	if n % 2 == 0:
		prev = pow2
	else:
		prev = pow2 + 1
	z = 1
	mu = 2 * pow2 % p
	for h in range(2, k + 1):
		z = z * mu % p
		if n % 2 == 0:
			prev = (z + (pow2 - 1) * prev % p) % p
		else:
			prev = (pow2 + 1) * prev % p
	if k == 0:
		print(1)
	else:
		print(prev % p)


M = 1000000007

def solve(n, k):
	if k == 0:
		return 1
	p = pow(2, n - 1, M)
	q = pow(2, n, M)
	if n % 2 == 0:
		p -= 1
		d0 = 0
		d1 = 0
		for i in range(k):
			if i == 0:
				d0 = p
				d1 = 1
			else:
				d1 = (d1 * q + d0) % M
				d0 = d0 * p % M
		return (d0 + d1) % M
	else:
		return pow(p + 1, k, M)
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	print(solve(n, k))


import os
import sys
from io import BytesIO, IOBase
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')
from math import ceil

def prod(a, mod=10 ** 9 + 7):
	ans = 1
	for each in a:
		ans = ans * each % mod
	return ans

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

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

def binary(x, length=16):
	y = bin(x)[2:]
	return y if len(y) >= length else '0' * (length - len(y)) + y
for _ in range(int(input()) if True else 1):
	(n, k) = map(int, input().split())
	mod = 10 ** 9 + 7
	if n % 2:
		print(pow(pow(4, n // 2, mod) + 1, k, mod))
	else:
		p = pow(2, n - 1, mod)
		q = p * (p + 1)
		x = 6 * pow(4, n // 2 - 1, mod) - 1
		y = p * x - q
		a = [1, p, q]
		while len(a) <= k + 2:
			a += [x * a[-1] - y * a[-2]]
			a[-1] = a[-1] % mod
		print(a[k] % mod)


from sys import stdin, stdout
m = 1000000007
twotothe = [1]
facts = [1]
for i in range(1, 200001):
	facts.append(facts[-1] * i % m)
	twotothe.append(twotothe[-1] * 2 % m)
invnums = [0] * 200001
invfacts = [0] * 200001
invnums[0] = 1
invnums[1] = 1
for i in range(2, 200001):
	invnums[i] = invnums[m % i] * (m - m // i) % m
invfacts[0] = 1
invfacts[1] = 1
for i in range(2, 200001):
	invfacts[i] = invnums[i] * invfacts[i - 1] % m

def comb(n, r):
	return facts[n] * invfacts[n - r] * invfacts[r] % m
for _ in range(int(stdin.readline())):
	(n, k) = map(int, stdin.readline().split())
	if k == 0:
		stdout.write('1\n')
		continue
	sm = sum((comb(n, r) for r in range(0, n, 2))) % m
	if n & 1:
		stdout.write(str(pow(sm + 1, k, m)) + '\n')
		continue
	ans = 1
	last = 1
	for i in range(k):
		ans = (last + sm * ans) % m
		last = last * twotothe[n] % m
	stdout.write(str(ans) + '\n')


T = int(input())
for _ in range(T):
	(n, k) = map(int, input().split())
	p = 10 ** 9 + 7
	if n & 1 == 1:
		answer = pow(pow(2, n - 1, p) + 1, k, p)
	else:
		answer = 1
		pow_ = 1
		_2_n_1 = pow(2, n - 1, p)
		for i in range(k):
			answer = answer * (_2_n_1 - 1) % p
			answer = (answer + pow_) % p
			pow_ = pow_ * _2_n_1 * 2 % p
	print(answer)


M = 10 ** 9 + 7

def mul(a, b):
	a %= M
	b %= M - 1
	k = 1
	s = bin(b)[2:]
	for x in s:
		k = k * k % M
		if x == '1':
			k = k * a % M
	return k

def sex(n, k):
	if k == 0:
		return 1
	p = mul(2, n - 1)
	if n % 2 == 1:
		return mul(p + 1, k)
	x = [0] * (k + 1)
	x[0] = 1
	for i in range(1, k + 1):
		x[i] = (p - 1) * x[i - 1] + mul(2 * p, i - 1)
		x[i] %= M
	return x[k]
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	print(sex(n, k))


for s in [*open(0)][1:]:
	M = 10 ** 9 + 7
	P = pow
	(n, k) = map(int, s.split())
	p = P(2, n - 1, M)
	print([(P(2 * p, k, M) + p * P(~-p, k, M)) * P(p + 1, -1, M) % M, P(p + 1, k, M)][n & 1])


real_ans = 0

def abc(x, n, k):
	global real_ans
	if len(x) == n:
		a = x[0]
		b = x[0]
		for j in x[1:]:
			a &= j
			b ^= j
		if a >= b:
			real_ans += 1
		return
	for j in range(2 ** k):
		abc(x + [j], n, k)
mod = 10 ** 9 + 7
e = 2 * 10 ** 5 + 1
fact = [1] * e
for j in range(1, e):
	fact[j] = j * fact[j - 1] % mod

def ncr(a, b):
	if a <= 0 or a < b:
		return 0
	x = fact[a]
	y = pow(fact[b] * fact[a - b], mod - 2, mod)
	return x * y % mod
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	if k == 0:
		print(1)
	else:
		b = pow(2, n - 1, mod)
		d = 1
		e = pow(2, n, mod)
		ans = 1
		for j in range(k):
			y = ans
			if n % 2:
				ans = (ans + y) % mod
			else:
				ans = (ans + d) % mod
			ans = (ans + b * y - y - y * (1 if n % 2 == 0 else 0)) % mod
			d = d * e % mod
		print(ans % mod)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	tmp1 = 2 ** (n - 1) % 1000000007
	tmp2 = 1
	ans = 0
	if k == 0:
		ans = 1
	elif k >= 1:
		if n % 2 == 0:
			ans = 2 ** (n - 1) % 1000000007
		else:
			ans = (2 ** (n - 1) + 1) % 1000000007
	for i in range(2, k + 1):
		tmp2 = tmp2 * tmp1 * 2 % 1000000007
		if n % 2 == 0:
			ans = (tmp2 + (tmp1 - 1) * ans) % 1000000007
		else:
			ans = (tmp1 + 1) * ans % 1000000007
	if n == 1:
		ans = 2 ** k % 1000000007
	print(ans)


t = int(input())
pow2 = [1 for x in range(2 * 100000 + 1)]
mod = 10 ** 9 + 7
for i in range(1, 200000 + 1):
	pow2[i] = pow2[i - 1] * 2
	pow2[i] %= mod

def solve(k, n):
	if k == 0:
		return 1
	if dp[k] != -1:
		return dp[k]
	if n % 2 == 0:
		ans = pow22[k - 1] - solve(k - 1, n)
		ans += solve(k - 1, n) * pow2[n - 1]
		ans %= mod
	else:
		ans = solve(k - 1, n)
		ans += solve(k - 1, n) * pow2[n - 1]
		ans %= mod
	dp[k] = ans
	return ans
while t:
	t -= 1
	(n, k) = [int(x) for x in input().split()]
	pow22 = [1 for x in range(k + 1)]
	for i in range(1, k + 1):
		pow22[i] = pow22[i - 1] * pow2[n]
		pow22[i] %= mod
	if k == 0:
		print(1)
		continue
	dp = [-1 for x in range(k + 1)]
	for i in range(1, k):
		solve(i, n)
	print(solve(k, n))


p = 10 ** 9 + 7

def power(x, y, p):
	b = bin(y)[2:]
	start = x % p
	answer = 1
	for i in range(len(b)):
		if b[len(b) - 1 - i] == '1':
			answer = answer * start % p
		start = start * start % p
	return answer

def invert(x, p):
	return power(x, p - 2, p)

def process(n, k):
	a1 = power(2, n * k, p)
	if n % 2 == 0:
		a2 = power(2, n - 1, p) % p
		a3 = (a2 - 1) % p
		R = (invert(2, p) - invert(power(2, n, p), p)) % p
		num1 = (power(R, k + 1, p) - R) % p
		den1 = (R - 1) % p
		num = a2 * a1 * num1 % p
		den = a3 * den1 % p
		entry = num * invert(den, p) % p
		return (a1 - entry) % p
	else:
		a2 = (power(2, n - 1, p) - 1) % p
		a3 = (a2 + 2) % p
		R = (invert(2, p) + invert(power(2, n, p), p)) % p
		num1 = (power(R, k + 1, p) - R) % p
		den1 = (R - 1) % p
		num = a2 * a1 * num1 % p
		den = a3 * den1 % p
		entry = num * invert(den, p) % p
		return (a1 - entry) % p
t = int(input())
for i in range(t):
	(n, k) = [int(x) for x in input().split()]
	print(process(n, k))


from collections import Counter
import string
import math
import bisect
import sys
from fractions import Fraction

def modDivide(a, b, m):
	inv = pow(b, m - 2, m)
	return inv * a % m

def array_int():
	return [int(i) for i in sys.stdin.readline().split()]

def vary(arrber_of_variables):
	if arrber_of_variables == 1:
		return int(sys.stdin.readline())
	if arrber_of_variables >= 2:
		return map(int, sys.stdin.readline().split())

def makedict(var):
	return dict(Counter(var))
testcases = vary(1)
for _ in range(testcases):
	(n, k) = vary(2)
	mod = 10 ** 9 + 7
	if k == 0:
		print(1)
		continue
	if n % 2 == 1:
		print(pow(1 + pow(2, n - 1, mod), k, mod))
	else:
		t = pow(pow(2, n - 1, mod) - 1, k, mod)
		a = pow(2, n * k, mod)
		b = (pow(2, n - 1, mod) + 1) % mod
		a = modDivide((a - t + mod) % mod, b, mod)
		t = (t + a) % mod
		print(t)


import sys
from math import gcd
input = sys.stdin.readline
mod = 10 ** 9 + 7
t = int(input())
for _ in range(t):
	(n, k) = list(map(int, input().split()))
	w0 = 1
	pow_n_low = 1
	for _ in range(n - 1):
		pow_n_low *= 2
		pow_n_low %= mod
	pow_n = pow_n_low * 2 % mod
	ans = w0
	pow_n_k_low = 1
	for i in range(1, k + 1):
		if n % 2 == 0:
			ans = ans * (pow_n_low - 1) + pow_n_k_low
			ans %= mod
			pow_n_k_low *= pow_n
			pow_n_k_low %= mod
		if n % 2 == 1:
			ans = ans * (pow_n_low + 1)
			ans %= mod
	print(ans)


def func():
	t = int(input().strip())
	cases = []
	for _ in range(t):
		(n, k) = map(int, input().strip().split())
		cases.append((n, k))
	for case in cases:
		(n, k) = case
		print(and_xor(n, k))

def and_xor(n, k):
	mod = 1000000007
	if n % 2:
		ans = pow(2, n - 1, mod) + 1
		return pow(ans, k, mod)
	if k == 0:
		return 1
	tmp = pow(2, n - 1, mod) - 1
	ans = tmp + 1
	res = cnt = pow(2, n, mod)
	for i in range(1, k):
		ans = (ans * tmp % mod + res) % mod
		res = res * cnt % mod
		ans %= mod
	return ans
func()


MOD = 10 ** 9 + 7
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	COEFF_WINS = 2 ** n % MOD
	COEFF_Q = 2 ** (n - 1) % MOD
	wins = 0
	q = 1
	for i in range(k):
		wins *= COEFF_WINS
		wins %= MOD
		if n % 2 == 0:
			wins += q
			q *= COEFF_Q - 1
		else:
			q *= COEFF_Q + 1
		q %= MOD
	wins += q
	print(wins % MOD)


mod = 10 ** 9 + 7
powers = [1]
for i in range(1, 200000 + 1):
	powers.append(powers[-1] * 2 % mod)
for nt in range(int(input())):
	(n, k) = map(int, input().split())
	add = [1]
	for i in range(k):
		add.append(add[-1] * powers[n] % mod)
	if n % 2:
		ans = pow(2, n * k, mod)
		for i in range(k):
			ans -= pow(powers[n - 1] + 1, i, mod) * (powers[n - 1] - 1) % mod * add[k - i - 1] % mod
			ans = ans % mod
		print(ans)
	else:
		ans = pow(2, n * k, mod)
		for i in range(k):
			ans -= pow(powers[n - 1] - 1, i, mod) * powers[n - 1] % mod * add[k - i - 1] % mod
			ans = ans % mod
		print(ans)


mod = 10 ** 9 + 7
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	total = pow(2, n, mod)
	h = pow(2, n - 1, mod)
	if k == 0:
		print(1)
		continue
	if n % 2 == 0:
		c = 0
		t = 1
		p = {}
		prev = 1
		for i in range(k + 1):
			p[i] = prev
			prev = prev * total % mod
		for i in range(k):
			c += t * p[k - i - 1]
			c %= mod
			t = t * (h - 1) % mod
		c += t
		c %= mod
		print(c)
	else:
		print(pow(h + 1, k, mod))


mod = 10 ** 9 + 7

def odd(k):
	if k == 0:
		return 1
	else:
		oddd = [1 for _ in range(k + 1)]
		for a in range(k, 0, -1):
			if a == k:
				oddd[a] = (tno + 1) % mod
			else:
				oddd[a] = (tno + 1) * oddd[a + 1] % mod
		return oddd[1]

def even(k):
	if k == 0:
		return 1
	else:
		eveen = [1 for _ in range(k + 1)]
		for a in range(k, 0, -1):
			if a == k:
				eveen[a] = tno
			else:
				eveen[a] = (tro[a] + (tno - 1) * eveen[a + 1]) % mod
		return eveen[1]
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	tno = 2 ** (n - 1) % mod
	tnt = 2 * tno % mod
	tro = [0 for _ in range(k + 1)]
	pip = 1
	for a in range(k, 0, -1):
		tro[a] = pip
		pip = pip * tnt % mod
	if n % 2 != 0:
		print(odd(k))
	else:
		print(even(k))


import sys
from sys import stdout
input = lambda : sys.stdin.readline().strip()
P = lambda : list(map(int, input().split()))
from math import factorial as f, gcd, ceil
from collections import deque, defaultdict as dd, Counter as C
from heapq import heapify, heappop, heappush, heappushpop, heapreplace, merge
from random import randint, choice, sample
from operator import itemgetter as ig, attrgetter as ag, methodcaller as mc
import time
mod = 10 ** 9 + 7
a = ord('a')

class FT:

	def __init__(self, N):
		self.ft = [0] * (N + 1)
		self.N = N

	def ls(self, x):
		return x & -x

	def fenwick_update(self, p, v):
		while p <= self.N:
			self.ft[p] += v
			p += self.ls(p)

	def fenwick_query(self, p):
		s = 0
		while p:
			s += self.ft[p]
			p -= self.ls(p)
		return s
start = time.time()

def fast_exp(x, exp):
	ans = 1
	base = x
	while exp:
		if exp & 1:
			ans *= base
		base *= base
		base %= mod
		ans %= mod
		exp >>= 1
	return ans

def countBits(n):
	count = 0
	while n:
		count += n & 1
		n >>= 1
	return count

def submasks(n):
	org = n
	while n:
		yield n
		n = n - 1 & org

def solve():
	(n, k) = P()
	if k == 0:
		print(1)
	elif n % 2:
		print(fast_exp(fast_exp(2, n - 1) + 1, k))
	else:
		z = fast_exp(2, n - 1) - 1
		z1 = fast_exp(2, n)
		ans = 0
		right = [1] * k
		for i in range(k - 2, -1, -1):
			right[i] = right[i + 1] * z1 % mod
		left = 1
		for i in range(k):
			ans = (ans + left * right[i]) % mod
			left = left * z % mod
		print((ans + fast_exp(z, k)) % mod)
tc = int(input())
for t in range(1, tc + 1):
	solve()


import queue
from math import *
import sys
from collections import *
from random import *
sys.setrecursionlimit(99999)
eps = sys.float_info.epsilon
P = 31
MOD = 10 ** 9 + 7

def is_prime(n):
	if n == 0 or n == 1:
		return False
	d = 2
	while d * d <= n:
		if n % d == 0:
			return False
		d += 1
	return True

def div_up(n, k):
	if n % k == 0:
		return n // k
	else:
		return n // k + 1

def bfs(start, visited, graph):
	q = deque()
	visited[start] = True
	q.appendleft(start)
	while len(q) != 0:
		v = q.pop()
		for to in graph[v]:
			if not visited[to]:
				visited[to] = True
				q.appendleft(to)

def to_int(c):
	if c == '>':
		return 0
	return 1

def ford_bellman(edges, d, cost, n):
	for i in range(n - 1):
		flag = True
		for edge in edges:
			(v, u) = (edge[0], edge[1])
			temp = d[v] + cost[edge]
			if temp < d[u]:
				d[u] = temp
				flag = False
		if flag:
			break

def num_len(n, base):
	if n == 0:
		return 1
	return int(floor(log(n, base) + 1))
cycles = 0

def dfs(graph, cl, p, v):
	global cycles
	cl[v] = 1
	for to in graph[v]:
		if cl[to] == 1 and p[v] != to:
			cycles += 1
		elif cl[to] == 0:
			p[to] = v
			dfs(graph, cl, p, to)
	cl[v] = 2

def down(a):
	for i in range(1, len(a)):
		if a[i] > a[i - 1]:
			return False
	return True

def up(a):
	for i in range(1, len(a)):
		if a[i] < a[i - 1]:
			return False
	return True

def _hash_(s):
	res = 0
	for i in range(len(s)):
		res += (ord(s[i]) - ord('a')) * P ** i
	return res

def binpow(a, n):
	res = 1
	while n:
		if n & 1:
			res *= a
			res %= MOD
		a *= a
		a %= MOD
		n >>= 1
	return res

def solve():
	(n, k) = map(int, input().split())
	S = binpow(2, n - 1)
	if k == 0:
		print(1)
		return
	eq = S
	if n % 2 != 0:
		eq += 1
	else:
		eq -= 1
	prev = 0
	if n % 2 == 0:
		prev += 1
	dp_big_1 = prev
	x = binpow(2, n)
	y = eq
	for i in range(2, k + 1):
		prev = (prev * x + y * dp_big_1) % MOD
		y = y * eq % MOD
	print((binpow(eq, k) + prev) % MOD)
for _ in range(int(input())):
	solve()

def debug():
	pass


import os, math
import sys
from io import BytesIO, IOBase

def main():
	mod = 10 ** 9 + 7
	mv = 2 * 10 ** 5
	pre = []
	v = 1
	for i in range(mv + 1):
		pre.append(v)
		v = v * 2 % mod
	T = int(input())
	for _ in range(T):
		(n, k) = map(int, input().split())
		if k == 0:
			print(1)
		elif n % 2 != 0:
			ans = (pre[n - 1] + 1) % mod
			ans = pow(ans, k, mod)
			print(ans % mod)
		else:
			val = pre[n - 1]
			ans = val
			rm = 1
			for i in range(k - 1):
				rm = rm * pre[n] % mod
				ans = ((val - 1) * ans % mod + rm) % mod
			print(ans % 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')
main()


import sys
import io
import math
import collections
import decimal
import itertools
import bisect
import heapq

def input():
	return sys.stdin.readline()[:-1]
INF = 10 ** 10
MOD = 1000000007

def solve(N, K):
	if K == 0:
		return 1
	D = 0
	for i in range(0, N, 2):
		D = (D + comb(N, i)) % MOD
	if N % 2 == 1:
		ans = pow(D + 1, K, MOD)
		return ans
	else:
		D_inv = pow(D, -1 + (MOD - 1), MOD)
		n_any = pow(2, N, MOD)
		v = pow(D, K, MOD)
		ans = v
		v = v * D_inv % MOD
		ans = (ans + v) % MOD
		for _ in range(K - 1):
			v = v * D_inv * n_any % MOD
			ans = (ans + v) % MOD
		return ans
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]

def comb(n, r):
	r = min(r, n - r)
	return fact[n] * factinv[r] * factinv[n - r] % MOD
N_MAX = 2 * 10 ** 5
for i in range(2, N_MAX + 1):
	fact.append(fact[-1] * i % MOD)
	inv.append(-inv[MOD % i] * (MOD // i) % MOD)
	factinv.append(factinv[-1] * inv[-1] % MOD)
T0 = int(input())
for _ in range(T0):
	(N, K) = map(int, input().split())
	print(solve(N, K))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	mod = int(1000000000.0 + 7)
	p = pow(2, n - 1, mod)
	b = 1
	c = 1
	if n % 2 == 0:
		b = p
	else:
		b = p + 1
	m = 2 * p % mod
	for i in range(2, k + 1):
		c = c * m % mod
		if n % 2 == 0:
			b = (c + (p - 1) * b) % mod
		else:
			b = (p + 1) * b % mod
	if k == 0:
		print(1)
	else:
		print(b)


ali = 0
from collections import defaultdict, Counter, deque
ali = 0
ali = 0
ali = 0
from math import sqrt, log10, log, floor, factorial, gcd
ali = 0
ali = 0
ali = 0
from bisect import bisect_left, bisect_right
ali = 0
ali = 0
ali = 0
from itertools import permutations, combinations
ali = 0
ali = 0
ali = 0
import sys, io, os
ali = 0
ali = 0
ali = 0
input = sys.stdin.readline
ali = 0
ali = 0
ali = 0
ali = 0
ali = 0
ali = 0
ali = 0
inf = float('inf')
ali = 0
ali = 0
ali = 0
mod = 10 ** 9 + 7
ali = 0
ali = 0

def get_list():
	return [int(i) for i in input().split()]
	ali = 0
ali = 0

def yn(a):
	print('YES' if a else 'NO')
	ali = 0
ali = 0
ali = 0
ceil = lambda a, b: (a + b - 1) // b
ali = 0
ali = 0
ali = 0
t = int(input())
ali = 0
ali = 0
for i in range(t):
	ali = 0
	(n, k) = [int(i) for i in input().split()]
	ali = 0
	ali = 0
	ali = 0
	if n % 2 == 0:
		ali = 0
		p = pow(2, n - 1, mod)
		ali = 0
		ali = 0
		ali = 0
		pp = pow(2, n, mod)
		ali = 0
		ali = 0
		ali = 0
		ans = 0
		ali = 0
		ali = 0
		for i in range(k):
			ali = 0
			ali = 0
			ali = 0
			u = pow((p - 1 + mod) % mod, k - i - 1, mod) * pow(pp, i, mod) % mod
			ali = 0
			ali = 0
			ali = 0
			ans = (ans + u) % mod
			ali = 0
			ali = 0
		ali = 0
		ans = ans + pow((p - 1 + mod) % mod, k, mod)
		ali = 0
		ali = 0
		ali = 0
		ans %= mod
		ali = 0
		ali = 0
		ali = 0
		print(ans)
		ali = 0
		ali = 0
	else:
		ali = 0
		p = pow(2, n - 1, mod)
		ali = 0
		ali = 0
		ali = 0
		pp = pow(2, n, mod)
		ali = 0
		ali = 0
		ali = 0
		ans = 0
		ali = 0
		ali = 0
		for i in range(k):
			ali = 0
			ali = 0
			ali = 0
			u = pow(p, k - i - 1, mod) * pow((p + 1) % mod, i, mod) % mod
			ali = 0
			ali = 0
			ali = 0
			ans = (ans + u) % mod
			ali = 0
			ali = 0
		ali = 0
		ans = ans + pow(p, k, mod)
		ali = 0
		ali = 0
		ali = 0
		ans %= mod
		ali = 0
		ali = 0
		ali = 0
		print(ans)
		ali = 0
		ali = 0


import sys
input = sys.stdin.readline

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

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

def mps(A):
	return [tuple(map(int, input().split())) for _ in range(A)]
import math
import bisect
from copy import deepcopy as dc
from itertools import accumulate
from collections import Counter, defaultdict, deque

def ceil(U, V):
	return (U + V - 1) // V

def modf1(N, MOD):
	return (N - 1) % MOD + 1
inf = int(1e+20)
mod = int(1000000000.0 + 7)
t = int(input())
for _ in range(t):
	(n, k) = mp()
	if k == 0:
		print(1)
		continue
	if n % 2 == 1:
		ans = 1
		for i in range(k):
			ans *= pow(2, n - 1, mod) + 1
			ans %= mod
	else:
		ans = 0
		u = pow(2, n, mod)
		v = pow(2, n - 1, mod) - 1
		for i in range(k):
			ans += pow(u, k - i - 1, mod) * pow(v, i, mod)
			ans %= mod
		ans += pow(v, k, mod)
	print(ans % mod)


import sys
input = sys.stdin.readline

def main():
	MOD = 10 ** 9 + 7
	t = int(input())
	for _ in range(t):
		(N, K) = [int(x) for x in input().split()]
		ans = 0
		if N % 2 == 1:
			ans += pow(pow(2, N - 1, MOD) + 1, K, MOD)
			print(ans)
			continue
		for i in range(K):
			ans += pow(pow(2, N - 1, MOD) - 1, i, MOD) * pow(pow(2, N, MOD), K - i - 1, MOD)
			ans %= MOD
		ans += pow(pow(2, N - 1, MOD) - 1, K, MOD)
		ans %= MOD
		print(ans % MOD)
main()


p = int(1000000000.0 + 7)

def sol(n, k):
	o = n % 2
	b = (1 << n - 1) % p
	tn = (b << 1) % p
	kn = 1
	c = 1
	for i in range(1, k + 1):
		c = (c * b + c) % p if o else (c * b + kn - c) % p
		kn = kn * tn % p
	return c
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	print(sol(n, k))


try:
	import sys
	from functools import lru_cache, cmp_to_key
	from heapq import merge, heapify, heappop, heappush
	from collections import defaultdict as dd, deque, Counter as C
	from itertools import combinations as comb, permutations as perm
	from bisect import bisect_left as bl, bisect_right as br, bisect, insort
	from time import perf_counter
	from fractions import Fraction
	import copy
	from copy import deepcopy
	import time
	starttime = time.time()
	mod = int(pow(10, 9) + 7)
	mod2 = 998244353

	def data():
		return sys.stdin.readline().strip()

	def out(*var, end='\n'):
		sys.stdout.write(' '.join(map(str, var)) + end)

	def L():
		return list(sp())

	def sl():
		return list(ssp())

	def sp():
		return map(int, data().split())

	def ssp():
		return map(str, data().split())

	def l1d(n, val=0):
		return [val for i in range(n)]

	def l2d(n, m, val=0):
		return [l1d(n, val) for j in range(m)]
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
except:
	pass
MOD = 10 ** 9 + 7
for _ in range(L()[0]):
	(n, k) = L()
	ans = 1
	if n % 2:
		ans = pow(1 + pow(2, n - 1, MOD), k, MOD)
		print(ans)
	else:
		for i in range(1, k + 1):
			ans = pow(pow(2, i - 1, MOD), n, MOD) + (pow(2, n - 1, MOD) - 1) * ans
			ans %= MOD
		print(ans)


import sys
readline = sys.stdin.readline
M = 10 ** 9 + 7

def bin_exp(num, k):
	ans = 1
	num %= M
	while k > 0:
		if k % 2 == 1:
			ans *= num
			ans %= M
		num *= num
		num %= M
		k //= 2
	return ans
t = int(readline())
for _ in range(t):
	(n, k) = map(int, readline().split())
	if k == 0:
		print(1)
		continue
	two_n_1 = bin_exp(2, n - 1)
	if n % 2 == 1:
		two_n_1 = (two_n_1 + 1) % M
		print(bin_exp(two_n_1, k) % M)
	else:
		dp = [0] * k
		dp[0] = two_n_1
		two_n = 2 * two_n_1 % M
		two_n_1 -= 1
		if two_n_1 < 0:
			two_n_1 += M
		two_n_k = 1
		for i in range(1, k):
			dp[i] = dp[i - 1] * two_n_1 % M
			two_n_k *= two_n
			two_n_k %= M
			dp[i] += two_n_k
			dp[i] %= M
		print(dp[k - 1] % M)


import sys
input = sys.stdin.readline
MOD = 10 ** 9 + 7

def main():
	(n, k) = map(int, input().split())
	if k == 0:
		print(1)
		return
	if n == 1:
		print(pow(2, k, MOD))
		return
	if n % 2 == 1:
		print(pow(pow(2, n - 1, MOD) + 1, k, MOD))
	else:
		ans = pow(pow(2, n - 1, MOD) - 1, k, MOD)
		for i in range(k):
			ans += pow(pow(2, n - 1, MOD) - 1, i, MOD) * pow(pow(2, n, MOD), k - 1 - i, MOD)
			ans %= MOD
		print(ans)
for _ in range(int(input())):
	main()


import os
import sys
import math
from io import BytesIO, IOBase
import io
from fractions import Fraction
import collections
from itertools import permutations
from collections import defaultdict
from collections import deque
from collections import Counter
import threading
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')

class SegmentTree:

	def __init__(self, data, default=0, func=lambda a, b: math.gcd(a, b)):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class SegmentTree1:

	def __init__(self, data, default=0, func=lambda a, b: a + b):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)
MOD = 10 ** 9 + 7

class Factorial:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorials = [1, 1]
		self.invModulos = [0, 1]
		self.invFactorial_ = [1, 1]

	def calc(self, n):
		if n <= -1:
			print('Invalid argument to calculate n!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.factorials):
			return self.factorials[n]
		nextArr = [0] * (n + 1 - len(self.factorials))
		initialI = len(self.factorials)
		prev = self.factorials[-1]
		m = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * i % m
		self.factorials += nextArr
		return self.factorials[n]

	def inv(self, n):
		if n <= -1:
			print('Invalid argument to calculate n^(-1)')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		p = self.MOD
		pi = n % p
		if pi < len(self.invModulos):
			return self.invModulos[pi]
		nextArr = [0] * (n + 1 - len(self.invModulos))
		initialI = len(self.invModulos)
		for i in range(initialI, min(p, n + 1)):
			next = -self.invModulos[p % i] * (p // i) % p
			self.invModulos.append(next)
		return self.invModulos[pi]

	def invFactorial(self, n):
		if n <= -1:
			print('Invalid argument to calculate (n^(-1))!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.invFactorial_):
			return self.invFactorial_[n]
		self.inv(n)
		nextArr = [0] * (n + 1 - len(self.invFactorial_))
		initialI = len(self.invFactorial_)
		prev = self.invFactorial_[-1]
		p = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p
		self.invFactorial_ += nextArr
		return self.invFactorial_[n]

class Combination:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorial = Factorial(MOD)

	def ncr(self, n, k):
		if k < 0 or n < k:
			return 0
		k = min(k, n - k)
		f = self.factorial
		return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD
mod = 10 ** 9 + 7
omod = 998244353
prime = [True for i in range(11)]
prime[0] = prime[1] = False

def SieveOfEratosthenes(n=10):
	p = 2
	c = 0
	while p <= n:
		if prime[p] == True:
			c += 1
			for i in range(p, n + 1, p):
				prime[i] = False
		p += 1

class DSU:

	def __init__(self, R, C):
		self.par = range(R * C + 1)
		self.rnk = [0] * (R * C + 1)
		self.sz = [1] * (R * C + 1)

	def find(self, x):
		if self.par[x] != x:
			self.par[x] = self.find(self.par[x])
		return self.par[x]

	def union(self, x, y):
		(xr, yr) = (self.find(x), self.find(y))
		if xr == yr:
			return
		if self.rnk[xr] < self.rnk[yr]:
			(xr, yr) = (yr, xr)
		if self.rnk[xr] == self.rnk[yr]:
			self.rnk[xr] += 1
		self.par[yr] = xr
		self.sz[xr] += self.sz[yr]

	def size(self, x):
		return self.sz[self.find(x)]

	def top(self):
		return self.size(len(self.sz) - 1) - 1

class LazySegTree:

	def __init__(self, _op, _e, _mapping, _composition, _id, v):

		def set(p, x):
			assert 0 <= p < _n
			p += _size
			for i in range(_log, 0, -1):
				_push(p >> i)
			_d[p] = x
			for i in range(1, _log + 1):
				_update(p >> i)

		def get(p):
			assert 0 <= p < _n
			p += _size
			for i in range(_log, 0, -1):
				_push(p >> i)
			return _d[p]

		def prod(l, r):
			assert 0 <= l <= r <= _n
			if l == r:
				return _e
			l += _size
			r += _size
			for i in range(_log, 0, -1):
				if l >> i << i != l:
					_push(l >> i)
				if r >> i << i != r:
					_push(r >> i)
			sml = _e
			smr = _e
			while l < r:
				if l & 1:
					sml = _op(sml, _d[l])
					l += 1
				if r & 1:
					r -= 1
					smr = _op(_d[r], smr)
				l >>= 1
				r >>= 1
			return _op(sml, smr)

		def apply(l, r, f):
			assert 0 <= l <= r <= _n
			if l == r:
				return
			l += _size
			r += _size
			for i in range(_log, 0, -1):
				if l >> i << i != l:
					_push(l >> i)
				if r >> i << i != r:
					_push(r - 1 >> i)
			l2 = l
			r2 = r
			while l < r:
				if l & 1:
					_all_apply(l, f)
					l += 1
				if r & 1:
					r -= 1
					_all_apply(r, f)
				l >>= 1
				r >>= 1
			l = l2
			r = r2
			for i in range(1, _log + 1):
				if l >> i << i != l:
					_update(l >> i)
				if r >> i << i != r:
					_update(r - 1 >> i)

		def _update(k):
			_d[k] = _op(_d[2 * k], _d[2 * k + 1])

		def _all_apply(k, f):
			_d[k] = _mapping(f, _d[k])
			if k < _size:
				_lz[k] = _composition(f, _lz[k])

		def _push(k):
			_all_apply(2 * k, _lz[k])
			_all_apply(2 * k + 1, _lz[k])
			_lz[k] = _id
		_n = len(v)
		_log = _n.bit_length()
		_size = 1 << _log
		_d = [_e] * (2 * _size)
		_lz = [_id] * _size
		for i in range(_n):
			_d[_size + i] = v[i]
		for i in range(_size - 1, 0, -1):
			_update(i)
		self.set = set
		self.get = get
		self.prod = prod
		self.apply = apply
MIL = 1 << 20

def makeNode(total, count):
	return total * MIL + count

def getTotal(node):
	return math.floor(node / MIL)

def getCount(node):
	return node - getTotal(node) * MIL
nodeIdentity = makeNode(0.0, 0.0)

def nodeOp(node1, node2):
	return node1 + node2
	return makeNode(getTotal(node1) + getTotal(node2), getCount(node1) + getCount(node2))
identityMapping = -1

def mapping(tag, node):
	if tag == identityMapping:
		return node
	count = getCount(node)
	return makeNode(tag * count, count)

def composition(mapping1, mapping2):
	return mapping1 if mapping1 != identityMapping else mapping2

def memodict(f):

	class memodict(dict):

		def __missing__(self, key):
			ret = self[key] = f(key)
			return ret
	return memodict().__getitem__

def pollard_rho(n):
	if n & 1 == 0:
		return 2
	if n % 3 == 0:
		return 3
	s = (n - 1 & 1 - n).bit_length() - 1
	d = n >> s
	for a in [2, 325, 9375, 28178, 450775, 9780504, 1795265022]:
		p = pow(a, d, n)
		if p == 1 or p == n - 1 or a % n == 0:
			continue
		for _ in range(s):
			prev = p
			p = p * p % n
			if p == 1:
				return math.gcd(prev - 1, n)
			if p == n - 1:
				break
		else:
			for i in range(2, n):
				(x, y) = (i, (i * i + 1) % n)
				f = math.gcd(abs(x - y), n)
				while f == 1:
					(x, y) = ((x * x + 1) % n, (y * y + 1) % n)
					y = (y * y + 1) % n
					f = math.gcd(abs(x - y), n)
				if f != n:
					return f
	return n

@memodict
def prime_factors(n):
	if n <= 1:
		return Counter()
	f = pollard_rho(n)
	return Counter([n]) if f == n else prime_factors(f) + prime_factors(n // f)

def distinct_factors(n):
	factors = [1]
	for (p, exp) in prime_factors(n).items():
		factors += [p ** i * factor for factor in factors for i in range(1, exp + 1)]
	return factors

def all_factors(n):
	(small, large) = ([], [])
	for i in range(1, int(n ** 0.5) + 1, 2 if n & 1 else 1):
		if not n % i:
			small.append(i)
			large.append(n // i)
	if small[-1] == large[-1]:
		large.pop()
	large.reverse()
	small.extend(large)
	return small

def binarySearch(arr, n, key):
	left = 0
	right = n - 1
	mid = 0
	res = n
	while left <= right:
		mid = (right + left) // 2
		if arr[mid] > key:
			res = mid
			right = mid - 1
		else:
			left = mid + 1
	return res

def binarySearch1(arr, n, key):
	left = 0
	right = n - 1
	mid = 0
	res = -1
	while left <= right:
		mid = (right + left) // 2
		if arr[mid] > key:
			right = mid - 1
		else:
			res = mid
			left = mid + 1
	return res
t = 1
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	if k == 0:
		print(1)
	elif n % 2 == 0:
		c1 = pow(2, n - 1, mod) - 1
		c1 %= mod
		a = 1
		c2 = pow(2, n, mod)
		ans = 0
		for i in range(k):
			b = pow(c2, k - i - 1, mod)
			ans += a * b % mod
			a = a * c1 % mod
		ans = (ans + a) % mod
		print(ans)
	else:
		p = pow(2, n - 1, mod) + 1
		p %= mod
		r = pow(p, k, mod)
		print(r)


def divisors(M):
	d = []
	i = 1
	while M >= i ** 2:
		if M % i == 0:
			d.append(i)
			if i ** 2 != M:
				d.append(M // i)
		i = i + 1
	return d

def popcount(x):
	x = x - (x >> 1 & 1431655765)
	x = (x & 858993459) + (x >> 2 & 858993459)
	x = x + (x >> 4) & 252645135
	x = x + (x >> 8)
	x = x + (x >> 16)
	return x & 127

def eratosthenes(n):
	res = [0 for i in range(n + 1)]
	prime = set([])
	for i in range(2, n + 1):
		if not res[i]:
			prime.add(i)
			for j in range(1, n // i + 1):
				res[i * j] = 1
	return prime

def factorization(n):
	res = []
	for p in prime:
		if n % p == 0:
			while n % p == 0:
				n //= p
			res.append(p)
	if n != 1:
		res.append(n)
	return res

def euler_phi(n):
	res = n
	for x in range(2, n + 1):
		if x ** 2 > n:
			break
		if n % x == 0:
			res = res // x * (x - 1)
			while n % x == 0:
				n //= x
	if n != 1:
		res = res // n * (n - 1)
	return res

def ind(b, n):
	res = 0
	while n % b == 0:
		res += 1
		n //= b
	return res

def isPrimeMR(n):
	d = n - 1
	d = d // (d & -d)
	L = [2, 3, 5, 7, 11, 13, 17]
	for a in L:
		t = d
		y = pow(a, t, n)
		if y == 1:
			continue
		while y != n - 1:
			y = y * y % n
			if y == 1 or t == n - 1:
				return 0
			t <<= 1
	return 1

def findFactorRho(n):
	from math import gcd
	m = 1 << n.bit_length() // 8
	for c in range(1, 99):
		f = lambda x: (x * x + c) % n
		(y, r, q, g) = (2, 1, 1, 1)
		while g == 1:
			x = y
			for i in range(r):
				y = f(y)
			k = 0
			while k < r and g == 1:
				ys = y
				for i in range(min(m, r - k)):
					y = f(y)
					q = q * abs(x - y) % n
				g = gcd(q, n)
				k += m
			r <<= 1
		if g == n:
			g = 1
			while g == 1:
				ys = f(ys)
				g = gcd(abs(x - ys), n)
		if g < n:
			if isPrimeMR(g):
				return g
			elif isPrimeMR(n // g):
				return n // g
			return findFactorRho(g)

def primeFactor(n):
	i = 2
	ret = {}
	rhoFlg = 0
	while i * i <= n:
		k = 0
		while n % i == 0:
			n //= i
			k += 1
		if k:
			ret[i] = k
		i += 1 + i % 2
		if i == 101 and n >= 2 ** 20:
			while n > 1:
				if isPrimeMR(n):
					(ret[n], n) = (1, 1)
				else:
					rhoFlg = 1
					j = findFactorRho(n)
					k = 0
					while n % j == 0:
						n //= j
						k += 1
					ret[j] = k
	if n > 1:
		ret[n] = 1
	if rhoFlg:
		ret = {x: ret[x] for x in sorted(ret)}
	return ret

def divisors(n):
	res = [1]
	prime = primeFactor(n)
	for p in prime:
		newres = []
		for d in res:
			for j in range(prime[p] + 1):
				newres.append(d * p ** j)
		res = newres
	res.sort()
	return res

def xorfactorial(num):
	if num == 0:
		return 0
	elif num == 1:
		return 1
	elif num == 2:
		return 3
	elif num == 3:
		return 0
	else:
		x = baseorder(num)
		return 2 ** x * ((num - 2 ** x + 1) % 2) + function(num - 2 ** x)

def xorconv(n, X, Y):
	if n == 0:
		res = [X[0] * Y[0] % mod]
		return res
	x = [X[i] + X[i + 2 ** (n - 1)] for i in range(2 ** (n - 1))]
	y = [Y[i] + Y[i + 2 ** (n - 1)] for i in range(2 ** (n - 1))]
	z = [X[i] - X[i + 2 ** (n - 1)] for i in range(2 ** (n - 1))]
	w = [Y[i] - Y[i + 2 ** (n - 1)] for i in range(2 ** (n - 1))]
	res1 = xorconv(n - 1, x, y)
	res2 = xorconv(n - 1, z, w)
	former = [(res1[i] + res2[i]) * inv for i in range(2 ** (n - 1))]
	latter = [(res1[i] - res2[i]) * inv for i in range(2 ** (n - 1))]
	former = list(map(lambda x: x % mod, former))
	latter = list(map(lambda x: x % mod, latter))
	return former + latter

def merge_sort(A, B):
	(pos_A, pos_B) = (0, 0)
	(n, m) = (len(A), len(B))
	res = []
	while pos_A < n and pos_B < m:
		(a, b) = (A[pos_A], B[pos_B])
		if a < b:
			res.append(a)
			pos_A += 1
		else:
			res.append(b)
			pos_B += 1
	res += A[pos_A:]
	res += B[pos_B:]
	return res

class UnionFindVerSize:

	def __init__(self, N):
		self._parent = [n for n in range(0, N)]
		self._size = [1] * N
		self.group = N

	def find_root(self, x):
		if self._parent[x] == x:
			return x
		self._parent[x] = self.find_root(self._parent[x])
		stack = [x]
		while self._parent[stack[-1]] != stack[-1]:
			stack.append(self._parent[stack[-1]])
		for v in stack:
			self._parent[v] = stack[-1]
		return self._parent[x]

	def unite(self, x, y):
		gx = self.find_root(x)
		gy = self.find_root(y)
		if gx == gy:
			return
		self.group -= 1
		if self._size[gx] < self._size[gy]:
			self._parent[gx] = gy
			self._size[gy] += self._size[gx]
		else:
			self._parent[gy] = gx
			self._size[gx] += self._size[gy]

	def get_size(self, x):
		return self._size[self.find_root(x)]

	def is_same_group(self, x, y):
		return self.find_root(x) == self.find_root(y)

class WeightedUnionFind:

	def __init__(self, N):
		self.parent = [i for i in range(N)]
		self.size = [1 for i in range(N)]
		self.val = [0 for i in range(N)]
		self.flag = True
		self.edge = [[] for i in range(N)]

	def dfs(self, v, pv):
		stack = [(v, pv)]
		new_parent = self.parent[pv]
		while stack:
			(v, pv) = stack.pop()
			self.parent[v] = new_parent
			for (nv, w) in self.edge[v]:
				if nv != pv:
					self.val[nv] = self.val[v] + w
					stack.append((nv, v))

	def unite(self, x, y, w):
		if not self.flag:
			return
		if self.parent[x] == self.parent[y]:
			self.flag = self.val[x] - self.val[y] == w
			return
		if self.size[self.parent[x]] > self.size[self.parent[y]]:
			self.edge[x].append((y, -w))
			self.edge[y].append((x, w))
			self.size[x] += self.size[y]
			self.val[y] = self.val[x] - w
			self.dfs(y, x)
		else:
			self.edge[x].append((y, -w))
			self.edge[y].append((x, w))
			self.size[y] += self.size[x]
			self.val[x] = self.val[y] + w
			self.dfs(x, y)

class Dijkstra:

	class Edge:

		def __init__(self, _to, _cost):
			self.to = _to
			self.cost = _cost

	def __init__(self, V):
		self.G = [[] for i in range(V)]
		self._E = 0
		self._V = V

	@property
	def E(self):
		return self._E

	@property
	def V(self):
		return self._V

	def add_edge(self, _from, _to, _cost):
		self.G[_from].append(self.Edge(_to, _cost))
		self._E += 1

	def shortest_path(self, s):
		import heapq
		que = []
		d = [10 ** 15] * self.V
		d[s] = 0
		heapq.heappush(que, (0, s))
		while len(que) != 0:
			(cost, v) = heapq.heappop(que)
			if d[v] < cost:
				continue
			for i in range(len(self.G[v])):
				e = self.G[v][i]
				if d[e.to] > d[v] + e.cost:
					d[e.to] = d[v] + e.cost
					heapq.heappush(que, (d[e.to], e.to))
		return d

def Z_algorithm(s):
	N = len(s)
	Z_alg = [0] * N
	Z_alg[0] = N
	i = 1
	j = 0
	while i < N:
		while i + j < N and s[j] == s[i + j]:
			j += 1
		Z_alg[i] = j
		if j == 0:
			i += 1
			continue
		k = 1
		while i + k < N and k + Z_alg[k] < j:
			Z_alg[i + k] = Z_alg[k]
			k += 1
		i += k
		j -= k
	return Z_alg

class BIT:

	def __init__(self, n, mod=0):
		self.BIT = [0] * (n + 1)
		self.num = n
		self.mod = mod

	def query(self, idx):
		res_sum = 0
		mod = self.mod
		while idx > 0:
			res_sum += self.BIT[idx]
			if mod:
				res_sum %= mod
			idx -= idx & -idx
		return res_sum

	def update(self, idx, x):
		mod = self.mod
		while idx <= self.num:
			self.BIT[idx] += x
			if mod:
				self.BIT[idx] %= mod
			idx += idx & -idx
		return

class dancinglink:

	def __init__(self, n, debug=False):
		self.n = n
		self.debug = debug
		self._left = [i - 1 for i in range(n)]
		self._right = [i + 1 for i in range(n)]
		self.exist = [True for i in range(n)]

	def pop(self, k):
		if self.debug:
			assert self.exist[k]
		L = self._left[k]
		R = self._right[k]
		if L != -1:
			if R != self.n:
				(self._right[L], self._left[R]) = (R, L)
			else:
				self._right[L] = self.n
		elif R != self.n:
			self._left[R] = -1
		self.exist[k] = False

	def left(self, idx, k=1):
		if self.debug:
			assert self.exist[idx]
		res = idx
		while k:
			res = self._left[res]
			if res == -1:
				break
			k -= 1
		return res

	def right(self, idx, k=1):
		if self.debug:
			assert self.exist[idx]
		res = idx
		while k:
			res = self._right[res]
			if res == self.n:
				break
			k -= 1
		return res

class SparseTable:

	def __init__(self, A, merge_func, ide_ele):
		N = len(A)
		n = N.bit_length()
		self.table = [[ide_ele for i in range(n)] for i in range(N)]
		self.merge_func = merge_func
		for i in range(N):
			self.table[i][0] = A[i]
		for j in range(1, n):
			for i in range(0, N - 2 ** j + 1):
				f = self.table[i][j - 1]
				s = self.table[i + 2 ** (j - 1)][j - 1]
				self.table[i][j] = self.merge_func(f, s)

	def query(self, s, t):
		b = t - s + 1
		m = b.bit_length() - 1
		return self.merge_func(self.table[s][m], self.table[t - 2 ** m + 1][m])

class BinaryTrie:

	class node:

		def __init__(self, val):
			self.left = None
			self.right = None
			self.max = val

	def __init__(self):
		self.root = self.node(-10 ** 15)

	def append(self, key, val):
		pos = self.root
		for i in range(29, -1, -1):
			pos.max = max(pos.max, val)
			if key >> i & 1:
				if pos.right is None:
					pos.right = self.node(val)
					pos = pos.right
				else:
					pos = pos.right
			elif pos.left is None:
				pos.left = self.node(val)
				pos = pos.left
			else:
				pos = pos.left
		pos.max = max(pos.max, val)

	def search(self, M, xor):
		res = -10 ** 15
		pos = self.root
		for i in range(29, -1, -1):
			if pos is None:
				break
			if M >> i & 1:
				if xor >> i & 1:
					if pos.right:
						res = max(res, pos.right.max)
					pos = pos.left
				else:
					if pos.left:
						res = max(res, pos.left.max)
					pos = pos.right
			elif xor >> i & 1:
				pos = pos.right
			else:
				pos = pos.left
		if pos:
			res = max(res, pos.max)
		return res

def solveequation(edge, ans, n, m):
	x = [0] * m
	used = [False] * n
	for v in range(n):
		if used[v]:
			continue
		y = dfs(v)
		if y != 0:
			return False
	return x

	def dfs(v):
		used[v] = True
		r = ans[v]
		for (to, dire, id) in edge[v]:
			if used[to]:
				continue
			y = dfs(to)
			if dire == -1:
				x[id] = y
			else:
				x[id] = -y
			r += y
		return r

class SegmentTree:

	def __init__(self, init_val, segfunc, ide_ele):
		n = len(init_val)
		self.segfunc = segfunc
		self.ide_ele = ide_ele
		self.num = 1 << (n - 1).bit_length()
		self.tree = [ide_ele] * 2 * self.num
		self.size = n
		for i in range(n):
			self.tree[self.num + i] = init_val[i]
		for i in range(self.num - 1, 0, -1):
			self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

	def update(self, k, x):
		k += self.num
		self.tree[k] = x
		while k > 1:
			self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
			k >>= 1

	def query(self, l, r):
		if r == self.size:
			r = self.num
		res = self.ide_ele
		l += self.num
		r += self.num
		while l < r:
			if l & 1:
				res = self.segfunc(res, self.tree[l])
				l += 1
			if r & 1:
				res = self.segfunc(res, self.tree[r - 1])
			l >>= 1
			r >>= 1
		return res

	def bisect_l(self, l, r, x):
		l += self.num
		r += self.num
		Lmin = -1
		Rmin = -1
		while l < r:
			if l & 1:
				if self.tree[l] <= x and Lmin == -1:
					Lmin = l
				l += 1
			if r & 1:
				if self.tree[r - 1] <= x:
					Rmin = r - 1
			l >>= 1
			r >>= 1
		if Lmin != -1:
			pos = Lmin
			while pos < self.num:
				if self.tree[2 * pos] <= x:
					pos = 2 * pos
				else:
					pos = 2 * pos + 1
			return pos - self.num
		elif Rmin != -1:
			pos = Rmin
			while pos < self.num:
				if self.tree[2 * pos] <= x:
					pos = 2 * pos
				else:
					pos = 2 * pos + 1
			return pos - self.num
		else:
			return -1
import sys, random, bisect
from collections import deque, defaultdict
from heapq import heapify, heappop, heappush
from itertools import permutations
from math import gcd, log
input = lambda : sys.stdin.readline().rstrip()
mi = lambda : map(int, input().split())
li = lambda : list(mi())

def cmb(n, r, mod):
	if r < 0 or r > n:
		return 0
	return g1[n] * g2[r] % mod * g2[n - r] % mod
mod = 10 ** 9 + 7
N = 2 * 10 ** 5
g1 = [1] * (N + 1)
g2 = [1] * (N + 1)
inverse = [1] * (N + 1)
for i in range(2, N + 1):
	g1[i] = g1[i - 1] * i % mod
	inverse[i] = -inverse[mod % i] * (mod // i) % mod
	g2[i] = g2[i - 1] * inverse[i] % mod
inverse[0] = 0
for _ in range(int(input())):
	(N, K) = mi()
	res = pow(pow(2, K, mod), N, mod)
	way = pow(2, N, mod)
	pow_w = [1 for i in range(K)]
	for i in range(1, K):
		pow_w[i] = pow_w[i - 1] * way % mod
	(one, zero, more) = (0, 0, 0)
	if N & 1:
		one = 1
		zero = pow(2, N - 1, mod)
		more = (pow(2, N - 1, mod) - 1) % mod
	else:
		one = 0
		zero = (pow(2, N - 1, mod) - 1) % mod
		more = pow(2, N - 1, mod)
	same = (one + zero) % mod
	t = 1
	for k in range(K - 1, -1, -1):
		res -= t * more % mod * pow_w[k] % mod
		res %= mod
		t = t * same % mod
	print(res)


mod = 10 ** 9 + 7

def modDivide(a, b, m):
	inv = pow(b, m - 2, m)
	return inv * a % m
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	if k == 0:
		print(1)
		continue
	if n % 2 == 1:
		print(pow(1 + pow(2, n - 1, mod), k, mod))
	else:
		t = pow(pow(2, n - 1, mod) - 1, k, mod)
		a = pow(2, n * k, mod)
		b = (pow(2, n - 1, mod) + 1) % mod
		a = modDivide((a - t + mod) % mod, b, mod)
		t = (t + a) % mod
		print(t)


import math
import random
import heapq, bisect
import sys
from collections import deque, defaultdict
from fractions import Fraction
import sys
from collections import defaultdict
mod = 10 ** 9 + 7
mod1 = 998244353
import os
import sys
from io import BytesIO, IOBase
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')
for ik in range(int(input())):
	(n, k) = map(int, input().split())
	great = 0
	equal = 0
	less = 0
	if n % 2 == 0:
		great = 1
	great %= mod
	if n % 2 == 1:
		equal = 1
	equal += pow(2, n - 1, mod)
	if n % 2 == 0:
		equal -= 1
	equal %= mod
	less = pow(2, n - 1, mod)
	if n % 2 == 1:
		less -= 1
	less %= mod
	ans = 0
	prev = 1
	for i in range(k):
		ans += prev * great % mod * pow(less + great + equal, k - 1 - i, mod)
		ans %= mod
		prev *= equal
		prev %= mod
	ans += prev
	ans %= mod
	print(ans)


from collections import defaultdict
import sys
p2D = lambda x: print(*x, sep='\n')

def II():
	return int(sys.stdin.buffer.readline())

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

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

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def BI():
	return sys.stdin.buffer.readline().rstrip()

def SI():
	return sys.stdin.buffer.readline().rstrip().decode()

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

def lli(rows):
	return [li() for _ in range(rows)]

def si():
	return input()

def ii():
	return int(input())

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

def solve():
	(n, k) = LI()
	mod = 10 ** 9 + 7
	if k == 0:
		return 1
	else:
		sbd = pow(2, n - 1, mod)
		ap = sbd * 2 % mod
		if n % 2:
			draw = pow(sbd + 1, k, mod)
			win = 0
		else:
			draw = pow(sbd - 1, k, mod)
			win = 0
			apf = 1
			sbdf = [1]
			sbd -= 1
			for l in range(k - 1):
				sbdf.append(sbdf[-1] * sbd % mod)
			for j in range(k):
				win = (win + apf * sbdf[k - j - 1] % mod) % mod
				apf = ap * apf % mod
		return (win + draw) % mod

def main():
	for _ in range(II()):
		sys.stdout.write(str(solve()) + '\n')
main()


inf = float('inf')
mod = 10 ** 9 + 7

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

def yn(a):
	print('YES' if a else 'NO')
ceil = lambda a, b: (a + b - 1) // b
t = int(input())
for i in range(t):
	(n, k) = [int(i) for i in input().split()]
	dp = [1 for i in range(k + 1)]
	muleven = pow(2, n - 1, mod)
	twon = pow(2, n, mod)
	mulodd = pow(2, n - 1, mod) + 1
	if n % 2 == 0:
		for i in range(1, k + 1):
			dp[i] = dp[i - 1] * (muleven - 1) % mod
			dp[i] = (pow(twon, i - 1, mod) + dp[i]) % mod
		print(dp[-1])
	else:
		for i in range(1, k + 1):
			dp[i] = dp[i - 1] * mulodd % mod
		print(dp[-1])


import sys
input = sys.stdin.readline

def solve():
	(n, k) = map(int, input().split())
	m = 10 ** 9 + 7
	val = pow(2, n - 1, m)
	if n % 2:
		val += 1
		val %= m
		return pow(val, k, m)
	else:
		R = pow(val + 1, m - 2, m)
		ans = (pow(2, n * k, m) - pow(val - 1, k, m)) % m * R % m
		ans += pow(val - 1, k, m)
		ans %= m
		return ans
for _ in range(int(input())):
	print(solve())


import decimal
import os
import sys
from collections import Counter
from io import BytesIO, IOBase
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 ints_get():
	return map(int, input().strip().split())

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

def chars_get():
	return list(map(str, sys.stdin.readline().strip().split()))

def output(to_be_printed, end='\n'):
	sys.stdout.write(str(to_be_printed) + end)

def main():
	MOD = 1000000007
	for _ in range(int(input())):
		(n, k) = map(int, input().split())
		if k == 0:
			print(1)
			continue
		if n == 1:
			print(pow(2, k, MOD))
			continue
		if n % 2 == 1:
			print(pow(pow(2, n - 1, MOD) + 1, k, MOD))
		else:
			ans = pow(pow(2, n - 1, MOD) - 1, k, MOD)
			for i in range(k):
				ans += pow(pow(2, n - 1, MOD) - 1, i, MOD) * pow(pow(2, n, MOD), k - 1 - i, MOD)
				ans %= MOD
			print(ans)
	return
main()