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
dist = range(1000000)
dist[0] = 1
dist[1] = 2
dist[2] = 4
for i in xrange(3 , 1000000):
	dist[i] = (dist[i-1] + dist[i-2] + dist[i-3])%1000000007	


t = int(raw_input())
for _ in xrange(0,t):
	n = int(raw_input())
	print dist[n-1]