Background

Original by: b2019dy, disangan233

$gcd$ is a vain OIer who has some magical mirrors.

Problem Description

$gcd$ has a total of $n$ objects, numbered as $A_1, A_2, A_3 \cdots A_n$. Among these objects, there are elemental plates and mirrors. Elemental plates carry elements, while mirrors initially do not carry any elements.

An elemental plate can correspond to at most one mirror, and if it does, the mirror will carry the element from the plate.

A mirror cannot correspond to another mirror.

Given the total number of objects $n$ and the number of elements each object carries after correspondence, how many possible correspondence scenarios are there?

Input Format

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

Output Format

Output the total number of scenarios modulo $1000000007$.

Sample Input and Output

Sample Input #1

3
1 2 3

Sample Output #1

2

Sample Input #2

5
1 2 2 4 5

Sample Output #2

8

Notes

For $20\%$ of the data, $n \leq 5$.
For $50\%$ of the data, $n \leq 10$.
For $100\%$ of the data, $n \leq 15$.

Sample Explanation

Due to the author's laziness, explanations will abbreviate "(the rest) are all elemental plates" as "suki" and "correspond" as $\to$.

Sample 1

• suki.
• $A1, A2 \to A3$.

Answer: $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 \to A5$.
• $A3 \to A2$, suki.
• $A3 \to A2$, $A1, A4 \to A5$.

Answer: $8$.

见题面 Input 部分

见题面 Output 部分