Count the number of distinct spanning trees that exist on ~N~ labeled vertices, given that some of these vertices are restricted in their degree.

Constraints

~1 \le N \le 1000~

In test data worth 30% of marks, you may assume ~N \le 300~.

Input Specification

The first line contains a single positive integer, ~N~.

Each of the next ~N~ lines contains a single integer, ~d_i~. If ~d_i~ is -1, then there is no degree restriction on vertex ~i~. Otherwise, vertex ~i~ must have degree ~d_i~.

Output Specification

Output the number of distinct spanning trees.

Sample Input

3
-1
-1
1

Sample Output

2