B. Grasshopper
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

A grasshopper starts at position $$$0$$$ on a number line containing the points $$$0, 1, 2, \dots, n$$$.

Each minute, the grasshopper chooses a point $$$j \in \{0,1,\dots,n\}$$$ that it has not chosen before and jumps over it. If the grasshopper is currently at position $$$i$$$ and jumps over point $$$j$$$, it lands at position $$$2j - i$$$.

After exactly $$$n+1$$$ minutes, the grasshopper has jumped over every point $$$0,1,\dots,n$$$ exactly once. It is guaranteed that after all jumps, the grasshopper returns to position $$$0$$$.

Your task is to count how many permutations of the jump-over points result in this behavior.

Input

The first line contains an integer $$$t$$$ — the number of test cases.

Each of the next $$$t$$$ lines contains a single integer $$$n$$$ $$$(2 \le n \le 75)$$$.

It is guaranteed that the sum of all values of $$$n$$$ over all test cases does not exceed $$$75$$$.

Output

For each test case, output a single integer — the number of valid orders of jump-over points modulo $$$10^9 + 7$$$.

Example
Input
4
2
3
4
8
Output
0
8
24
31680
Note
  • Each point from $$$0$$$ to $$$n$$$ must be jumped over exactly once.
  • The order of jump-over points matters.
  • Some values of $$$n$$$ may have zero valid permutations.
  • Since the answer can be large, all results are taken modulo $$$10^9 + 7$$$.

For example, when $$$n=4$$$, one valid order is: [ 0, 1, 2, 4, 3 ] After performing these jumps, the grasshopper returns to position $$$0$$$.