AGRADE - The Chain Reaction
Aayush enters the Algorithms class late. His teacher is angry with him, so in order to punish him he asks him to solve a problem. In case Aayush is not able to solve the problem his current A grade will be converted into B. The problem statement is - "Given the below recursive function he needs to figure out how many times the given function will call itself". Help him save his grade.
f(n) { if n <= 2 return 1 else return f(n - 1) * f(n - 2) * f(n - 3) }
Input
First line contains the number of test cases T. T lines follow each containing an integer N.
Output
One result for each test case equal to the number of recursive function calls. Each output in new line. As the result could be very large print it modulo 10^9 + 7.
Constraints
1 <= T <= 1000
1 <= N <= 10^15
Example
Input: 3 2
3
4
Output: 0
3
6
Added by: | Apurv Singhal |
Date: | 2012-09-11 |
Time limit: | 0.100s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |
Resource: | QUIZ'01 2012,BITS Pilani |