## A Tree Problem

View as PDF

Points: 25 (partial)
Time limit: 0.6s
Memory limit: 162M

Problem types

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

#### Constraints

In test data worth 30% of marks, you may assume .

#### Input Specification

The first line contains a single positive integer, .

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

#### Output Specification

Output the number of distinct spanning trees.

#### Sample Input

3
-1
-1
1

#### Sample Output

2