We all know fibonnaci numbers.similarly we also have tribonnaci numbers whose first few terms is given as 0,1,1,2,4,7...
First line of input contains T(number of test cases)
Next T lines contain a number N.
For each test cases,output Nth tribonnaci number in a separate line.Since Nth term can be very large,output result modulo 1000000007
Problem Setter:Abhishek Sanghai