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.

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = 'from typing import List\r\nMatrix = List[List[int]]\r\n\r\nMOD = 10 ** 9 + 7\r\n\r\n\r\ndef identity(n: int) -> Matrix:\r\n    matrix = [[0] * n for _ in range(n)]\r\n\r\n    for i in range(n):\r\n        matrix[i][i] = 1\r\n\r\n    return matrix\r\n\r\n\r\ndef multiply(mat1: Matrix, mat2: Matrix, copy: Matrix) -> None:\r\n    r1, r2 = len(mat1), len(mat2)\r\n    c1, c2 = len(mat1[0]), len(mat2[0])\r\n\r\n    result = [[0] * c2 for _ in range(r1)]\r\n\r\n    for i in range(r1):\r\n        for j in range(c2):\r\n            for k in range(r2):\r\n                result[i][j] = (result[i][j] + mat1[i][k] * mat2[k][j]) % MOD\r\n\r\n    for i in range(r1):\r\n        for j in range(c2):\r\n            copy[i][j] = result[i][j]\r\n\r\n\r\ndef power(mat: Matrix, n: int) -> Matrix:\r\n    res = identity(len(mat))\r\n\r\n    while n:\r\n        if n & 1:\r\n            multiply(res, mat, res)\r\n\r\n        multiply(mat, mat, mat)\r\n\r\n        n >>= 1\r\n\r\n    return res\r\n\r\n\r\ndef fib(n: int) -> int:\r\n    if n == 0:\r\n        return 0\r\n\r\n    magic = [[2, 1],\r\n             [2, 0]]\r\n\r\n    mat = power(magic, n)\r\n\r\n    return mat[0][0]\r\n\r\nfor _ in range(int(input())):\r\n    n = int(input())\r\n\r\n    print(fib(n) % MOD)\r\n'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 18167