All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Given N, count how many permutations of [1, 2, 3, ..., N] satisfy the following property.
Let P1, P2, ..., PN denote the permutation. The property we want to satisfy is that there exists an i between 2 and n-1 (inclusive) such that
- Pj > Pj + 1 ∀ i ≤ j ≤ N - 1.
- Pj > Pj - 1 ∀ 2 ≤ j ≤ i.
First line contains T, the number of test cases. Each test case consists of N in one line.
For each test case, output the answer modulo 109+7.
- 1 ≤ T ≤ 100
- 1 ≤ N ≤ 109
- Subtask #1(40 points): 1 ≤ N ≤ 1000
- Subtask #2(60 points): original constraints
Input: 2 2 3 Output: 0 2
Test case 1:
No permutation satisfies.
Test case 2:
Permutations [1, 3, 2] and [2, 3, 1] satisfy the property.
|Tags||combinatorics, darkshadows, easy, fast-expo, nov16|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.