All Submissions


Problem Statement
We all know fibonnaci numbers.similarly we also have tribonnaci numbers whose first few terms is given as 0,1,1,2,4,7...

Input
First line of input contains T(number of test cases)
Next T lines contain a number N.

Output
For each test cases,output Nth tribonnaci number in a separate line.Since Nth term can be very large,output result modulo 1000000007

Constraints
T<=100
N<=10^10

Sample Input


5
1
2
3
4
5


Sample Output


0
1
1
2
4

Problem Setter:Abhishek Sanghai

Languages: C,C++,Java

Time Limit: 1 Second(s)
Score: 100 Point(s)
Input File Limit: 50000 Bytes

Submit

Login to post clarification.

No Clarifications.

Contest

Mode Judge

Passive

Online

Overall Rankings

RankNameScore
1xyz0
2Ams0
3TIP0
4team420
5xyzz0
6asdasdasd0
7abcd0
8khankhan0
9Gabriel0
10gigel0