import operator

ten = len('aaaaaaaaaa')
nine = len('aaaaaaaaa')
seven = len('aaaaaaa')
two = len('aa')
one = len('a')
zero = len('')
mod = pow(ten, nine) + seven

def compute(n, mod):
    if n == zero:
        return (two.__mod__(mod), one.__mod__(mod), one.__mod__(mod))
    k = n // two
    a, b, s = compute(k, mod)
    if n.__mod__(two) == zero:
        l_n = (operator.mul(a, a) - operator.mul(two, s)).__mod__(mod)
        l_n_plus_1 = (operator.mul(a, b) - s).__mod__(mod)
        new_sign = one.__mod__(mod)
    else:
        l_n = (operator.mul(a, b) - s).__mod__(mod)
        l_n_plus_1 = (operator.mul(b, b) - operator.mul(two, (-s))).__mod__(mod)
        new_sign = (-one).__mod__(mod)
    return (l_n, l_n_plus_1, new_sign)

T = int(input())
for _ in range(T):
    N = int(input())
    res, _, _ = compute(N, mod)
    print(res)