CSES - HIIT Open 2016 - Kaaleppi's puzzle
  • Time limit: 5.00 s
  • Memory limit: 256 MB

Kaaleppi has created the following puzzle:

Given an integer nn, construct a permutation of numbers 1,2,,n1,2,\ldots,n such that there are no adjacent values whose difference is 11.

For example, when n=4n = 4, there are 22 solutions: (2,4,1,3)(2, 4, 1, 3) and (3,1,4,2)(3, 1, 4, 2).

Your task is to calculate the number of solutions for Kaaleppi's puzzle for given nn values. The answer may be big so please output it modulo 109+710^9+7.

Input

The first input line contains an integer tt: the number of test cases.

After this, tt lines follow. Each line contains an integer nn.

Output

For each test case, output the number of solutions for Kaaleppi's puzzle modulo 109+710^9+7.

Constraints

  • 1t201 \le t \le 20
  • 1n10001 \le n \le 1000

Example

Input:

3
4
9
123

Output:

2
47622
554938841