Background

Original by: b2019dy, disangan233.

$gcd$ is a very vain OIer, and he has some magical mirrors.

Problem Description

$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.

Input Format

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 Format

Output the number of schemes modulo $1000000007$.

3
1 2 3

2

5
1 2 2 4 5

8

Hint

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