Our chef has been assigned a task to make a necklace of length N, from gold, diamond and platinum.There is single kind of gold, two types of diamond and three types of platinum available.
A necklace can be represented as strings of the form (G)∗(D1|D2)∗(P1|P2|P3)∗$ (G)*(D1|D2)*(P1|P2|P3)* $ where (x|y) means we can use x or y and ∗$ * $ means we can repeat the previous parenthesized expression 0 or more times.
Instead of making necklace he choose to count all such distinct necklaces possible for a given length N.

-----Input:-----
-The first line of the input contains a single integer T$T$ denoting the number of test cases. The description of T$T$ test cases follows.
-Only line of every test case contains an integer N$N$ denoting the length of the necklace required.

-----Output:-----
For each test case, print the number of all such distinct necklaces, with given length. As the number can be really large, print it modulo  109+7$10^{9}+7$.

-----Constraints-----
- 1≤T≤10000$1 \leq T \leq 10000$
- 2≤N≤1000000000$2 \leq N \leq 1000000000$
- String S$S$ consists of only upper case english alphabets.

-----Subtasks-----
- 20 points : 1≤N≤5$1 \leq N \leq 5$
- 70 points : Original$Original$ Constraints$Constraints$

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

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

```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 = "import math\r\nimport bisect\r\nimport itertools\r\nimport sys\r\nmod=10**9 +7\r\n'''fact=[1]*1001\r\nifact=[1]*1001\r\nfor i in range(1,1001):\r\n    fact[i]=((fact[i-1])*i)%mod\r\n    ifact[i]=((ifact[i-1])*pow(i,mod-2,mod))%mod\r\ndef ncr(n,r):\r\n    return (((fact[n]*ifact[n-r])%mod)*ifact[r])%mod\r\ndef npr(n,r):\r\n    return (((fact[n]*ifact[n-r])%mod))\r\n    '''\r\n'''def mindiff(a):\r\n    b=a[:]\r\n    b.sort()\r\n    m=10000000000\r\n    for i in range(len(b)-1):\r\n        if b[i+1]-b[i]<m:\r\n            m=b[i+1]-b[i]\r\n    return m\r\n    '''\r\n'''def lcm(a,b):\r\n    return a*b//math.gcd(a,b)\r\n\r\n    '''\r\n    \r\n'''def merge(a,b):\r\n    i=0;j=0\r\n    c=0\r\n    ans=[]\r\n    while i<len(a) and j<len(b):\r\n        if a[i]<b[j]:\r\n            ans.append(a[i])\r\n            i+=1\r\n        else:\r\n            ans.append(b[j])\r\n            c+=len(a)-i\r\n            j+=1\r\n    ans+=a[i:]\r\n    ans+=b[j:]\r\n    return ans,c\r\ndef mergesort(a):\r\n    if len(a)==1:\r\n        return a,0\r\n    mid=len(a)//2   \r\n    left,left_inversion=mergesort(a[:mid])\r\n    right,right_inversion=mergesort(a[mid:])\r\n    m,c=merge(left,right)\r\n    c+=(left_inversion+right_inversion)\r\n    return m,c\r\n    \r\n'''\r\n'''\r\ndef is_prime(num):\r\n    if num == 2: return True\r\n    if num == 3: return True\r\n    if num%2 == 0: return False\r\n    if num%3 == 0: return False\r\n    t = 5\r\n    a = 2\r\n    while t <= int(math.sqrt(num)):\r\n        if num%t == 0: return False\r\n        t += a\r\n        a = 6 - a\r\n    return True\r\n '''\r\na1=[2,6]\r\na2=[3,18]\r\na=[]\r\nfor i in range(100000):\r\n    a2.append(((a2[-1]+a1[-1]+1)*3)%mod)\r\n    a1.append(((a1[-1]+1)*2)%mod)\r\nfor i in range(100000):\r\n    a.append((a1[i]+a2[i]+1)%mod)\r\nt=int(input())\r\n#print(a)\r\nfor i in range(t):\r\n    n=int(input())\r\n    print(a[n- 1])"
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 12015963