Mr. X wants to buy a necklace for his girlfriend.
The available necklaces are bi-colored (red and blue beads).

Mr. X desperately wants to impress his girlfriend and knows that she will like the necklace only if every prime length continuous sub-sequence of beads in the necklace has more or equal number of red beads than blue beads.

Given the number of beads in the necklace N, Mr. X wants to know the number of all possible such necklaces.

Note: - It is given that the necklace is a single string and not a loop.

Input Format 

The first line of the input contains an integer T, the number of testcases. 

T lines follow, each line containing N, the number of beads in the necklace.  

Constraints 

1 ≤ T ≤ 10^{4} 

2 ≤ N ≤ 10^{18}  

Output Format 

For each testcase, print in a newline, the number of such necklaces that are possible.  If the answer is greater than or equal to 10^{9}+7, print the answer modulo ( % ) 10^{9}+7.

Sample Input

2
2
3

Sample Output

3
4

Explanation

For the first testcase, valid arrangement of beads are 

BR RB RR

For the second testcase, valid arrangement of beads are

BRR RBR RRR RRB

Source: hackerrank | Difficulty: MEDIUM_HARD
Tags: Matrices


Solutions:
from random import randint
from collections import Counter
from functools import reduce
from itertools import accumulate, combinations, takewhile
home = 0
lire = 1
trace = 0
mp = 10 ** 6
if home:
	from mesures import ch
modo = 10 ** 9 + 7
pars = []

def sqmatmulmod(m1, m2, modo=None):
	if trace & 32:
		print(m1, m2)
	mr = [[0] * len(m1)]
	for i in range(len(m1) - 1):
		mr += [mr[0].copy()]
	for l in range(len(m1)):
		for c in range(len(m1)):
			mr[l][c] = sum((m1[l][ix] * m2[ix][c] for ix in range(len(m1)))) % modo
	return mr

def matUnit(n):
	r = []
	for ix in range(n):
		r = r + [[0] * ix + [1] + [0] * (n - ix - 1)]
	return r

def expMatMod(m1, po, modo=None):
	r = matUnit(len(m1))
	em1 = m1.copy()
	bm = 1
	while po:
		if po & bm:
			r = sqmatmulmod(em1, r, modo)
			po ^= bm
		em1 = sqmatmulmod(em1, em1, modo)
		bm <<= 1
	return r

def matmulvec_(m1, v):
	return list((sum((m1[l][ix] * v[ix] for ix in range(len(m1)))) for l in range(len(m1))))

def matmulvec(m1, v, modo=None):
	if modo is None:
		return matmulvec_(m1, v)
	if len(v) != len(m1):
		print('erreur mul vect taille matrice et vecteur differents', len(v), len(m1))
		return None
	res = []
	for l in range(len(m1)):
		res += [sum((m1[l][ix] * v[ix] for ix in range(len(m1))))]
	return list((sum((m1[l][ix] * v[ix] for ix in range(len(m1)))) % modo for l in range(len(m1))))

def preCalc(maxpo):
	global mat, vect
	mat = [[0, 1, 1, 1], [1, 0, 0, 0], [0, 1, 0, 0], [0, 0, 1, 0]]
	vect = [6, 4, 3, 2]
	mats = {}
	mats[1] = mat
	for po in range(2, maxpo + 1):
		mats[1 << po - 1] = sqmatmulmod(mats[1 << po - 2], mats[1 << po - 2], modo)
	return mats

def faireUn(N):
	if N < 4:
		return [3, 4][N - 2]
	n = N - 4
	cb = 1
	r = matUnit(4)
	while n:
		if n & cb:
			r = sqmatmulmod(r, mats[cb], modo)
			n ^= cb
		cb <<= 1
	return list(matmulvec(r, vect, modo))[0]
if home and (not lire):
	pass
else:
	Nbs = list(enumerate((int(input().strip()) for _ in range(int(input().strip())))))
	Nbs.sort(key=lambda k: k[1])
	mxPo = max((i[1] for i in Nbs)).bit_length()
	mats = preCalc(mxPo)
	lr = [[Nb[0], faireUn(Nb[1]), Nb[1]] for Nb in Nbs]
	if trace & 16:
		print(list(((Nb[1], parMat(Nb[1]), faireUn(Nb[1])) for Nb in Nbs)))
	for r in sorted(lr):
		print(r[1])


import math
PHI = (116 + 12 * 93 ** (1 / 2)) ** (1 / 3)
PHI_BAR = (116 - 12 * 93 ** (1 / 2)) ** (1 / 3)
PSI = -1 + 3 ** (1 / 2) * 1j
PSI_BAR = -1 - 3 ** (1 / 2) * 1j
R_1 = 1 / 6 * (2 + (PHI + PHI_BAR))
R_2 = 1 / 12 * (4 + PSI * PHI_BAR + PSI_BAR * PHI)
R_3 = 1 / 12 * (4 + PSI * PHI + PSI_BAR * PHI_BAR)
A = 2 * R_2 * R_3 / (R_1 * (R_1 - R_2) * (R_1 - R_3)) - 3 * (R_2 + R_3) / (R_1 * (R_1 - R_2) * (R_1 - R_3)) + 4 / (R_1 * (R_1 - R_2) * (R_1 - R_3))
B = -2 * R_1 * R_3 / (R_2 * (R_1 - R_2) * (R_2 - R_3)) + 3 * (R_1 + R_3) / (R_2 * (R_1 - R_2) * (R_2 - R_3)) - 4 / (R_2 * (R_1 - R_2) * (R_2 - R_3))
C = 2 * R_1 * R_2 / (R_3 * (R_1 - R_3) * (R_2 - R_3)) + 3 * (R_1 + R_2) / (R_3 * (R_1 - R_3) * (R_2 - R_3)) + 4 / (R_3 * (R_1 - R_3) * (R_2 - R_3))

