Akash is feeling lonely.So he decided to visit his friend's house. His friend's house is located at the distance of K metres from his house.Now,he can take a step of one metre ,two metres or three metres at a time.Can you tell me number of ways of reaching Akash's friend house. As the answer can be large Print answer mod 1000000007

Input

First line contains an integer t denoting number of test cases
Next t lines contains an integer k

Output

Print t lines containing number of ways to to reach friend's house modulo 1000000007

Subtasks
1<=t<=15 , 1<=k<=15 (30 points)
1<=t<=10000 , 1<=k<10000 ( 20 Points)
1<=t<=100000 , 1<=k<=1000000 (50 points)