Description

Ever since Mingming learned about tree structures, he has become interested in unusual trees.

Given nodes labeled $1$ to $N$, and the final degrees of some nodes, you may add edges between any pair of nodes. How many trees can be formed whose degrees meet the given requirements?

Input Format

The first line contains a positive integer $N$ ($0 < N \le 1000$).

The next $N$ lines: the $(i+1)$-th line contains a positive integer representing the degree $D_i$ of the $i$-th node. If the degree is unconstrained, input -1.

Output Format

Output a single positive integer on one line, the number of different trees that satisfy the requirements. If there is no solution, output $0$.

3
1
-1
-1

2

Hint

The two trees are 1-2-3 and 1-3-2.

Translated by ChatGPT 5