## MOG Round #34## Ended |

Fito is playing with permutations once again. Let $A =(A_1,\, A_2,\, \cdots,\, A_N)$ be a permutation of $(1, 2,..., N)$ with $N \geq 2$. He says that $A$ is special if and only if it satisfies that the length of the longest increasing block is at most $2$ and the elements $1$ and $N$ are inverted, that means the position of $N$ is smaller than the position of $1$. A block, in this case, refers to any sequence of elements at consecutive positions in $A$.

Your task is to help Fito counting the number of special permutations modulo $10^9+7$.

The first line of input contains an integer $1 \leq T \leq 100$ with the number of cases to solve. Each of the $T$ following lines contains an integer $N$ ($2 \leq N \leq 2000$).

For each case print one line with the number of special permutations of size $N$ modulo $10^9+7$.

Input

4
2
3
4
10

Output

1
3
10
454030

The special permutations of length 4 are:

- 3 2 4 1
- 2 4 1 3
- 2 4 3 1
- 3 4 2 1
- 3 4 1 2
- 4 1 3 2
- 4 2 1 3
- 4 2 3 1
- 4 3 1 2
- 4 3 2 1