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
dp={1:1,2:2,3:4}
def ans(n):
    if n in dp:
        return dp[n]
    else:
        l=[]
        l.append(1)
        l.append(2)
        l.append(4)
        for i in range(4,n+1):
        	if i not in dp:
        		l.append(l[i-2]+l[i-3]+l[i-4])
        		dp[i]=l[i-2]+l[i-3]+l[i-4]
        	else:
        		l.append(dp[i])
        dp[n]=l[n-1]
        return l[n-1]
tc=int(input())
while tc>0:
    n=int(input())
    a=ans(n)
    print(a%(1000000007))
    tc=tc-1