407630: GYM102861 I Interactivity

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.)

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$$$.

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)$$$.

3
1 1

3

4
1 2 3

4

5
1 2 2 2

7