Roy has played a lot of Mario that he got bored of playing it again and again. So now he wants to design a stage of Mario game.

Right now he is simply designing a group of walls using bricks that little Mario has to cross over. Little Mario cannot jump more than 3 bricks' height, so Roy cannot create a wall of height more than 3.

Roy has N number of bricks. Roy wants to make a group of walls such that height of no single wall exceeds 3.

For example if N = 8, one of the group of walls can be as follows:

Now Roy wonders how many different groups of walls can he generate for a given number of bricks.
(See Sample Test Case Explanation for clarification)

Input:
First line contains integer T, number of Test Cases. 
Next T lines each will contain integer N, number of bricks Roy has.

Output:
Print an integer in new line for each test case, number of different groups of walls.

Since answer can be very large, print it modulo 1000000007

Constraints:
1 ≤ T ≤ 10
1 ≤ N ≤ 100000

Sample Test Case Explanation:  For N = 3SAMPLE INPUT
1
3

SAMPLE OUTPUT
4
'''
Created on Oct 31, 2014

@author: aksam
'''

mod = 10 ** 9 + 7
test = int(input())
for i in range(test):
    n = int(input())
    t1 = 1
    t2 = 2
    t3 = 4
    if n == 1:
        print(t1)
    elif n == 2:
        print(t2)
    elif n == 3:
        print(t3)
    else:
        result = 0
        for j in range(n - 3):
            result = (t1 + t2 + t3) % mod
            t3, result = result, t3
            t2, result = result, t2
            t1, result = result, t1
        print(t3)