A - A special permutation

Time limit: 2 s
Memory limit: 256 MiB
Languages: C, C++, Java, Python, ... (details)

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$.

Input

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$).

Output

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

Sample test(s)

Input
4 2 3 4 10
Output
1 3 10 454030

Hints

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