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
mod = 1000000007
def calculate(n):
	a = [0,1,2,4]
	for i in xrange(4,n+1):
		temp = (a[i-3]%mod+a[i-2]%mod+a[i-1]%mod)%mod
		a.append(temp)
	print a[n]%mod
	del a[:]

t = input()
for i in xrange(t):
	n = input()
	calculate(n)