#13204Count these Permutations

Let ⌊x⌋ be the floor of x. Count the number of permutations (a1, a2, . . . , an) of (1, 2, . . . , n) such that |a1-1| + |a2-2| + · · · + |an-n| = ⌊n2/2⌋

Input

A number of of inputs (≤ 1000), each start with the number of value of integer n (1 ≤ n ≤ 1000000).

Output

Output the number of permutations modulo 1000000007.

1
2
3

1
1
3