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

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.