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

For a given $N$, find the number of ways to choose an integer $x$ from the range $[0, 2^{N} - 1]$ such that $x \oplus (x+1) = (x+2) \oplus (x+3)$, where $\oplus$ denotes the bitwise XOR operator.

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

------ Input ------

The first line contains an integer $T$, the number of test cases. Then the test cases follow. 
The only line of each test case contains a single integer $N$. 

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

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

------ Subtasks ------
Subtask #1 (100 points): Original Constraints

----- Sample Input 1 ------ 
2

1

2
----- Sample Output 1 ------ 
1

2
----- explanation 1 ------ 
Test Case $1$: The possible values of $x$ are $\{0\}$.

Test Case $2$: The possible values of $x$ are $\{0, 2\}$.

Difficulty: MEDIUM
Tags: Bit manipulation

Constructive algorithms

Number theory

Mathematics

Ad-hoc
Skill types: Bit manipulation

Starter code:

Solutions:
for _ in range(int(input())):
	n = int(input())
	print(pow(2, n - 1, 1000000007))


for i in range(int(input())):
	n = int(input())
	print(pow(2, n - 1, 1000000007))


for i in range(int(input())):
	n = int(input())
	if n == 1:
		print(1)
	elif n == 2:
		print(2)
	else:
		print(pow(2, n - 1, 10 ** 9 + 7))


t = int(input())
while t > 0:
	n = int(input())
	print(pow(2, n - 1, 1000000007))
	t -= 1


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


a = int(input(''))
for i in range(a):
	x = int(input())
	print(pow(2, x - 1, 1000000007))


maxn = 10 ** 5
mod = 10 ** 9 + 7
dp = [1]
for i in range(1, maxn + 1):
	dp.append(dp[i - 1] * 2 % mod)
for case in range(int(input())):
	n = int(input())
	print(dp[n - 1])


for t in range(int(input())):
	n = int(input())
	print(pow(2, n - 1, 1000000007))


import math
for tc in range(int(input())):
	n = int(input())
	print(pow(2, n - 1, 1000000007))


modNo = int(1000000000.0 + 7)
t = int(input())
while t > 0:
	n = int(input())
	print(pow(2, n - 1, modNo))
	t = t - 1


t = int(input())
while t > 0:
	p = int(input())
	k = pow(2, p - 1, 1000000007)
	print(k)
	t -= 1


factDp = [-1 for i in range(10 ** 5)]
curr = 2
factDp[0] = 1
factDp[1] = 2
MOD = 10 ** 9 + 7
for i in range(2, 10 ** 5):
	curr = curr * 2 % MOD
	factDp[i] = curr
for _ in range(int(input())):
	n = int(input())
	res = factDp[n - 1]
	print(res)


t = int(input())
for i in range(t):
	x = int(input())
	mod = 1000000007
	print(pow(2, x - 1, mod))


for t in range(int(input())):
	n = int(input())
	import math
	if n == 1:
		print(1)
	elif n == 2:
		print(2)
	else:
		v = pow(2, n - 1, 1000000007)
		print(v)


t = int(input())
while t:
	count1 = 0
	n = int(input())
	if n == 0:
		print(1)
	else:
		print(pow(2, n - 1, 1000000007))
	t = t - 1


tum = int(input())
pum = int(1000000000.0 + 7)
for i in range(tum):
	num = int(input())
	if num == 1:
		print(1)
	else:
		print((2 << num - 2) % pum)


import math
t = int(input())
for _ in range(t):
	n = int(input())
	res = pow(2, n - 1, 1000000007)
	print(res)


from sys import stdin
for _ in range(int(stdin.readline())):
	print(pow(2, int(stdin.readline()) - 1, 1000000007))


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


t = int(input())
for i in range(t):
	n = int(input())
	c = 1
	n = n - 1
	b = 2
	while n:
		if n % 2 != 0:
			c = c * b % 1000000007
		b = b * b % 1000000007
		n //= 2
	print(c % 1000000007)


for T in range(int(input())):
	n = int(input())
	ans = pow(2, n - 1, 1000000007)
	print(ans)


for U in range(int(input())):
	n = int(input())
	print(pow(2, n - 1, 1000000007))


from sys import stdin
l = []
lim = 10000000000.0 + 7
for _ in range(int(stdin.readline())):
	l.append(pow(2, int(stdin.readline()) - 1, 1000000007))
for i in l:
	print(i)


z = int(input())
while z:
	n = int(input())
	print(pow(2, n - 1, 1000000007))
	z -= 1


for i in range(int(input())):
	n = int(input())
	x = 1 << n
	m = 1000000007
	print(x // 2 % m)


for _ in range(int(input())):
	k = int(input())
	print(pow(2, k - 1, 1000000007))


t = int(input())
try:
	while t:
		n = int(input())
		print(pow(2, n - 1, 1000000007))
except:
	pass


t = int(input())
while t > 0:
	n = int(input())
	x = 1000000007
	a = pow(2, n - 1, x)
	print(a)
	t -= 1


for i in range(int(input())):
	count = 0
	a = int(input())
	print(pow(2, a - 1, 1000000007))


poww = [0]
res = 2
for i in range(1, 100001):
	poww.append(res)
	res *= 2
for _ in range(int(input())):
	n = int(input())
	print(poww[n] // 2 % 1000000007)


t = int(input())
import math
for _ in range(t):
	m = pow(10, 9) + 7
	n = int(input())
	n = pow(2, n - 1, m)
	print(n)


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


z = int(input())
while z:
	z -= 1
	a = int(input())
	print(pow(2, a - 1, 1000000007))