Valentine's Day '18 S4 - Coastal California Cities

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type

Carol is going to a California internship this summer, so she needs to be prepared to travel. She asked Cactus for help, but the only thing she received was a very bad map. The map lists the N-1 edges that connect the N cities of North America. However, they are not labelled by name. Carol knows that to read the map properly, she must assign a unique label to each node, an integer from 1 to N. However, Carol knows that for every subtree in the tree, the difference between the maximum label and the minimum label is as small as possible. Count the number of labellings of the tree which satisfy this condition, mod 10^9+7.

Constraints

1 \le N \le 200\,000

Input Specification

The first line will contain N, the number of cities.

The next N-1 lines will each contain an integer p_i, the parent of the i^\text{th} node.

The root of the tree is 0.

Output Specification

Output a single integer, the answer to the problem mod 10^9+7.

Sample Input

10
0
0
2
0
0
1
2
7
4

Sample Output

5760

Comments

There are no comments at the moment.