Let ⌊x⌋ be the floor of x. Count the number of permutations (a1,a2,...,an) of (1,2,...,n) such that |a1–1| + |a2–2| + · · · + |an–n| = ⌊n2/2⌋ A number of of inputs (≤ 1000), each start with the number of value of integer n (1 ≤ n ≤ 1000000). Output Output the number of permutations modulo 1000000007. Sample Input 1 2 3 Sample Output 1 1 3 Input