|| ||Code Submission Evaluation System
HIIT Open 2016
Tasks | Messages | Scoreboard | Statistics
CSES - HIIT Open 2016 - Kaaleppi's puzzleCSES - 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$.
The first input line contains an integer $t$: the number of test cases.
After this, $t$ lines follow. Each line contains an integer $n$.
For each test case, output the number of solutions for Kaaleppi's puzzle modulo $10^9+7$.
- $1 \le t \le 20$
- $1 \le n \le 1000$