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

SAMPLE INPUT
2
2
3

SAMPLE OUTPUT
2
4

见题面

见题面