#13204Count these Permutations

★★★★

時間限制：2000 毫秒記憶體限制：64 MB

Let ⌊x⌋ be the floor of x. Count the number of permutations (a₁, a₂, . . . , a_n) of (1, 2, . . . , n) such that

|a₁-1| + |a₂-2| + ... + |a_n-n| = ⌊n²/2⌋

A number of of inputs (≤ 1000), each start with the number of value of integer n (1 ≤ n ≤ 1000000).

Output the number of permutations modulo 1000000007.

範例輸入 1

1
2
3

範例輸出 1

1
1
3

Pro 專屬功能：查看這題在歷屆 CPE 出現過幾次 — 升級以解鎖.