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