Chef has a strip of length $N$ units and he wants to tile it using $4$ kind of tiles

-A Red tile of $2$ unit length

-A Red tile of $1$ unit length

-A Blue tile of $2$ unit length

-A Blue tile of $1$ unit length   
Chef is having an infinite supply of each of these tiles. He wants to find out the number of ways in which he can tile the strip. Help him find this number.
Since this number can be large, output your answer modulo 1000000007 ($10^9 + 7$).

-----Input:-----
- First line will contain $T$, number of testcases. Then the testcases follow. 
- Each testcase contains of a single line of input, an integer $N$. 

-----Output:-----
For each testcase, output in a single line your answer modulo 1000000007.

-----Constraints-----
- $1 \leq T \leq 1000$
- $2 \leq N \leq 10^{18}$

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

-----Sample Output:-----
6

-----EXPLANATION:-----

It can be seen that for a strip of length $2$, there are $6$ possible configurations.     
$NOTE : $ 2 tiles of 1 unit length are different from 1 tile of 2 unit length.

Source: codechef | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
MOD = 1000000007

def fib(n):
	F = [[2, 2], [1, 0]]
	power(F, n - 1)
	ans = [6, 2]
	return (F[0][0] * 6 + F[0][1] * 2) % MOD

def multiply(F, M):
	x = (F[0][0] * M[0][0] + F[0][1] * M[1][0]) % MOD
	y = (F[0][0] * M[0][1] + F[0][1] * M[1][1]) % MOD
	z = (F[1][0] * M[0][0] + F[1][1] * M[1][0]) % MOD
	w = (F[1][0] * M[0][1] + F[1][1] * M[1][1]) % MOD
	F[0][0] = x
	F[0][1] = y
	F[1][0] = z
	F[1][1] = w

def power(F, n):
	if n == 0 or n == 1:
		return
	M = [[2, 2], [1, 0]]
	power(F, n // 2)
	multiply(F, F)
	if n % 2 != 0:
		multiply(F, M)
for _ in range(int(input())):
	n = int(input())
	ans = 1
	if n == 0:
		ans = 1
	elif n == 1:
		ans = 2
	elif n == 2:
		ans = 6
	else:
		ans = fib(n - 1)
	print(ans)


from typing import List
Matrix = List[List[int]]
MOD = 10 ** 9 + 7

def identity(n: int) -> Matrix:
	matrix = [[0] * n for _ in range(n)]
	for i in range(n):
		matrix[i][i] = 1
	return matrix

def multiply(mat1: Matrix, mat2: Matrix, copy: Matrix) -> None:
	(r1, r2) = (len(mat1), len(mat2))
	(c1, c2) = (len(mat1[0]), len(mat2[0]))
	result = [[0] * c2 for _ in range(r1)]
	for i in range(r1):
		for j in range(c2):
			for k in range(r2):
				result[i][j] = (result[i][j] + mat1[i][k] * mat2[k][j]) % MOD
	for i in range(r1):
		for j in range(c2):
			copy[i][j] = result[i][j]

def power(mat: Matrix, n: int) -> Matrix:
	res = identity(len(mat))
	while n:
		if n & 1:
			multiply(res, mat, res)
		multiply(mat, mat, mat)
		n >>= 1
	return res

def fib(n: int) -> int:
	if n == 0:
		return 0
	magic = [[2, 1], [2, 0]]
	mat = power(magic, n)
	return mat[0][0]
for _ in range(int(input())):
	n = int(input())
	print(fib(n) % MOD)