Gopal is climbing the stairs. He can jump 1 or 2 or 3 steps at a time.
He wants to climb N steps. In how many ways can he reach the Nth step?
As the answer can be too large Output it modulo 10^9+7.

Input:
First line of the input contains an integer T denoting the number of test cases.
Then T lines follow each line containing an integer N.

Output:
Output the required answer in a new line for each test case.

Constraints:
1 ≤ N ≤ 10^5

Sample Input
2
3
4

Sample Output
4
7

Explanation:
Test case: 2
There 7 ways of reaching 4^th step in the stairs:-

1+1+1+1
1+1+2
1+2+1
2+1+1
1+3
3+1
2+2SAMPLE INPUT
2
3
4

SAMPLE OUTPUT
4
7
'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
num=input()

i=0
a=[None]*1000
b=[None]*100001
max=0
while(i<num):
	a[i]=input()
	if(max<a[i]):
		max=a[i]
	i=i+1

b[0]=0
b[1]=1
b[2]=2
b[3]=4

i=4
while(i<=max):
	b[i]=b[i-1]+b[i-2]+b[i-3]
	i=i+1

i=0
while(i<num):
	print(b[a[i]]%1000000007)
	i=i+1