def count_arrangements(n):
	return A * R_1 ** n + B * R_2 ** n + C * R_3 ** n
A = [[1, 0, 1], [1, 0, 0], [0, 1, 0]]
MOD = 10 ** 9 + 7
INIT = [2, 3, 4]

def matrix_count_arrangements(n):
	if n < 4:
		return INIT[n - 1]
	M = matrix_exp(A, n - 3)
	return (INIT[2] * M[0][0] + INIT[1] * M[0][1] + INIT[0] * M[0][2]) % MOD

def matrix_exp(A, n):
	binary_length = int(math.log(n, 2)) + 1
	powers_of_A = [0] * (binary_length + 1)
	powers_of_A[0] = [[1, 0, 0], [0, 1, 0], [0, 0, 1]]
	powers_of_A[1] = A
	for i in range(2, binary_length + 1):
		A_i_1 = powers_of_A[i - 1]
		powers_of_A[i] = matrix_multiply(A_i_1, A_i_1)
	answer = powers_of_A[0]
	i = 1
	while n > 0:
		if n & 1:
			answer = matrix_multiply(answer, powers_of_A[i])
		n >>= 1
		i += 1
	return answer

def matrix_multiply(A, B):
	return [[(A[0][0] * B[0][0] + A[0][1] * B[1][0] + A[0][2] * B[2][0]) % MOD, (A[0][0] * B[0][1] + A[0][1] * B[1][1] + A[0][2] * B[2][1]) % MOD, (A[0][0] * B[0][2] + A[0][1] * B[1][2] + A[0][2] * B[2][2]) % MOD], [(A[1][0] * B[0][0] + A[1][1] * B[1][0] + A[1][2] * B[2][0]) % MOD, (A[1][0] * B[0][1] + A[1][1] * B[1][1] + A[1][2] * B[2][1]) % MOD, (A[1][0] * B[0][2] + A[1][1] * B[1][2] + A[1][2] * B[2][2]) % MOD], [(A[2][0] * B[0][0] + A[2][1] * B[1][0] + A[2][2] * B[2][0]) % MOD, (A[2][0] * B[0][1] + A[2][1] * B[1][1] + A[2][2] * B[2][1]) % MOD, (A[2][0] * B[0][2] + A[2][1] * B[1][2] + A[2][2] * B[2][2]) % MOD]]
t = int(input().strip())
for _ in range(t):
	n = int(input().strip())
	print(matrix_count_arrangements(n))


import sys
from time import time

def primes_gen(n):
	cache = [True] * n
	cache[0] = cache[1] = False
	for p in range(n):
		if cache[p]:
			yield p
			for i in range(p + p, n, p):
				cache[i] = False

def cache_gen(prms):

	def is_valid(s):
		l = len(s)
		if l % 2 == 0:
			thr = l // 2
		else:
			thr = l // 2 + 1
		for p in prms:
			if p > len(s):
				break
			t = s[:p]
			if p == 2:
				thr = 1
			else:
				thr = p // 2 + 1
			r = sum((1 for c in t if c == 'R'))
			if r < thr:
				return False
		return True
	cache = {''}
	while True:
		yield cache
		new_cache = set()
		for s in cache:
			for c in 'BR':
				t = c + s
				if is_valid(t):
					new_cache.add(t)
				t = s + c
				if is_valid(t[::-1]):
					new_cache.add(t)
		cache = new_cache

def test(n, m):
	prms = tuple(primes_gen(100))
	print('prms=%s' % (prms,), file=sys.stderr)
	for (i, cache) in enumerate(cache_gen(prms)):
		print('i=%s cache=%d' % (i, len(cache)), file=sys.stderr)
		if i == n:
			break
	return 0

def mat_mul(A, B, m):
	return ((A[0] * B[0] + A[1] * B[3] + A[2] * B[6]) % m, (A[0] * B[1] + A[1] * B[4] + A[2] * B[7]) % m, (A[0] * B[2] + A[1] * B[5] + A[2] * B[8]) % m, (A[3] * B[0] + A[4] * B[3] + A[5] * B[6]) % m, (A[3] * B[1] + A[4] * B[4] + A[5] * B[7]) % m, (A[3] * B[2] + A[4] * B[5] + A[5] * B[8]) % m, (A[6] * B[0] + A[7] * B[3] + A[8] * B[6]) % m, (A[6] * B[1] + A[7] * B[4] + A[8] * B[7]) % m, (A[6] * B[2] + A[7] * B[5] + A[8] * B[8]) % m)

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

def solve(n, m):
	A = (0, 0, 1, 1, 0, 0, 0, 1, 1)
	P = mat_pow(A, n, m)
	return (P[0] + 2 * P[3] + 3 * P[6]) % m
