# Felipe, Juan Alfonso

MOD = 1000000007
q = int(input().rstrip())

memo = [0 for i in range(30000)]

for i in range(30000):
    if(i == 0 or i == 1):
        ans = 1
    elif(i == 2):
        ans = 2
    elif(i > 2):
        ans = (memo[i-2] + memo[i-3])
    memo[i] = ans
outs = []

for i in range(q):
    n = int(input().rstrip())
    outs.append(memo[n] % MOD)

print("{}".format("\n".join(list(map(str,outs)))))