Code Submission Evaluation System Login

HIIT Open 2016

Start:2016-05-28 11:00:00
End:2016-05-28 16:00:00
 

Tasks | Messages | Scoreboard | Statistics


CSES - HIIT Open 2016 - Kaaleppi's puzzle

Kaaleppi's puzzle

Time limit:5.00 s
Memory limit:256 MB

Kaaleppi has created the following puzzle:

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

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

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

Input

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

After this, $t$ lines follow. Each line contains an integer $n$.

Output

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

Constraints
Example

Input:
3
4
9
123


Output:
2
47622
554938841