Oleana is choreographing a Falinks Formation Dance. Her Falinks is special: it has $$$n$$$ troopers in its squad. The dance follows a precise set of instructions, represented by a single permutation $$$\pi$$$, where each trooper at position $$$i$$$ moves to a new position $$$\pi _i$$$.
Chairman Rose wants to figure out the exact dance instruction (the permutation), but he has limited information! Initially, he sees the Falinks troopers standing in their standard formation: $$$\bf{1}$$$ through $$$\bf{n}$$$ in order. Then, Oleana commands her Falinks to perform the dance repeatedly, applying $$$\pi$$$ over and over. After each execution of the dance, she tells Chairman Rose how many troopers are back in their original positions.
Chairman Rose, being a little silly, accidentally spills coffee on his notes! Now he can only read the first $$$\lfloor n/2\rfloor$$$ recorded values.
Help Chairman Rose determine the number of possible Formation Dances (permutations) that Oleana could have chosen. Since this number can be large, return the answer modulo $$$10^9+7$$$.
The first line contains one integer $$$2 \leq n \leq 10^5$$$.
The second contains $$$\lfloor n/2\rfloor$$$ integers $$$0 \leq p_i \leq n$$$, the number of Falinks troopers that return to their original position after $$$i$$$ permutations by $$$\pi$$$.
The input is guaranteed to be valid.
Return a single integer mod $$$10^9 + 7$$$, the number of different possible dance instructions (permutations) Oleana could have picked to be $$$\pi$$$.
31
3
51 5
15
In the first test case, there are 6 possible permutations of length 3: (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), and (3, 2, 1). We know that exactly one trooper returned to their original position on the first dance instruction. This corresponds to exactly the permutations (1, 3, 2), (2, 1, 3), and (3, 2, 1).
