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.

Difficulty: interview

Starter code:

Solutions:
# Fibonacci Series using 
# Optimized Method 

# function that returns nth 
# Fibonacci number
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
    # return F[0][0]


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)