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⁹+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⁵

Sample Input

2
3
4

4
7

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

1+1+1+1
1+1+2
1+2+1
2+1+1
1+3
3+1
2+2