You are given an integer $N$. Consider set $S=\{0,\:1,\ldots,\:2^N-1\}$. How many subsets $A\subset S$ with $\bigoplus_{x\in A}x=0$ ($\theta$ denotes xor operation) are there? 

Print your answer modulo $(10^9+7)$. 

Note that the  xorsum of an empty set is zero!  

Input Format 

The first line contains one integer $\mathbf{T}$, the number of testcases. 

The next $\mathbf{T}$ lines contain one integer $N$ each.

Output Format 

Output $\mathbf{T}$ lines. Each line is one number, answer to the problem modulo $10^9+7$.

Constraints 

$1\leq T\leq10000$ 

$1\leq N\leq10^{18}$

Sample Input  

2
1
2

Sample Output  

2
4

Explanation 

For $N=1$ there are $2$ sets - ∅ and $\{0\}$. 

For $N=2$ there are $4$ sets - ∅, $\{0\}$, $\{1,\:2,\:3\}$, $\{0,\:1,\:2,\:3\}$.

Difficulty: MEDIUM
Tags: Number theory

Starter code:

Solutions:
import sys, random
from math import sqrt

def solve():
	stdin = sys.stdin
	MOD = 10 ** 9 + 7
	T = int(stdin.readline())
	for _ in range(T):
		N = int(stdin.readline())
		ex = (pow(2, N, MOD - 1) - N) % (MOD - 1)
		print(pow(2, ex, MOD))
solve()


P = 10 ** 9 + 7

def f(x):
	a = (pow(2, x, P - 1) - x) % (P - 1)
	return pow(2, a, P)
t = int(input())
for _ in range(t):
	print(f(int(input())))


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


n = int(input())
mod = 1000000007

def powmod(x, n, mod):
	res = 1
	while n:
		if n % 2 == 1:
			res = res * x % mod
		x = x * x % mod
		n //= 2
	return res
for i in range(n):
	x = int(input())
	print(powmod(2, (powmod(2, x, mod - 1) - x + mod - 1) % (mod - 1), mod))


def main():
	MOD = 10 ** 9 + 7
	ncases = int(input())
	for _ in range(ncases):
		n = int(input())
		exponent = (pow(2, n, MOD - 1) - n) % (MOD - 1)
		print(pow(2, exponent, MOD))
main()


import sys

