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
a = 100010 *[0]
a[0], a[1], a[2] = 1, 1, 2
for i in range(3,50010):
   	a[i] = a[i-1] + a[i-2] + a[i-3]
done = False   	
for _ in xrange(int(raw_input())):
	n = int(raw_input())
	if n > 50000 and not done:
		for i in range(50000, 100010):
			a[i] = a[i-1] + a[i-2] + a[i-3]
		done = True	
	print a[n] % 1000000007