**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

- 1 \le t \le 20
- 1 \le n \le 1000

# Example

Input:

3 4 9 123

Output:

2 47622 554938841