# Define mod using allowed characters
ten = sum([True for _ in 'aaaaaaaaaa'])
nine = sum([True for _ in 'aaaaaaaaa'])
seven = sum([True for _ in 'aaaaaaa'])
mod = pow(ten, nine).__add__(seven)

# Basic numerical values
zero = sum([])
one = sum([True])
two = one.__add__(one)

# Initial matrix for Lucas sequence
initial_matrix = [
    [one, one],
    [one, zero]
]

# Vector [L(1), L(0)] = [1, 2]
vec = [one, two.__add__(zero)]

def multiply(a, b, mod_val):
    c = [[zero]*two for _ in (zero, one)]
    for i in (zero, one):
        for j in (zero, one):
            term1 = a[i][zero].__mul__(b[zero][j])
            term2 = a[i][one].__mul__(b[one][j])
            total = term1.__add__(term2)
            c[i][j] = total.__mod__(mod_val)
    return c

def matrix_pow(mat, power, mod_val):
    result = [[one if i == j else zero for j in (zero, one)] for i in (zero, one)]
    current = power
    while current > zero:
        if current.__mod__(two).__eq__(one):
            result = multiply(result, mat, mod_val)
        mat = multiply(mat, mat, mod_val)
        current = current.__floordiv__(two)
    return result

T = int(input())
for _ in (zero,)*T:
    Ni = int(input())
    if Ni == one:
        print(one.__mod__(mod))
    else:
        power = Ni.__sub__(one)
        mat = matrix_pow(initial_matrix, power, mod)
        term1 = mat[zero][zero].__mul__(vec[zero])
        term2 = mat[zero][one].__mul__(vec[one])
        total = term1.__add__(term2)
        ans = total.__mod__(mod)
        print(ans)