tm = time()
m = pow(10, 9) + 7
t = int(input())
for _ in range(t):
	n = int(input())
	print(solve(n, m))
print('time elapsed: %s' % (time() - tm), file=sys.stderr)


S = 3
P = 10 ** 9 + 7

def mult(A, B):
	C = [[0] * S for _ in range(S)]
	for i in range(S):
		for j in range(S):
			for k in range(S):
				C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % P
	return C
A = [[1, 0, 1], [1, 0, 0], [0, 1, 0]]
Apow2 = [[[1, 0, 0], [0, 1, 0], [0, 0, 1]], A]
for _ in range(1, 62):
	Apow2.append(mult(Apow2[-1], Apow2[-1]))

def Apow(b):
	result = [[1, 0, 0], [0, 1, 0], [0, 0, 1]]
	p2 = 1
	while b:
		if b & 1:
			result = mult(result, Apow2[p2])
		p2 += 1
		b >>= 1
	return result

def main():
	T = int(input())
	for _ in range(T):
		N = int(input())
		M = Apow(N - 2)
		cnt = 0
		for i in range(3):
			for j in range(3):
				cnt = (cnt + M[i][j]) % P
		print(cnt)
main()


modulo_constant = 10 ** 9 + 7

def mx_times(a, b, m):
	return [[sum((a * b for (a, b) in zip(a_row, b_col))) % m for b_col in zip(*b)] for a_row in a]

def mx_pow(mx, n, mo):
	ret = [[1, 0, 0], [0, 1, 0], [0, 0, 1]]
	while n:
		if n & 1:
			ret = mx_times(ret, mx, mo)
		n >>= 1
		mx = mx_times(mx, mx, mo)
	return ret

def necklace(n):
	return mx_pow([[1, 1, 0], [0, 0, 1], [1, 0, 0]], n + 2, modulo_constant)[0][0]

def run_necklace(reader=input, printer=print):
	for _ in range(int(reader())):
		printer(int(necklace(int(reader()))))
run_necklace()


mod = 1000000007
apow2list = [[[1, 1, 0], [0, 0, 1], [1, 0, 0]]]

def matpow(a, n, x):
	toret = []
	for i in range(n):
		row = [0] * n
		row[i] = 1
		toret.append(row)
	apow2 = a
	curr = x
	stepnum = 0
	while curr > 0:
		if curr % 2 == 1:
			nextret = []
			for i in range(n):
				row = [0] * n
				for j in range(n):
					for k in range(n):
						row[j] = (row[j] + toret[i][k] * apow2[k][j]) % mod
				nextret.append(row)
			toret = nextret
		stepnum += 1
		try:
			apow2 = apow2list[stepnum]
		except:
			nextapow = []
			for i in range(n):
				row = [0] * n
				for j in range(n):
					for k in range(n):
						row[j] = (row[j] + apow2[i][k] * apow2[k][j]) % mod
				nextapow.append(row)
			apow2 = nextapow
			apow2list.append(apow2.copy())
		curr //= 2
	return toret
t = int(input())
mat = [[1, 1, 0], [0, 0, 1], [1, 0, 0]]
for _ in range(t):
	n = int(input())
	apow = matpow(mat, 3, n)
	print((apow[0][0] + apow[0][1] + apow[0][2]) % mod)


M = 10 ** 9 + 7
d = {}

