# Enter your code here. Read input from STDIN. Print output to STDOUT
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))