407630: GYM102861 I Interactivity

Memory Limit:1024 MB Time Limit:0 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

I. Interactivitytime limit per test0.25 secondsmemory limit per test1024 megabytesinputstandard inputoutputstandard output

One day, Alice challenged Bob with the interactive programming problem described below.

—————–$$$≀≀$$$—————–

You have a tree (an acyclic connected graph). Each node of the tree has exactly one parent, except the root node, which has no parent. Nodes that are not parents of any nodes are called leaves. You know the structure of the tree, because you know the parent of each node that is not the root.

Each node contains an integer value. A node that is not a leaf contains the sum of the values of all its direct children. Thus, all the values in the tree are determined by the values contained in the leaves.

The picture below depicts an example. The leaves are marked as gray, while the other nodes are white. Each node shows the value it contains.

Initially, you don't know any of the node values, but you can query them one by one. Your task is to figure out the value of each node in the tree, making as few queries as possible.

—————–$$$≀≀$$$—————–

Bob solved this problem very easily. Then, to spice things up, Alice asked him: "given the tree structure, how many different solutions to this problem exist?" That is, how many different minimal sets of queries exist that allow one to figure out all the values stored in the tree? (Two sets of queries are considered different if and only if there is a node that is queried in one set but not in the other.)

Input

The tree has $$$N$$$ nodes in total. Each node is identified by an integer between $$$1$$$ and $$$N$$$, where node $$$1$$$ is the root.

The input consists of two lines. The first line contains only the integer $$$N$$$.

The second line contains $$$N-1$$$ integers $$$P_1, P_2, \ldots, P_{N-1}$$$, separated by a single space, where $$$P_i$$$ is the parent of node $$$i + 1$$$, for $$$i = 1, 2, \ldots, N - 1$$$.

$$$2 \le N \le 10^5$$$.

$$$1 \le P_i \le N$$$, for $$$i = 1, 2, \ldots, N - 1$$$.

Output

The output consists of a single line, which must contain the number of different minimal solutions to the problem faced by Bob. As this number may be large, your answer must be calculated mod $$$1000000007$$$ $$$(10^9 + 7)$$$.

ExamplesInput
3
1 1
Output
3
Input
4
1 2 3
Output
4
Input
5
1 2 2 2
Output
7

加入题单

上一题 下一题 算法标签: