P4871 Oiers' Mirror (mirror)

Original by: [b2019dy](https://www.luogu.org/space/show?uid=78488), [disangan233](https://www.luogu.org/space/show?uid=72679). $gcd$ is a very vain OIer, and he has some magical mirrors.

$gcd$ has $n$ objects in total, numbered $A_1, A_2, A_3 \cdots A_n$. Among these objects, some are element plates and some are mirrors. An element plate contains elements, while a mirror has no elements at the beginning. An element plate can correspond to **at most** one mirror. In that case, the mirror will carry the elements on that element plate. A mirror cannot correspond to other mirrors. You are now given the total number of objects $n$ and the number of elements each object has **after correspondence**. Please find how many different correspondence schemes there are.

The first line: an integer $n$, the total number of objects. The second line: $n$ integers, representing the final number of elements of each object.

Output the number of schemes modulo $1000000007$.

For $20\%$ of the testdata, $n \leq 5$. For $50\%$ of the testdata, $n \leq 10$. For $100\%$ of the testdata, $n \leq 15$. ## Sample Explanation Because the problem setter is too lazy, in the explanation, "(the rest) are all element plates" is abbreviated as "suki", and "correspond" is abbreviated as $\to$. ### Sample 1 * suki. * $A1, A2 \to A3$. #### The answer is: $2$. ### Sample 2 * suki. * $A2, A3 \to A4$, suki. * $A1, A4 \to A5$, suki. * $A1, A2, A3 \to A5$, suki. * $A2 \to A3$, suki. * $A2 \to A3$, $A1, A4$->$A5$. * $A3 \to A2$, suki. * $A3 \to A2$, $A1, A4$->$A5$. ### The answer is: $8$. Translated by ChatGPT 5