Ever since Mingming learned about tree structures, he has developed a keen interest in trees of all shapes and sizes. After drawing many different trees, he came up with a question: given $n$ nodes labeled from $1$ to $n$, and allowing arbitrary connections between any two nodes, how many different trees with $n$ nodes can be formed in total? While working on this problem, he thought of another, more general question: given $n$ nodes labeled from $1$ to $n$ and the required degrees for some of these nodes, and allowing arbitrary connections between any two nodes, how many different trees with $n$ nodes can be formed such that the degrees of the nodes satisfy the given requirements?

Mingming pondered this for a long time but could only manually calculate a few simple cases. As a beginner in programming, he does not know how to write a program to solve this problem. Therefore, he is turning to you, who are preparing for NOI2008, to help him solve it.

Input

The first line contains an integer $n$, representing the number of nodes in the tree. The next $n$ lines represent the required degrees for nodes $1$ through $n$ respectively. The $(i+1)$-th line represents the required degree $D_i$ for node $i$. If the value is $-1$, it means there is no requirement for the degree of node $i$. The input data guarantees $0 < n \le 1000$ and $-1 \le D_i < n$.

Output

Contains a single integer representing the number of different trees that can be drawn. If there is no solution, output $0$.

Examples

Input 1

3
1
-1
-1

Output 1

2