|
Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana
ℹ️ We've recently migrated MOG to a new server with a different grader. As a result, some features—especially those related to submission evaluation—might not work correctly. If you encounter any issues, please report them by clicking the exclamation icon in the bottom right corner of the website.
A - A special permutation
Languages: C, C++, Java, Python, Kotlin, C#
Time & Memory limits: (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