def fastexpmod(n, pow, mod):
	if pow == 0:
		return 1
	return (n if pow % 2 else 1) * fastexpmod(n * n % mod, pow // 2, mod) % mod
p = MOD = 10 ** 9 + 7
input()
all_Ns = map(int, sys.stdin.read().split())
for N in all_Ns:
	exponent = (fastexpmod(2, N, p - 1) - N % (p - 1)) % (p - 1)
	print(fastexpmod(2, exponent, MOD))


def fastPow2(p, mod):
	base = 2
	result = 1
	while p > 0:
		if p % 2 == 1:
			result = result * base % mod
		p = p // 2
		base = base * base % mod
	return result

def doIt(ls):
	mod = 1000000007
	val = 2
	n = 1
	for x in ls:
		print(fastPow2((fastPow2(x, mod - 1) - x) % (mod - 1), mod))
t = int(input())
l = []
for i in range(t):
	l.append(int(input()))
doIt(l)


def modulo(a, b, c):
	x = 1
	y = a
	while b > 0:
		if b % 2 == 1:
			x = x * y % c
		y = y * y % c
		b //= 2
	return x
t = input()
t = int(t)
MOD = 1000000007
for i in range(t):
	n = input()
	n = int(n)
	power = modulo(2, n, MOD - 1)
	n = n % (MOD - 1)
	power = (power - n) % (MOD - 1)
	power = (power + MOD - 1) % (MOD - 1)
	ans = modulo(2, power, MOD)
	print(ans)


MOD = 10 ** 9 + 7
T = int(input())
for _ in range(T):
	N = int(input())
	NN = (pow(2, N, MOD - 1) - N) % (MOD - 1)
	print(pow(2, NN, MOD))


import sys, random
from math import sqrt

def solve():
	stdin = sys.stdin
	MOD = 10 ** 9 + 7
	T = int(stdin.readline())
	for _ in range(T):
		N = int(stdin.readline())
		ex = (pow(2, N, MOD - 1) - N) % (MOD - 1)
		print(pow(2, ex, MOD))
solve()


for _ in range(int(input())):
	N = int(input())
	print(pow(2, (pow(2, N, 10 ** 9 + 6) - N) % (10 ** 9 + 6), 10 ** 9 + 7))


T = int(input().strip())
for _ in range(T):
	N = int(input().strip())
	P = 10 ** 9 + 7
	print(pow(2, pow(2, N, P - 1) + -N % (P - 1), P))


def b(x, a, mod):
	y = 1
	while a > 0:
		if a & 1 == 1:
			y = y * x % mod
		x = x * x % mod
		a >>= 1
	return y
t = int(input())
mod = 10 ** 9 + 7
ans = []
for _ in range(t):
	n = int(input())
	m = b(2, n, mod - 1) - n
	m %= mod - 1
	ans.append(b(2, m, mod))
for i in range(len(ans)):
	print(ans[i])


m = 10 ** 9 + 7

def expsqm(x, n, mod):
	r = 1
	while n:
		if n % 2 == 1:
			r = r * x % mod
		x = x * x % mod
		n //= 2
	return r
for _ in range(int(input())):
	n = int(input())
	print(expsqm(2, (expsqm(2, n, m - 1) - n) % (m - 1), m))


modint = 10 ** 9 + 7

def expmod(a, n, m):
	if n == 1:
		return a % m
	elif n == 0:
		return 1
	else:
		res = 1
		if n % 2 == 1:
			res = res * (a % m) % m
		res = res * expmod(a, n // 2, m) ** 2 % m % m
		return res
t = int(input())
for i in range(t):
	n = int(input())
	print(expmod(2, (expmod(2, n, modint - 1) - n) % (modint - 1), modint))


t = int(input())
for i in range(t):
	n = int(input())
	d = (pow(2, n, 1000000006) - n) % 1000000006
	print(pow(2, d, 1000000007))


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


import sys

def extended_gcd(aa, bb):
	(lastremainder, remainder) = (abs(aa), abs(bb))
	(x, lastx, y, lasty) = (0, 1, 1, 0)
	while remainder:
		(lastremainder, (quotient, remainder)) = (remainder, divmod(lastremainder, remainder))
		(x, lastx) = (lastx - quotient * x, x)
		(y, lasty) = (lasty - quotient * y, y)
	return (lastremainder, lastx * (-1 if aa < 0 else 1), lasty * (-1 if bb < 0 else 1))

def modinv(a, m):
	(g, x, y) = extended_gcd(a, m)
	if g != 1:
		raise ValueError
	return x % m
M = 1000000007
TWO_INV = modinv(2, M)
Totient_M = M - 1

def solve(N):
	two_inv_n = pow(TWO_INV, N, M)
	two_n_mod_totient = pow(2, N, Totient_M)
	two_raised_2_N = pow(2, two_n_mod_totient, M)
	return two_inv_n * two_raised_2_N % M
T = int(input().strip())
for _ in range(T):
	N = int(input().strip())
	print(solve(N))


p = 10 ** 9 + 7
T = int(input())
for t in range(T):
	N = int(input())
	k = (pow(2, N, p - 1) - N) % (p - 1)
	print(pow(2, k, p))


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


import sys
from time import time

def solve_bf(n, m):
	cnt = 0
	k = pow(2, n)
	stack = [(0, 0)]
	while stack:
		(total, number) = stack.pop()
		if total == 0:
			cnt += 1
		for new_number in range(number, k):
			new_total = total ^ new_number
			next_number = new_number + 1
			stack.append((new_total, next_number))
	return cnt

def mat_mul(A, B, m):
	return ((A[0] * B[0] + A[1] * B[2]) % m, (A[0] * B[1] + A[1] * B[3]) % m, (A[2] * B[0] + A[3] * B[2]) % m, (A[2] * B[1] + A[3] * B[3]) % m)

def mat_pow(A, n, m):
	C = (1, 0, 0, 1)
	P = A
	while n != 0:
		if n % 2 == 1:
			C = mat_mul(C, P, m)
		P = mat_mul(P, P, m)
		n //= 2
	return C

def modinv(a, p):
	return pow(a, p - 2, p)

def solve_incorrect(n, m):
	print('n=%d m=%d' % (n, m), file=sys.stderr)
	if n < 3:
		return pow(2, n, m)
	M = (0, 1, 1, 2)
	P = mat_pow(M, n, m - 1)
	print('P=%s' % (P,), file=sys.stderr)
	p = P[2]
	return pow(2, p, m)

def solve(n, m):
	print('n=%d m=%d' % (n, m), file=sys.stderr)
	pwr = (pow(2, n, m - 1) - n) % (m - 1)
	return pow(2, pwr, m)
tm = time()
t = int(input())
m = pow(10, 9) + 7
for _ in range(t):
	n = int(input())
	print(solve(n, m))
print('time elapsed: %s' % (time() - tm), file=sys.stderr)


def modexp(a, b, m):
	a = a % m
	r = 1
	while b > 0:
		if b % 2 != 0:
			r = r * a % m
			b -= 1
		a = a ** 2 % m
		b = b >> 1
	return r
t = int(input())
for a0 in range(t):
	n = int(input())
	m = 10 ** 9 + 7
	t1 = (modexp(2, n, m - 1) - n % (m - 1)) % (m - 1)
	t2 = modexp(2, t1, m)
	print(t2)


P = 10 ** 9 + 7
T = int(input())
for _ in range(T):
	N = int(input())
	print(pow(2, (pow(2, N, P - 1) - N) % (P - 1), P))


MOD = 1000000007
for _ in range(int(input())):
	n = int(input())
	e = (pow(2, n, MOD - 1) - n) % (MOD - 1)
	r = pow(2, e, MOD)
	print(r)


def powerMod(base, exponent, modulus):
	result = 1
	while exponent > 0:
		if exponent % 2 == 1:
			result = result * base % modulus
		base = base * base % modulus
		exponent //= 2
	return result

def solve(n):
	p = 10 ** 9 + 7
	return powerMod(2, (powerMod(2, n, p - 1) - n) % (p - 1), p)
t = int(input())
for _ in range(t):
	n = int(input())
	print(solve(n))


mod = 1000000007

def powmod(b, e, m):
	rv = 1
	v = b
	while e > 0:
		if e & 1 == 1:
			rv = rv * v % m
		v = v * v % m
		e //= 2
	return rv
num_probs = int(input())
for _ in range(num_probs):
	n = int(input())
	mm = powmod(2, n, mod - 1)
	mmm = (mm - n) % (mod - 1)
	print(powmod(2, mmm, mod))


def bin(x, a, mod):
	y = 1
	while a > 0:
		if a & 1 == 1:
			y = y * x % mod
		x = x * x % mod
		a >>= 1
	return y
t = int(input())
mod = 10 ** 9 + 7
for _ in range(t):
	n = int(input())
	m = bin(2, n, mod - 1) - n
	m %= mod - 1
	ans = bin(2, m, mod)
	print(ans)


Q = int(input().strip())
mod = 7 + 10 ** 9

def binomial(n, k):
	if k < 0 or k > n:
		return 0
	if k == 0 or k == n:
		return 1
	k = min(k, n - k)
	c = 1
	for i in range(k):
		c = c * (n - i) // (i + 1)
	return c

def brute_force(n):
	N = 2 ** n
	S = [0] * (N + 1)
	S[0] = S[1] = 1
	for m in range(2, N + 1):
		S[m] = binomial(N, m - 1) - S[m - 2] * (N - (m - 2))
		assert S[m] % m == 0
		S[m] //= m
	return sum(S)

def solve_funny(N):
	expo = (pow(2, N, mod - 1) - N) % (mod - 1)
	return pow(2, expo, mod)
for _ in range(Q):
	N = int(input().strip())
	print(solve_funny(N))


M = 10 ** 9 + 7
for _ in range(int(input())):
	n = int(input())
	print(pow(2, (pow(2, n, M - 1) - n) % (M - 1), M))


import os
import sys
MOD = 1000000007
for _ in range(int(input())):
	n = int(input())
	e = (pow(2, n, MOD - 1) - n) % (MOD - 1)
	r = pow(2, e, MOD)
	print(r)


maxN = 10 ** 18
B = 10 ** 9 + 7

def multiplicativeInverse(M, b):
	return pow(M, b - 2, b)

def solve(n):
	denom = pow(2, n, B)
	invDenom = multiplicativeInverse(denom, B)
	TwoToTheN_modBminus1 = pow(2, n, B - 1)
	numerator = pow(2, TwoToTheN_modBminus1, B)
	return numerator * invDenom % B
t = int(input())
for _ in range(t):
	n = int(input())
	print(solve(n))


MOD = 1000000007
for _ in range(int(input())):
	n = int(input())
	e = (pow(2, n, MOD - 1) - n) % (MOD - 1)
	r = pow(2, e, MOD)
	print(r)


MOD = 1000000007
for _ in range(int(input())):
	n = int(input())
	e = (pow(2, n, MOD - 1) - n) % (MOD - 1)
	r = pow(2, e, MOD)
	print(r)


modint = 10 ** 9 + 7

def expmod(a, n, m):
	if n == 1:
		return a % m
	elif n == 0:
		return 1
	else:
		res = 1
		if n % 2 == 1:
			res = res * (a % m) % m
		res = res * expmod(a, n // 2, m) ** 2 % m % m
		return res
t = int(input())
for i in range(t):
	n = int(input())
	print(expmod(2, (expmod(2, n, modint - 1) - n) % (modint - 1), modint))


def power(x, a, mod):
	y = 1
	while a > 0:
		if a & 1 == 1:
			y = y * x % mod
		x = x * x % mod
		a >>= 1
	return y
t = int(input())
mod = 10 ** 9 + 7
for _ in range(t):
	n = int(input())
	m = power(2, n, mod - 1) - n
	m %= mod - 1
	ans = power(2, m, mod)
	print(ans)


mod = 10 ** 9 + 7
for _ in range(int(input())):
	n = int(input())
	first = pow(2, n, mod - 1)
	first = (first + mod - 1 - n) % (mod - 1)
	print(pow(2, first, mod))


def pow_mod(a, b, mod):
	res = 1
	while b > 0:
		if b % 2 == 1:
			res = res % mod * (a % mod) % mod
		a = a % mod * (a % mod) % mod
		b >>= 1
	return res
for _ in range(int(input())):
	n = int(input())
	mod = 10 ** 9 + 7
	remainder = (pow_mod(2, n, mod - 1) - n) % (mod - 1)
	ans = pow_mod(2, remainder, mod) % mod
	print(ans % (mod - 1))


MOD = 1000000007
for _ in range(int(input())):
	n = int(input())
	e = (pow(2, n, MOD - 1) - n) % (MOD - 1)
	r = pow(2, e, MOD)
	print(r)


MOD = 1000000007
for _ in range(int(input())):
	n = int(input())
	e = (pow(2, n, MOD - 1) - n) % (MOD - 1)
	r = pow(2, e, MOD)
	print(r)


mod = 10 ** 9 + 7

def fastExpo(x, n, p):
	ret = 1
	while n:
		if n & 1:
			ret = ret * x % p
		x = x * x % p
		n >>= 1
	return ret

def bezout(a, b):
	(r1, r2) = (a, b)
	(u1, v1) = (1, 0)
	(u2, v2) = (0, 1)
	(aux1, aux2) = (0, 0)
	q = 0
	while r2:
		q = r1 // r2
		(r1, r2) = (r2, r1 % r2)
		(aux1, aux2) = (u2, v2)
		(u2, v2) = (u1 - q * u2, v1 - q * v2)
		(u1, v1) = (aux1, aux2)
	return (u1, v1)

def main():
	t = int(input())
	for _ in range(t):
		n = int(input())
		power = fastExpo(2, n, mod - 1)
		A = fastExpo(2, power, mod)
		B = fastExpo(2, n, mod)
		C = bezout(B, mod)[0] % mod
		print(A * C % mod)
main()


MOD = 1000000007
for _ in range(int(input())):
	n = int(input())
	e = (pow(2, n, MOD - 1) - n) % (MOD - 1)
	r = pow(2, e, MOD)
	print(r)


import math
import os
import random
import re
import sys
MOD = 1000000007
for _ in range(int(input())):
	n = int(input())
	e = (pow(2, n, MOD - 1) - n) % (MOD - 1)
	r = pow(2, e, MOD)
	print(r)


def bin(x, a, mod):
	y = 1
	while a > 0:
		if a & 1 == 1:
			y = y * x % mod
		x = x * x % mod
		a >>= 1
	return y
t = int(input())
mod = 10 ** 9 + 7
for _ in range(t):
	n = int(input())
	m = bin(2, n, mod - 1) - n
	m %= mod - 1
	ans = bin(2, m, mod)
	print(ans)


import sys, random
from math import sqrt

def solve():
	stdin = sys.stdin
	MOD = 10 ** 9 + 7
	T = int(stdin.readline())
	for _ in range(T):
		N = int(stdin.readline())
		ex = (pow(2, N, MOD - 1) - N) % (MOD - 1)
		print(pow(2, ex, MOD))
solve()


import sys, random
from math import sqrt

def solve():
	stdin = sys.stdin
	MOD = 10 ** 9 + 7
	T = int(stdin.readline())
	for _ in range(T):
		N = int(stdin.readline())
		ex = (pow(2, N, MOD - 1) - N) % (MOD - 1)
		print(pow(2, ex, MOD))
solve()


MOD = 1000000007
for _ in range(int(input())):
	n = int(input())
	e = (pow(2, n, MOD - 1) - n) % (MOD - 1)
	r = pow(2, e, MOD)
	print(r)