Mock CCO '19 Contest 1 Problem 5 - 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