You are given an integer N, print the Nth fibo-chachi number.

we define Nth fibo-chachi number as
f(N)=f(N-1)+f(N-3) + f(N-5)
f(0)=f(1)=f(2)=f(3)=f(4)=1

Input :
First line will contain an integer 'T' (number of test cases ).
For each test case there is an integer 'N'.

output :
for each test case print Nth Fibo-chachi number modulo 1000000007.

constraints :
1<=T<=500000
0<=N<=10000000