Princess Artapoelc greeted her guests by either kissing on the cheek (K) or hugging (H). From the first guest 

she kisses, she has a
compulsion to necessarily kiss every alternate guest from that first kissed guest. That is if the guests are G_{1}, 

G_{2}, ..., G_{i}, G_{i+1}, ..., G_{n} and if she first kissed G_{i} then she must necessarily kiss 

G_{i+2}, G_{i+4}, G_{i+6} ... till the last
possible guest. Your task is to determine in how many ways she can greet N guests.
    
Input
    
First line of the input contains T (T ≤ 1000) denoting the number of test cases.
    
T
lines follow each containing a single integer N (1 ≤ N ≤ 10^{9}) denoting the number of guests.
    
Output
    
For each case the output should be a single integer representing the number of ways Artapoelc can greet N guests. As the 

answer can be large
print it modulo 1000000007.
    
----- Sample Input 1 ------ 
3
1
2
3
----- Sample Output 1 ------ 
2
4
6
----- explanation 1 ------ 

In the first case the possible ways are
    
K, H
    
Second case:
    
KH, HK, HH, KK
    
Third case:
    
HHH, HHK, HKH, HKK, KHK, KKK

Difficulty: MEDIUM
Tags: Number theory

Mathematics

Starter code:

Solutions:
for i in range(int(input())):
	n = int(input())
	ans = 2
	if n % 2 == 0:
		x = pow(2, n // 2, 1000000007)
		ans += 3 * x - 4
	else:
		x = pow(2, n // 2 + 1, 1000000007)
		ans += 2 * x - 4
	print(int(ans % 1000000007))


def solve():
	n = int(input())
	mod = 10 ** 9 + 7
	res = 0
	if n % 2 == 0:
		res += pow(2, n // 2, mod)
		n -= 1
	res += 4 * (pow(2, n // 2, mod) - 1)
	res += 2
	return res % mod
T = int(input())
while T:
	print(solve())
	T -= 1


for i in range(int(input())):
	N = int(input())
	NAS = 2
	NAS = 2
	if N % 2 == 0:
		N = pow(2, N // 2, 1000000007)
		NAS += N * 3 - 4
	else:
		N = pow(2, N // 2 + 1, 1000000007)
		NAS += N * 2 - 4
	NAS = NAS % 1000000007
	print(NAS)


for test in range(int(input())):
	n = int(input())
	m = 2
	if n % 2 != 0:
		n = pow(2, n // 2 + 1, 1000000007)
		m += 2 * n - 4
	else:
		n = pow(2, n // 2, 1000000007)
		m += 3 * n - 4
	m = m % 1000000007
	print(m)


t = int(input())
m = 1000000007
for x in range(t):
	n = int(input())

	def pw2(n):
		if n == 0:
			return 1
		r = pw2(int(n / 2))
		r = r * r % m
		if n % 2 != 0:
			r = 2 * r % m
		return r
	if n % 2 == 1:
		k = (n + 1) // 2
		print(2 * pw2(k) % m - 2)
	else:
		k = n // 2
		print(3 * pw2(k) % m - 2)


m = 10 ** 9 + 7
for _ in range(int(input())):
	n = int(input())
	n += 1

	def pw2(n):
		if n == 0:
			return 1
		r = pw2(int(n / 2))
		r = r * r % m
		if n % 2 != 0:
			r = 2 * r % m
		return r
	print((pw2(n // 2) % m + pw2(n - n // 2) % m - 2) % m)


modulo = 1000000007

def pw2(n):
	if n == 0:
		return 1
	r = pw2(int(n / 2))
	r = r * r % modulo
	if n % 2 != 0:
		r = 2 * r % modulo
	return r

def solve(n):
	n1 = int(n / 2)
	n2 = n - n1
	return (pw2(n1) + pw2(n2) - 2) % modulo
t = int(input())
while t > 0:
	n = int(input())
	print(solve(n + 1) % modulo)
	t -= 1


for _ in range(int(input())):
	n = int(input())
	if n % 2 == 1:
		k = (n + 1) // 2
		ans = 2 * pow(2, k, 1000000007) - 2
		ans = ans % 1000000007
		print(ans)
	else:
		k = (n + 2) // 2
		p = pow(2, k, 1000000007)
		ans = 2 * p % 1000000007 - pow(2, k - 1, 1000000007) - 2
		ans = ans % 1000000007
		print(ans)


import bisect
import sys
import math

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

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

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

def get_int():
	return int(sys.stdin.readline().strip())

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

def solve():
	n = get_int()
	M = 10 ** 9 + 7
	if n == 1:
		print(2)
		return
	ans = 2
	if n % 2 == 0:
		c = (n - 1) // 2
		ans += pow(2, c + 2, M)
		ans += pow(2, n // 2, M)
		ans -= 4
		ans = ans % M
		print(ans)
	else:
		c = n // 2
		ans += pow(2, c + 2, M)
		ans -= 4
		ans = ans % M
		print(ans)
T = get_int()
while T:
	solve()
	T -= 1


M = 1000000007

def solve(b):
	if b == 0:
		return 1
	r = solve(b // 2)
	r = r * r % M
	if b % 2 == 1:
		r = r * 2 % M
	return r
for i in range(int(input())):
	n = int(input())
	n += 1
	ans = (solve(n // 2) + solve(n - n // 2) - 2) % M
	print(ans)


NT = int(input())
MOD = 1000000007
while NT > 0:
	NT -= 1
	N = int(input())
	ans = 1
	if N % 2 == 0:
		k = N // 2
		ans = (3 * pow(2, k, MOD) - 2) % MOD
	else:
		k = (N + 1) // 2
		ans = (pow(2, k + 1, MOD) - 2) % MOD
	ans = (ans + MOD) % MOD
	print(ans)


import math
m = 1000000007
for _ in range(int(input())):
	n = int(input())
	i = math.ceil((n + 1) / 2)
	j = (n + 1) // 2
	i1 = pow(2, i, m)
	j1 = pow(2, j, m)
	count = (i1 + j1 - 2) % m
	print(int(count))


import math
T = int(input())
mod = 1000000007
for _ in range(T):
	N = int(input())
	A = math.ceil((N + 1) / 2)
	B = (N + 1) // 2
	C = pow(2, A, mod)
	D = pow(2, B, mod)
	ans = (C + D - 2) % mod
	print(int(ans))


mod = 1000000007
for _ in range(int(input())):
	n = int(input())
	if n % 2 == 0:
		print((3 * pow(2, n // 2, mod) % mod - 2) % mod)
	else:
		print((2 * pow(2, (n + 1) // 2, mod) % mod - 2) % mod)


T = int(input())
for _ in range(T):
	N = int(input())
	K = 0
	if N > 0:
		K = 2
		if N % 2 == 1:
			n = pow(2, N // 2 + 1, 1000000007)
			K += 2 * n - 4
		else:
			n = pow(2, N // 2, 1000000007)
			K += 3 * n - 4
	K = K % 1000000007
	print(K)


def power(a, b):
	res = 1
	while b > 0:
		if b & 1:
			res *= a
			res %= mod
		a *= a
		a %= mod
		b >>= 1
	return res % mod
t = int(input())
mod = 1000000007
for test in range(t):
	n = int(input())
	if n == 1:
		print(2)
		continue
	res = power(2, n // 2)
	ans = res - 2
	ans %= mod
	ans = 2 + 2 * ans
	ans += res
	ans %= mod
	if n % 2 == 1:
		ans += res
		ans %= mod
	ans %= mod
	print(ans)


import math
import os
import random
import re
import sys
T = int(input())
mod = 1000000007
for _ in range(T):
	N = int(input())
	A = math.ceil((N + 1) / 2)
	B = (N + 1) // 2
	C = pow(2, A, mod)
	D = pow(2, B, mod)
	ans = (C + D - 2) % mod
	print(int(ans))


import sys
import math
sys.setrecursionlimit(10 ** 7)

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

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

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

def get_int():
	return int(sys.stdin.readline().strip())

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

def exp(x, n, m):
	if n == 0:
		return 1
	ans = exp(x, n // 2, m)
	ans = ans * ans % m
	if n % 2 == 1:
		ans *= x
		ans = ans % m
	return ans

def solve(n):
	n += 1
	n1 = n // 2
	n2 = n - n1
	ans = exp(2, n1, 10 ** 9 + 7) + exp(2, n2, 10 ** 9 + 7) - 2
	ans = ans % (10 ** 9 + 7)
	print(ans)
	return
T = get_int()
while T:
	n = get_int()
	solve(n)
	T -= 1


from math import log2 as log
import math

def power(a, b):
	res = 1
	while b > 0:
		if b & 1 == 1:
			res = res * a % 1000000007
		a = a * a % 1000000007
		b = b >> 1
	return res
t = int(input())
lim = 1000000007
for _ in range(t):
	n = int(input())
	if n == 1:
		print(2)
	else:
		k = 1
		if n % 2 == 0:
			n = n - 1
			k = 2 + 4 * (power(2, n // 2) - 1) + power(2, n // 2 + 1)
		else:
			k = 2 + 4 * (power(2, n // 2) - 1)
		print(k % lim)


def power(a, b):
	res = 1
	while b > 0:
		if b & 1 == 1:
			res = res * a % 1000000007
		a = a * a % 1000000007
		b = b >> 1
	return res
T = int(input())
for _ in range(T):
	n = int(input())
	s = 0
	n = n - 1
	if n % 2 == 0:
		term = n // 2
		s = 4 * (power(2, term) - 1) % 1000000007
	else:
		term = (n - 1) // 2
		s = 4 * (power(2, term) - 1) % 1000000007
		s = (s + power(2, term + 1)) % 1000000007
	print((s + 2) % 1000000007)


import math

def repeated(a, b):
	res = 1
	while b > 0:
		if b % 2 == 1:
			res = res * a % m
		a = a * a % m
		b = b // 2
	return res
m = 10 ** 9 + 7
for _ in range(int(input())):
	N = int(input())
	print((repeated(2, (N + 1) // 2) + repeated(2, math.ceil((N + 1) / 2)) - 2) % m)


def power(t, q, u):
	x = int(t)
	y = int(q)
	p = int(u)
	x = x % p
	res = 1
	while y > 0:
		if y % 2 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res
testc = int(input())
for i in range(testc):
	a = int(input())
	ans = 0
	z = 0
	if a % 2 == 0:
		z = a // 2
		ans = power(2, z, 1000000007) + power(2, z + 1, 1000000007) - 2
		print(ans % 1000000007)
	else:
		z = (a + 1) // 2
		ans = power(2, z, 1000000007) + power(2, z, 1000000007) - 2
		print(ans % 1000000007)


import math
T = int(input())
for i in range(T):
	n = int(input())
	a = pow(2, (n + 1) // 2, 10 ** 9 + 7)
	b = pow(2, math.ceil((n + 1) / 2), 10 ** 9 + 7)
	c = (a + b - 2) % (10 ** 9 + 7)
	print(c)


import math
mod = 10 ** 9 + 7
for _ in range(int(input())):
	n = int(input())
	e = (n + 1) // 2
	o = math.ceil((n + 1) / 2)
	a1 = pow(2, e, mod)
	a2 = pow(2, o, mod)
	ans = (a1 + a2 - 2) % mod
	print(ans)


m = 1000000007

def pow(n):
	(r, x) = (1, 2)
	while n:
		if n & 1:
			r = r * x % m
		n >>= 1
		x = x * x % m
	return r
for t in range(int(input())):
	n = int(input()) + 2
	if n & 1:
		print((pow(n // 2) - 1) * 2 % m)
	else:
		print(((pow(n // 2) - 1) * 2 % m - pow((n - 1) // 2)) % m)


def power(no, times, m):
	if times == 0:
		return 1
	val = power(no, times // 2, m) % m
	val = val * val % m
	if times % 2 == 0:
		return val
	else:
		return no * val % m
t = int(input())
while t > 0:
	n = int(input())
	m = 1000000007
	no = 2
	if n % 2 == 0:
		print((2 * (power(no, n // 2, m) - 1) + power(no, n // 2, m)) % m)
	else:
		print(2 * (power(no, n // 2 + 1, m) - 1) % 1000000007)
	t -= 1


import math
for u in range(int(input())):
	n = int(input())
	m = 10 ** 9 + 7
	x = math.ceil((n + 1) / 2)
	y = math.floor((n + 1) / 2)
	xx = pow(2, x, m)
	yy = pow(2, y, m)
	print((xx + yy - 2) % m)


mod = int(1000000000.0) + 7
for _ in range(int(input())):
	n = int(input())
	if n <= 2:
		print(2 * n)
		continue
	till = n >> 1
	ans = 2
	if n % 2 == 0:
		ans += pow(2, till, mod)
		till -= 1
	ans = (ans + 4 * pow(2, till, mod) - 4) % mod
	print(ans)


import math
mod = 10 ** 9 + 7
t = int(input())
while t:
	n = int(input())
	p1 = math.floor((n + 1) / 2)
	p2 = math.ceil((n + 1) / 2)
	ans1 = pow(2, p1, mod)
	ans2 = pow(2, p2, mod)
	ans = (ans1 + ans2 - 2) % mod
	print(ans)
	t -= 1


import math
mod = 10 ** 9 + 7
for _ in range(int(input())):
	n = int(input())
	p1 = math.ceil((n + 1) / 2)
	p2 = math.floor((n + 1) / 2)
	ans1 = pow(2, p1, mod)
	ans2 = pow(2, p2, mod)
	ans = ans1 + ans2 - 2
	print(ans % mod)


import math
mod = 10 ** 9 + 7
for _ in range(int(input())):
	n = int(input())
	op1 = pow(2, math.ceil((n + 1) / 2), mod)
	op2 = pow(2, math.floor((n + 1) / 2), mod) - 2
	print((op1 + op2) % mod)


import math
for _ in range(int(input())):
	n = int(input())
	p = (pow(2, math.ceil((n + 1) / 2), 10 ** 9 + 7) + pow(2, math.floor((n + 1) / 2), 10 ** 9 + 7) - 2) % (10 ** 9 + 7)
	print(p)


import math
try:
	T = int(input())
	for i in range(T):
		N = int(input())
		s = 1000000007
		a = math.ceil((N + 1) / 2)
		b = (N + 1) // 2
		print((pow(2, a, s) + pow(2, b, s) - 2) % s)
except:
	pass


import math
for _ in range(int(input())):
	n = int(input())
	a = math.ceil((n + 1) / 2)
	b = (n + 1) // 2
	print((pow(2, a, 1000000007) + pow(2, b, 1000000007) - 2) % 1000000007)


import math
import sys
inp = sys.stdin.readlines()
leninp = len(inp) - 1
i = 1
t = int(inp[0])
for _ in range(t):
	init = 2
	n = int(inp[i])
	i += 1
	init1 = math.ceil((n + 1) / 2)
	init2 = (n + 1) // 2
	output = pow(2, init1, 1000000007) + pow(2, init2, 1000000007) - 2
	print(output % 1000000007)


import sys
from random import choice, randint
inp = sys.stdin.readline
out = sys.stdout.write
flsh = sys.stdout.flush
sys.setrecursionlimit(10 ** 9)
inf = 10 ** 20
eps = 1.0 / 10 ** 10
mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]

def MI():
	return map(int, inp().strip().split())

def LI():
	return list(map(int, inp().strip().split()))

def LLI():
	return [list(map(int, l.split())) for l in sys.stdin.readlines().strip()]

def LI_():
	return [int(x) - 1 for x in inp().strip().split()]

def LF():
	return [float(x) for x in inp().strip().split()]

def LS():
	return inp().strip().split()

def I():
	return int(inp().strip())

def F():
	return float(inp().strip())

def S():
	return inp().strip()

def pf(s):
	return out(s + '\n')

def JA(a, sep):
	return sep.join(map(str, a))

def JAA(a, s, t):
	return s.join((t.join(map(str, b)) for b in a))

def main():
	from math import ceil, floor

	def fast_exponentiation(base, exp):
		res = 1
		while exp:
			if exp & 1:
				res = res * base % mod
			base = base * base % mod
			exp >>= 1
		return res % mod
	t = I()
	l = []
	for _ in range(t):
		n = I()
		ans = fast_exponentiation(2, ceil((n + 1) / 2)) + fast_exponentiation(2, floor((n + 1) / 2)) - 2
		l.append(ans % mod)
	for i in range(t):
		pf(str(l[i]))
main()


from math import ceil, floor
for _ in range(int(input())):
	N = int(input())
	A = (pow(2, ceil((N + 1) / 2), 1000000007) + pow(2, floor((N + 1) / 2), 1000000007) - 2) % 1000000007
	print(A)


t = int(input())
for _ in range(t):
	n = int(input())
	c = 0
	if n == 1:
		print(2)
	elif n == 2:
		print(4)
	elif n % 2 != 0:
		c = int(pow(2, n // 2 + 1, 1000000007)) - 1
		print(2 * c % 1000000007)
	else:
		c = int(pow(2, n // 2, 1000000007))
		ans = (2 * (c - 1) + c) % 1000000007
		print(ans % 1000000007)


def f(base, exp, mod=1000000007):
	res = 1
	while exp > 0:
		if exp % 2 == 1:
			res = res * base % mod
		base = base * base % mod
		exp = int(exp / 2)
	return res % mod

def count(n):
	if n == 1:
		return 2
	exp = int(n / 2)
	p = f(2, exp, 1000000007)
	gp = 2 * (p - 1) % 1000000007
	ans = 2 + 2 * gp
	if n % 2 == 0:
		ans -= p
	return ans % 1000000007

def c(N):
	MOD = 1000000007
	if N % 2 == 0:
		k = int(N / 2)
		ans = 3 * pow(2, k, MOD) - 2
	else:
		k = int((N + 1) / 2)
		ans = pow(2, k + 1, MOD) - 2
	ans = (ans + MOD) % MOD
	return ans
for case in range(int(input())):
	N = int(input())
	print(count(N))


import math
for _ in range(int(input())):
	n = int(input())
	print((pow(2, math.ceil((n + 1) / 2), 1000000007) + pow(2, math.floor((n + 1) / 2), 1000000007) - 2) % 1000000007)


mod = 1000000007
for _ in range(int(input())):
	N = int(input())
	p = N // 2
	if N % 2 == 1:
		print((pow(2, p + 2, mod) - 2) % mod)
	else:
		print((3 * pow(2, p, mod) - 2) % mod)


def ckisshug(n):

	def binary_exponentiation(a, b, p):
		r = 1
		while b:
			if b % 2:
				r = r * a % p
			a = a * a % p
			b >>= 1
		return r
	p = 1000000007
	if n == 1:
		return 2
	elif n & 1:
		A = 4 * (binary_exponentiation(2, n // 2 - 1, p) - 1) % p % p
		B = 2 * binary_exponentiation(2, n // 2, p) % p
		return (A % p + B % p) % p + 2
	else:
		A = 4 * (binary_exponentiation(2, n // 2 - 1, p) - 1) % p % p
		B = binary_exponentiation(2, n // 2, p)
		return (A % p + B % p) % p + 2
t = int(input())
for _ in range(t):
	n = int(input())
	print(ckisshug(n))


for _ in range(int(input())):
	n = int(input())
	if n % 2 == 0:
		ans = (pow(2, (n - 1) // 2 + 1, 1000000007) - 1) * 2 + pow(2, n // 2, 1000000007)
	else:
		ans = (pow(2, (n - 1) // 2 + 1, 1000000007) - 1) * 2
	print(ans % 1000000007)


mod = int(1000000000.0 + 7)

def exp(pw):
	base = 2
	res = 1
	while pw > 0:
		if pw % 2 == 1:
			res = res * base % mod
		base = base * base % mod
		pw //= 2
	return res % mod
for _ in range(int(input())):
	n = int(input())
	k = n
	f = 0
	if n % 2 == 0:
		f = 1
		n = n // 2 - 1
		n += 2
	else:
		n = n // 2
		n += 2
	a = exp(n)
	if f == 1:
		a = (a + exp(k // 2)) % mod
	a = (a - 2 % mod) % mod
	print(a)


for _ in range(int(input())):
	n = int(input())
	if n % 2:
		n1 = n // 2
		print((pow(2, n1 + 1, 1000000007) - 1 + 2 * (pow(2, n1, 1000000007) - 1) + 1) % 1000000007)
	else:
		n1 = n // 2
		print((pow(2, n1 + 1, 1000000007) - 1 + 2 * (pow(2, n1 - 1, 1000000007) - 1) + 1) % 1000000007)


from math import ceil, floor
mod = 10 ** 9 + 7
for _ in range(int(input())):
	n = int(input())
	x1 = ceil((n + 1) / 2)
	x2 = floor((n + 1) / 2)
	print((pow(2, x1, mod) + pow(2, x2, mod) - 2) % mod)


import math

def abc(n):
	e = 10 ** 9 + 7
	k = math.ceil(n / 2)
	x = (pow(2, k + 1, e) - 2) % e
	if n % 2 != 0:
		return x
	return (x + pow(2, k, e)) % e
t = int(input())
for _ in range(t):
	n = int(input())
	print(abc(n))


MOD = 1000000007
for _ in range(int(input())):
	n = int(input())
	k = 0
	ans = 0
	if n % 2 == 0:
		k = n // 2
		ans = 3 * pow(2, k, MOD) - 2
	else:
		k = (n + 1) // 2
		ans = pow(2, k + 1, MOD) - 2
	ans = (ans + MOD) % MOD
	print(ans)


for i in range(int(input())):
	n = int(input())
	if n % 2 != 0:
		sum = 2 * (pow(2, (n + 1) // 2, 1000000007) - 1)
	else:
		val = pow(2, n // 2, 1000000007)
		sum = 3 * val - 2
	print(sum % 1000000007)


from math import ceil
for _ in range(int(input())):
	n = int(input())
	if n % 2:
		ans = 2 * (pow(2, ceil(n / 2), 10 ** 9 + 7) - 1) % (10 ** 9 + 7)
	else:
		ans = (2 * (pow(2, ceil(n / 2), 10 ** 9 + 7) - 1) + pow(2, n // 2, 10 ** 9 + 7)) % (10 ** 9 + 7)
	print(ans)


import math
t = int(input())
for j in range(t):
	a = int(input())
	if a % 2 == 0:
		n = int(a / 2)
		ans = pow(2, n, 1000000007) - 1
		ans = 3 * (ans % 1000000007) % 1000000007
		print(ans + 1)
	else:
		n = int((a + 1) / 2)
		ans = pow(2, n, 1000000007) - 1
		ans = 2 * (ans % 1000000007) % 1000000007
		print(ans)


def poww(power, base):
	res = 1
	while power:
		if power & 1:
			res *= base % mod
		base *= base % mod
		power >>= 1
	return res
t = int(input())
mod = 1000000007
for i in range(t):
	n = int(input())
	if n == 1:
		print(2)
		continue
	terms = n // 2
	terms -= 1
	temp = poww(terms, 2)
	sumGP = 2 + 4 * (temp - 1)
	if n % 2 == 0:
		print((sumGP + temp * 2) % mod)
	else:
		print((sumGP + temp * 4) % mod)


t = int(input())
m = 1000000007
while t > 0:
	n = int(input())
	if n % 2 == 0:
		ans = 3 * pow(2, n // 2, m) - 2
	else:
		ans = 2 * pow(2, (n + 1) // 2, m) - 2
	print(ans % m)
	t -= 1


t = int(input())
for _ in range(t):
	n = int(input())
	m = 1000000007
	if n % 2 == 0:
		z = pow(2, n // 2, m)
		z = 3 * z - 2
	else:
		z = pow(2, (n + 1) // 2, m)
		z = 2 * z - 2
	print(z % m)


test_cases = int(input())
for i in range(test_cases):
	n = int(input())
	m = 1000000007
	if n % 2 == 0:
		z = pow(2, n // 2, m)
		z = 3 * z - 2
	else:
		z = pow(2, (n + 1) // 2, m)
		z = 2 * z - 2
	print(z % m)


def fun(base, exp):
	res = 1
	mod = 10 ** 9 + 7
	while exp > 0:
		if exp & 1:
			res = res * base % mod
		base = base * base % mod
		exp = exp >> 1
	return res % mod
t = int(input())
MOD = 10 ** 9 + 7
while t > 0:
	t -= 1
	N = int(input())
	ans = 1
	if N % 2 == 0:
		k = N // 2
		ans = 3 * fun(2, k) - 2
	else:
		k = (N + 1) // 2
		ans = fun(2, k + 1) - 2
	ans = (ans + MOD) % MOD
	print(int(ans))


mod = 1000000007

def power(b, y):
	result = 1
	while y > 0:
		if y % 2 == 1:
			result = result * b % mod
		b = b * b % mod
		y //= 2
	return result % mod
for i in range(int(input())):
	n = int(input())
	if n == 1:
		print(2)
		continue
	if n & 1:
		d = n // 2
		c = n // 2
	else:
		d = n // 2
		c = n // 2 - 1
	ans = 2 + 2 * (power(2, d) + power(2, c) - 2)
	print(ans % mod)


N = 1000000007

def power(bas, exp):
	if exp == 0:
		return 1
	if exp == 1:
		return bas % N
	t = power(bas, int(exp / 2))
	t = t * t % N
	if exp % 2 == 0:
		return t
	else:
		return bas % N * t % N
for _ in range(int(input())):
	n = int(input())
	res = 2
	if (n - 1) % 2 == 1:
		exp = int(n / 2)
		res += power(2, exp) + 2 * 2 * (power(2, int((n - 2) / 2)) - 1)
	else:
		exp = int((n - 1) / 2)
		res += 2 * 2 * (power(2, exp) - 1)
	if res > N:
		print(res % N)
	else:
		print(res)