Solve the programming task below in a Python markdown code block.
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