def f(n):
	if n <= 0:
		return 1
	if n == 1:
		return 2
	if n == 2:
		return 3
	if n == 3:
		return 4
	if n in d:
		return d[n]
	t1 = f(n // 2 - 1)
	t2 = f(n // 2 - 2)
	t3 = f(n // 2 - 3)
	if n % 2 == 0:
		d[n] = (t1 * t1 + 2 * t2 * t3) % M
	else:
		d[n] = (t2 * t2 + 2 * t3 * t1 + t1 * t1) % M
	return d[n]
T = input()
for _ in range(int(T)):
	N = int(input())
	print(f(N))


M = 10 ** 9 + 7
d = {}

def f(n):
	if n <= 0:
		return 1
	if n == 1:
		return 2
	if n == 2:
		return 3
	if n == 3:
		return 4
	if n in d:
		return d[n]
	t1 = f(n // 2 - 1)
	t2 = f(n // 2 - 2)
	t3 = f(n // 2 - 3)
	if n % 2 == 0:
		d[n] = (t1 * t1 + 2 * t2 * t3) % M
	else:
		d[n] = (t2 * t2 + 2 * t3 * t1 + t1 * t1) % M
	return d[n]
T = input()
for _ in range(int(T)):
	N = int(input())
	print(f(N))


M = 10 ** 9 + 7
d = {}

def f(n):
	if n <= 0:
		return 1
	if n == 1:
		return 2
	if n == 2:
		return 3
	if n == 3:
		return 4
	if n in d:
		return d[n]
	t1 = f(n // 2 - 1)
	t2 = f(n // 2 - 2)
	t3 = f(n // 2 - 3)
	if n % 2 == 0:
		d[n] = (t1 * t1 + 2 * t2 * t3) % M
	else:
		d[n] = (t2 * t2 + 2 * t3 * t1 + t1 * t1) % M
	return d[n]
T = input()
for _ in range(int(T)):
	N = int(input())
	print(f(N))


M = 10 ** 9 + 7
d = {}

def f(n):
	if n <= 0:
		return 1
	if n == 1:
		return 2
	if n == 2:
		return 3
	if n == 3:
		return 4
	if n in d:
		return d[n]
	t1 = f(n // 2 - 1)
	t2 = f(n // 2 - 2)
	t3 = f(n // 2 - 3)
	if n % 2 == 0:
		d[n] = (t1 * t1 + 2 * t2 * t3) % M
	else:
		d[n] = (t2 * t2 + 2 * t3 * t1 + t1 * t1) % M
	return d[n]
T = input()
for _ in range(int(T)):
	N = int(input())
	print(f(N))


M = 10 ** 9 + 7
d = {}

def f(n):
	if n <= 0:
		return 1
	if n == 1:
		return 2
	if n == 2:
		return 3
	if n == 3:
		return 4
	if n in d:
		return d[n]
	t1 = f(n // 2 - 1)
	t2 = f(n // 2 - 2)
	t3 = f(n // 2 - 3)
	if n % 2 == 0:
		d[n] = (t1 * t1 + 2 * t2 * t3) % M
	else:
		d[n] = (t2 * t2 + 2 * t3 * t1 + t1 * t1) % M
	return d[n]
T = input()
for _ in range(int(T)):
	N = int(input())
	print(f(N))


M = 10 ** 9 + 7
d = {}

def f(n):
	if n <= 0:
		return 1
	if n == 1:
		return 2
	if n == 2:
		return 3
	if n == 3:
		return 4
	if n in d:
		return d[n]
	t1 = f(n // 2 - 1)
	t2 = f(n // 2 - 2)
	t3 = f(n // 2 - 3)
	if n % 2 == 0:
		d[n] = (t1 * t1 + 2 * t2 * t3) % M
	else:
		d[n] = (t2 * t2 + 2 * t3 * t1 + t1 * t1) % M
	return d[n]
T = input()
for _ in range(int(T)):
	N = int(input())
	print(f(N))


M = 10 ** 9 + 7
d = {}

def f(n):
	if n <= 0:
		return 1
	if n == 1:
		return 2
	if n == 2:
		return 3
	if n == 3:
		return 4
	if n in d:
		return d[n]
	t1 = f(n // 2 - 1)
	t2 = f(n // 2 - 2)
	t3 = f(n // 2 - 3)
	if n % 2 == 0:
		d[n] = (t1 * t1 + 2 * t2 * t3) % M
	else:
		d[n] = (t2 * t2 + 2 * t3 * t1 + t1 * t1) % M
	return d[n]
T = input()
for _ in range(int(T)):
	N = int(input())
	print(f(N))


M = 10 ** 9 + 7
d = {}

def f(n):
	if n <= 0:
		return 1
	if n == 1:
		return 2
	if n == 2:
		return 3
	if n == 3:
		return 4
	if n in d:
		return d[n]
	t1 = f(n // 2 - 1)
	t2 = f(n // 2 - 2)
	t3 = f(n // 2 - 3)
	if n % 2 == 0:
		d[n] = (t1 * t1 + 2 * t2 * t3) % M
	else:
		d[n] = (t2 * t2 + 2 * t3 * t1 + t1 * t1) % M
	return d[n]
T = input()
for _ in range(int(T)):
	N = int(input())
	print(f(N))


M = 10 ** 9 + 7
d = {}

def f(n):
	if n <= 0:
		return 1
	if n == 1:
		return 2
	if n == 2:
		return 3
	if n == 3:
		return 4
	if n in d:
		return d[n]
	t1 = f(n // 2 - 1)
	t2 = f(n // 2 - 2)
	t3 = f(n // 2 - 3)
	if n % 2 == 0:
		d[n] = (t1 * t1 + 2 * t2 * t3) % M
	else:
		d[n] = (t2 * t2 + 2 * t3 * t1 + t1 * t1) % M
	return d[n]
T = input()
for _ in range(int(T)):
	N = int(input())
	print(f(N))


M = 10 ** 9 + 7
d = {}

def f(n):
	if n <= 0:
		return 1
	if n == 1:
		return 2
	if n == 2:
		return 3
	if n == 3:
		return 4
	if n in d:
		return d[n]
	t1 = f(n // 2 - 1)
	t2 = f(n // 2 - 2)
	t3 = f(n // 2 - 3)
	if n % 2 == 0:
		d[n] = (t1 * t1 + 2 * t2 * t3) % M
	else:
		d[n] = (t2 * t2 + 2 * t3 * t1 + t1 * t1) % M
	return d[n]
T = input()
for _ in range(int(T)):
	N = int(input())
	print(f(N))


M = 10 ** 9 + 7
d = {}

def f(n):
	if n <= 0:
		return 1
	if n == 1:
		return 2
	if n == 2:
		return 3
	if n == 3:
		return 4
	if n in d:
		return d[n]
	t1 = f(n // 2 - 1)
	t2 = f(n // 2 - 2)
	t3 = f(n // 2 - 3)
	if n % 2 == 0:
		d[n] = (t1 * t1 + 2 * t2 * t3) % M
	else:
		d[n] = (t2 * t2 + 2 * t3 * t1 + t1 * t1) % M
	return d[n]
T = input()
for _ in range(int(T)):
	N = int(input())
	print(f(N))


M = 10 ** 9 + 7
d = {}

def f(n):
	if n <= 0:
		return 1
	if n == 1:
		return 2
	if n == 2:
		return 3
	if n == 3:
		return 4
	if n in d:
		return d[n]
	t1 = f(n // 2 - 1)
	t2 = f(n // 2 - 2)
	t3 = f(n // 2 - 3)
	if n % 2 == 0:
		d[n] = (t1 * t1 + 2 * t2 * t3) % M
	else:
		d[n] = (t2 * t2 + 2 * t3 * t1 + t1 * t1) % M
	return d[n]
T = input()
for _ in range(int(T)):
	N = int(input())
	print(f(N))


M = 10 ** 9 + 7
d = {}

def f(n):
	if n <= 0:
		return 1
	if n == 1:
		return 2
	if n == 2:
		return 3
	if n == 3:
		return 4
	if n in d:
		return d[n]
	t1 = f(n // 2 - 1)
	t2 = f(n // 2 - 2)
	t3 = f(n // 2 - 3)
	if n % 2 == 0:
		d[n] = (t1 * t1 + 2 * t2 * t3) % M
	else:
		d[n] = (t2 * t2 + 2 * t3 * t1 + t1 * t1) % M
	return d[n]
T = input()
for _ in range(int(T)):
	N = int(input())
	print(f(N))


M = 10 ** 9 + 7
d = {}

def f(n):
	if n <= 0:
		return 1
	if n == 1:
		return 2
	if n == 2:
		return 3
	if n == 3:
		return 4
	if n in d:
		return d[n]
	t1 = f(n // 2 - 1)
	t2 = f(n // 2 - 2)
	t3 = f(n // 2 - 3)
	if n % 2 == 0:
		d[n] = (t1 * t1 + 2 * t2 * t3) % M
	else:
		d[n] = (t2 * t2 + 2 * t3 * t1 + t1 * t1) % M
	return d[n]
T = input()
for _ in range(int(T)):
	N = int(input())
	print(f(N))


M = 10 ** 9 + 7
d = {}

def f(n):
	if n <= 0:
		return 1
	if n == 1:
		return 2
	if n == 2:
		return 3
	if n == 3:
		return 4
	if n in d:
		return d[n]
	t1 = f(n // 2 - 1)
	t2 = f(n // 2 - 2)
	t3 = f(n // 2 - 3)
	if n % 2 == 0:
		d[n] = (t1 * t1 + 2 * t2 * t3) % M
	else:
		d[n] = (t2 * t2 + 2 * t3 * t1 + t1 * t1) % M
	return d[n]
T = input()
for _ in range(int(T)):
	N = int(input())
	print(f(N))


M = 10 ** 9 + 7
d = {}

def f(n):
	if n <= 0:
		return 1
	if n == 1:
		return 2
	if n == 2:
		return 3
	if n == 3:
		return 4
	if n in d:
		return d[n]
	t1 = f(n // 2 - 1)
	t2 = f(n // 2 - 2)
	t3 = f(n // 2 - 3)
	if n % 2 == 0:
		d[n] = (t1 * t1 + 2 * t2 * t3) % M
	else:
		d[n] = (t2 * t2 + 2 * t3 * t1 + t1 * t1) % M
	return d[n]
T = input()
for _ in range(int(T)):
	N = int(input())
	print(f(N))


M = 10 ** 9 + 7
d = {}

def f(n):
	if n <= 0:
		return 1
	if n == 1:
		return 2
	if n == 2:
		return 3
	if n == 3:
		return 4
	if n in d:
		return d[n]
	t1 = f(n // 2 - 1)
	t2 = f(n // 2 - 2)
	t3 = f(n // 2 - 3)
	if n % 2 == 0:
		d[n] = (t1 * t1 + 2 * t2 * t3) % M
	else:
		d[n] = (t2 * t2 + 2 * t3 * t1 + t1 * t1) % M
	return d[n]
T = input()
for _ in range(int(T)):
	N = int(input())
	print(f(N))


M = 10 ** 9 + 7
d = {}

def f(n):
	if n <= 0:
		return 1
	if n == 1:
		return 2
	if n == 2:
		return 3
	if n == 3:
		return 4
	if n in d:
		return d[n]
	t1 = f(n // 2 - 1)
	t2 = f(n // 2 - 2)
	t3 = f(n // 2 - 3)
	if n % 2 == 0:
		d[n] = (t1 * t1 + 2 * t2 * t3) % M
	else:
		d[n] = (t2 * t2 + 2 * t3 * t1 + t1 * t1) % M
	return d[n]
T = input()
for _ in range(int(T)):
	N = int(input())
	print(f(N))


from random import randint
from collections import Counter
from functools import reduce
from itertools import accumulate, combinations, takewhile
home = 0
lire = 1
trace = 0
mp = 10 ** 6
if home:
	from mesures import ch
modo = 10 ** 9 + 7
pars = []

def sqmatmulmod(m1, m2, modo=None):
	if trace & 32:
		print(m1, m2)
	mr = [[0] * len(m1)]
	for i in range(len(m1) - 1):
		mr += [mr[0].copy()]
	for l in range(len(m1)):
		for c in range(len(m1)):
			mr[l][c] = sum((m1[l][ix] * m2[ix][c] for ix in range(len(m1)))) % modo
	return mr

def matUnit(n):
	r = []
	for ix in range(n):
		r = r + [[0] * ix + [1] + [0] * (n - ix - 1)]
	return r

def expMatMod(m1, po, modo=None):
	r = matUnit(len(m1))
	em1 = m1.copy()
	bm = 1
	while po:
		if po & bm:
			r = sqmatmulmod(em1, r, modo)
			po ^= bm
		em1 = sqmatmulmod(em1, em1, modo)
		bm <<= 1
	return r

def matmulvec_(m1, v):
	return list((sum((m1[l][ix] * v[ix] for ix in range(len(m1)))) for l in range(len(m1))))

def matmulvec(m1, v, modo=None):
	if modo is None:
		return matmulvec_(m1, v)
	if len(v) != len(m1):
		print('erreur mul vect taille matrice et vecteur differents', len(v), len(m1))
		return None
	res = []
	for l in range(len(m1)):
		res += [sum((m1[l][ix] * v[ix] for ix in range(len(m1))))]
	return list((sum((m1[l][ix] * v[ix] for ix in range(len(m1)))) % modo for l in range(len(m1))))

def preCalc(maxpo):
	global mat, vect
	mat = [[0, 1, 1, 1], [1, 0, 0, 0], [0, 1, 0, 0], [0, 0, 1, 0]]
	vect = [6, 4, 3, 2]
	mats = {}
	mats[1] = mat
	for po in range(2, maxpo + 1):
		mats[1 << po - 1] = sqmatmulmod(mats[1 << po - 2], mats[1 << po - 2], modo)
	return mats

def faireUn(N):
	if N < 4:
		return [3, 4][N - 2]
	n = N - 4
	cb = 1
	r = matUnit(4)
	while n:
		if n & cb:
			r = sqmatmulmod(r, mats[cb], modo)
			n ^= cb
		cb <<= 1
	return list(matmulvec(r, vect, modo))[0]
if home and (not lire):
	pass
else:
	Nbs = list(enumerate((int(input().strip()) for _ in range(int(input().strip())))))
	Nbs.sort(key=lambda k: k[1])
	mxPo = max((i[1] for i in Nbs)).bit_length()
	mats = preCalc(mxPo)
	lr = [[Nb[0], faireUn(Nb[1]), Nb[1]] for Nb in Nbs]
	if trace & 16:
		print(list(((Nb[1], parMat(Nb[1]), faireUn(Nb[1])) for Nb in Nbs)))
	for r in sorted(lr):
		print(r[1])


M = 10 ** 9 + 7
d = {}

def f(n):
	if n <= 0:
		return 1
	if n == 1:
		return 2
	if n == 2:
		return 3
	if n == 3:
		return 4
	if n in d:
		return d[n]
	t1 = f(n // 2 - 1)
	t2 = f(n // 2 - 2)
	t3 = f(n // 2 - 3)
	if n % 2 == 0:
		d[n] = (t1 * t1 + 2 * t2 * t3) % M
	else:
		d[n] = (t2 * t2 + 2 * t3 * t1 + t1 * t1) % M
	return d[n]
T = input()
for _ in range(int(T)):
	N = int(input())
	print(f(N))


M = 10 ** 9 + 7
d = {}

def f(n):
	if n <= 0:
		return 1
	if n == 1:
		return 2
	if n == 2:
		return 3
	if n == 3:
		return 4
	if n in d:
		return d[n]
	t1 = f(n // 2 - 1)
	t2 = f(n // 2 - 2)
	t3 = f(n // 2 - 3)
	if n % 2 == 0:
		d[n] = (t1 * t1 + 2 * t2 * t3) % M
	else:
		d[n] = (t2 * t2 + 2 * t3 * t1 + t1 * t1) % M
	return d[n]
T = input()
for _ in range(int(T)):
	N = int(input())
	print(f(N))


M = 10 ** 9 + 7
d = {}

def f(n):
	if n <= 0:
		return 1
	if n == 1:
		return 2
	if n == 2:
		return 3
	if n == 3:
		return 4
	if n in d:
		return d[n]
	t1 = f(n // 2 - 1)
	t2 = f(n // 2 - 2)
	t3 = f(n // 2 - 3)
	if n % 2 == 0:
		d[n] = (t1 * t1 + 2 * t2 * t3) % M
	else:
		d[n] = (t2 * t2 + 2 * t3 * t1 + t1 * t1) % M
	return d[n]
n = int(input())
for i in range(n):
	N = int(input())
	print(f(N))


M = 10 ** 9 + 7
d = {}

def f(n):
	if n <= 0:
		return 1
	if n == 1:
		return 2
	if n == 2:
		return 3
	if n == 3:
		return 4
	if n in d:
		return d[n]
	t1 = f(n // 2 - 1)
	t2 = f(n // 2 - 2)
	t3 = f(n // 2 - 3)
	if n % 2 == 0:
		d[n] = (t1 * t1 + 2 * t2 * t3) % M
	else:
		d[n] = (t2 * t2 + 2 * t3 * t1 + t1 * t1) % M
	return d[n]
T = input()
for _ in range(int(T)):
	N = int(input())
	print(f(N))


M = 10 ** 9 + 7
d = {}

def f(n):
	if n <= 0:
		return 1
	if n == 1:
		return 2
	if n == 2:
		return 3
	if n == 3:
		return 4
	if n in d:
		return d[n]
	t1 = f(n // 2 - 1)
	t2 = f(n // 2 - 2)
	t3 = f(n // 2 - 3)
	if n % 2 == 0:
		d[n] = (t1 * t1 + 2 * t2 * t3) % M
	else:
		d[n] = (t2 * t2 + 2 * t3 * t1 + t1 * t1) % M
	return d[n]
T = input()
for _ in range(int(T)):
	N = int(input())
	print(f(N))


M = 10 ** 9 + 7
d = {}

def f(n):
	if n <= 0:
		return 1
	if n == 1:
		return 2
	if n == 2:
		return 3
	if n == 3:
		return 4
	if n in d:
		return d[n]
	t1 = f(n // 2 - 1)
	t2 = f(n // 2 - 2)
	t3 = f(n // 2 - 3)
	if n % 2 == 0:
		d[n] = (t1 * t1 + 2 * t2 * t3) % M
	else:
		d[n] = (t2 * t2 + 2 * t3 * t1 + t1 * t1) % M
	return d[n]
T = input()
for _ in range(int(T)):
	N = int(input())
	print(f(N))


M = 10 ** 9 + 7
d = {}

def f(n):
	if n <= 0:
		return 1
	if n == 1:
		return 2
	if n == 2:
		return 3
	if n == 3:
		return 4
	if n in d:
		return d[n]
	t1 = f(n // 2 - 1)
	t2 = f(n // 2 - 2)
	t3 = f(n // 2 - 3)
	if n % 2 == 0:
		d[n] = (t1 * t1 + 2 * t2 * t3) % M
	else:
		d[n] = (t2 * t2 + 2 * t3 * t1 + t1 * t1) % M
	return d[n]
T = input()
for _ in range(int(T)):
	N = int(input())
	print(f(N))


M = 10 ** 9 + 7
d = {}

def f(n):
	if n <= 0:
		return 1
	if n == 1:
		return 2
	if n == 2:
		return 3
	if n == 3:
		return 4
	if n in d:
		return d[n]
	t1 = f(n // 2 - 1)
	t2 = f(n // 2 - 2)
	t3 = f(n // 2 - 3)
	if n % 2 == 0:
		d[n] = (t1 * t1 + 2 * t2 * t3) % M
	else:
		d[n] = (t2 * t2 + 2 * t3 * t1 + t1 * t1) % M
	return d[n]
T = input()
for _ in range(int(T)):
	N = int(input())
	print(f(N))


M = 10 ** 9 + 7
d = {}

def f(n):
	if n <= 0:
		return 1
	if n == 1:
		return 2
	if n == 2:
		return 3
	if n == 3:
		return 4
	if n in d:
		return d[n]
	t1 = f(n // 2 - 1)
	t2 = f(n // 2 - 2)
	t3 = f(n // 2 - 3)
	if n % 2 == 0:
		d[n] = (t1 * t1 + 2 * t2 * t3) % M
	else:
		d[n] = (t2 * t2 + 2 * t3 * t1 + t1 * t1) % M
	return d[n]
T = input()
for _ in range(int(T)):
	N = int(input())
	print(f(N))


M = 10 ** 9 + 7
d = {}

def f(n):
	if n <= 0:
		return 1
	if n == 1:
		return 2
	if n == 2:
		return 3
	if n == 3:
		return 4
	if n in d:
		return d[n]
	t1 = f(n // 2 - 1)
	t2 = f(n // 2 - 2)
	t3 = f(n // 2 - 3)
	if n % 2 == 0:
		d[n] = (t1 * t1 + 2 * t2 * t3) % M
	else:
		d[n] = (t2 * t2 + 2 * t3 * t1 + t1 * t1) % M
	return d[n]
T = input()
for _ in range(int(T)):
	N = int(input())
	print(f(N))


M = 10 ** 9 + 7
d = {}

def f(n):
	if n <= 0:
		return 1
	if n == 1:
		return 2
	if n == 2:
		return 3
	if n == 3:
		return 4
	if n in d:
		return d[n]
	t1 = f(n // 2 - 1)
	t2 = f(n // 2 - 2)
	t3 = f(n // 2 - 3)
	if n % 2 == 0:
		d[n] = (t1 * t1 + 2 * t2 * t3) % M
	else:
		d[n] = (t2 * t2 + 2 * t3 * t1 + t1 * t1) % M
	return d[n]
T = input()
for _ in range(int(T)):
	N = int(input())
	print(f(N))


M = 10 ** 9 + 7
d = {}

def f(n):
	if n <= 0:
		return 1
	if n == 1:
		return 2
	if n == 2:
		return 3
	if n == 3:
		return 4
	if n in d:
		return d[n]
	t1 = f(n // 2 - 1)
	t2 = f(n // 2 - 2)
	t3 = f(n // 2 - 3)
	if n % 2 == 0:
		d[n] = (t1 * t1 + 2 * t2 * t3) % M
	else:
		d[n] = (t2 * t2 + 2 * t3 * t1 + t1 * t1) % M
	return d[n]
T = input()
for _ in range(int(T)):
	N = int(input())
	print(f(N))


M = 10 ** 9 + 7
d = {}

def f(n):
	if n <= 0:
		return 1
	if n == 1:
		return 2
	if n == 2:
		return 3
	if n == 3:
		return 4
	if n in d:
		return d[n]
	t1 = f(n // 2 - 1)
	t2 = f(n // 2 - 2)
	t3 = f(n // 2 - 3)
	if n % 2 == 0:
		d[n] = (t1 * t1 + 2 * t2 * t3) % M
	else:
		d[n] = (t2 * t2 + 2 * t3 * t1 + t1 * t1) % M
	return d[n]
T = input()
for _ in range(int(T)):
	N = int(input())
	print(f(N))


M = 10 ** 9 + 7
d = {}

def f(n):
	if n <= 0:
		return 1
	if n == 1:
		return 2
	if n == 2:
		return 3
	if n == 3:
		return 4
	if n in d:
		return d[n]
	t1 = f(n // 2 - 1)
	t2 = f(n // 2 - 2)
	t3 = f(n // 2 - 3)
	if n % 2 == 0:
		d[n] = (t1 * t1 + 2 * t2 * t3) % M
	else:
		d[n] = (t2 * t2 + 2 * t3 * t1 + t1 * t1) % M
	return d[n]
T = input()
for _ in range(int(T)):
	N = int(input())
	print(f(N))


M = 10 ** 9 + 7
d = {}

def f(n):
	if n <= 0:
		return 1
	if n == 1:
		return 2
	if n == 2:
		return 3
	if n == 3:
		return 4
	if n in d:
		return d[n]
	t1 = f(n // 2 - 1)
	t2 = f(n // 2 - 2)
	t3 = f(n // 2 - 3)
	if n % 2 == 0:
		d[n] = (t1 * t1 + 2 * t2 * t3) % M
	else:
		d[n] = (t2 * t2 + 2 * t3 * t1 + t1 * t1) % M
	return d[n]
T = input()
for _ in range(int(T)):
	N = int(input())
	print(f(N))


M = 10 ** 9 + 7
d = {}

def f(n):
	if n <= 0:
		return 1
	if n == 1:
		return 2
	if n == 2:
		return 3
	if n == 3:
		return 4
	if n in d:
		return d[n]
	t1 = f(n // 2 - 1)
	t2 = f(n // 2 - 2)
	t3 = f(n // 2 - 3)
	if n % 2 == 0:
		d[n] = (t1 * t1 + 2 * t2 * t3) % M
	else:
		d[n] = (t2 * t2 + 2 * t3 * t1 + t1 * t1) % M
	return d[n]
T = input()
for _ in range(int(T)):
	N = int(input())
	print(f(N))


M = 10 ** 9 + 7
d = {}

def f(n):
	if n <= 0:
		return 1
	if n == 1:
		return 2
	if n == 2:
		return 3
	if n == 3:
		return 4
	if n in d:
		return d[n]
	t1 = f(n // 2 - 1)
	t2 = f(n // 2 - 2)
	t3 = f(n // 2 - 3)
	if n % 2 == 0:
		d[n] = (t1 * t1 + 2 * t2 * t3) % M
	else:
		d[n] = (t2 * t2 + 2 * t3 * t1 + t1 * t1) % M
	return d[n]
T = input()
for _ in range(int(T)):
	N = int(input())
	print(f(N))


M = 10 ** 9 + 7
d = {}

def f(n):
	if n <= 0:
		return 1
	if n == 1:
		return 2
	if n == 2:
		return 3
	if n == 3:
		return 4
	if n in d:
		return d[n]
	t1 = f(n // 2 - 1)
	t2 = f(n // 2 - 2)
	t3 = f(n // 2 - 3)
	if n % 2 == 0:
		d[n] = (t1 * t1 + 2 * t2 * t3) % M
	else:
		d[n] = (t2 * t2 + 2 * t3 * t1 + t1 * t1) % M
	return d[n]
T = input()
for _ in range(int(T)):
	N = int(input())
	print(f(N))


M = 10 ** 9 + 7
d = {}

def f(n):
	if n <= 0:
		return 1
	if n == 1:
		return 2
	if n == 2:
		return 3
	if n == 3:
		return 4
	if n in d:
		return d[n]
	t1 = f(n // 2 - 1)
	t2 = f(n // 2 - 2)
	t3 = f(n // 2 - 3)
	if n % 2 == 0:
		d[n] = (t1 * t1 + 2 * t2 * t3) % M
	else:
		d[n] = (t2 * t2 + 2 * t3 * t1 + t1 * t1) % M
	return d[n]
T = input()
for _ in range(int(T)):
	N = int(input())
	print(f(N))


M = 10 ** 9 + 7
d = {}

def f(n):
	if n <= 0:
		return 1
	if n == 1:
		return 2
	if n == 2:
		return 3
	if n == 3:
		return 4
	if n in d:
		return d[n]
	t1 = f(n // 2 - 1)
	t2 = f(n // 2 - 2)
	t3 = f(n // 2 - 3)
	if n % 2 == 0:
		d[n] = (t1 * t1 + 2 * t2 * t3) % M
	else:
		d[n] = (t2 * t2 + 2 * t3 * t1 + t1 * t1) % M
	return d[n]
T = input()
for _ in range(int(T)):
	N = int(input())
	print(f(N))