Problem Background

A light rain has started to fall from the sky. By the time I return home in the evening, I push open the courtyard gate and see a carpet of petals on the ground. With the recent days of petal fall, the tree now has very few petals left. Picking up a petal from the ground, my dry eyes instantly fill with tears, which slide down my cheeks. I wonder if what falls on the petals is rain or tears...

Problem Description

Looking at the flowers on the tree: a flower has $n$ petals, connected by $n-1$ edges, and all petals are interconnected.

As spring departs, the petals on the tree begin to fall. Specifically, each day, an edge is chosen uniformly at random from the unbroken edges to be severed.

When the degree of each petal is no more than 2, we say that the flower has withered.

How many days is the expected time for a flower to wither?

Input Format

The first line contains a positive integer $n$, representing the number of petals.

The second line contains $n-1$ positive integers $f_2, \dots, f_n$, indicating that there is an edge between petal $f_i$ and petal $i$.

Output Format

A single line containing a positive integer, representing the expected withering time of a flower, modulo $985661441$ (which is a prime number).

If you do not know how to perform modular arithmetic with fractions, please refer to this problem.

Sample Input and Output

Sample Input #1

4
1 2 2

Sample Output #1

1

Sample Input #2

5
1 1 2 2

Sample Output #2

739246082

Sample Input #3

19
1 2 3 4 5 6 1 8 9 10 11 12 1 14 15 16 17 18

Sample Output #3

246415365

Sample Input #4

49
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 3 11 13 13 15 1 21 7 20 16 4 3 11 11 24 24 31 33 29 24 21 22 12 27 18 37 25 28 26 22 36 38 29

Sample Output #4

587033383

Notes

[Sample 1 Explanation]

It can be observed that no matter which edge is severed first, the flower will wither, so the expected withering time is $1$.

[Sample 2 Explanation]

If the first edge severed is $(1,2)$ or $(2,4)$ or $(2,5)$, the withering time is $1$; if the first edge severed is $(1,3)$, the withering time is $2$. Therefore, the expected withering time is $\frac{3}{4} \times 1 + \frac{1}{4} \times 2 = \frac{5}{4}$.

[Data Range and Constraints]

This problem uses batched testing.

• Subtask 1 (1 point): $f_i = i-1$.
• Subtask 2 (12 points): $n \leq 8$.
• Subtask 3 (12 points): $n \leq 18$.
• Subtask 4 (8 points): $f_i = 1$.
• Subtask 5 (16 points): Only the degree of node 1 is greater than 2.
• Subtask 6 (13 points): $n \leq 50$.
• Subtask 7 (13 points): $n \leq 100$.
• Subtask 8 (13 points): $n \leq 500$.
• Subtask 9 (12 points): No special restrictions.

For $100\%$ of the data, $1 \leq n \leq 5 \times 10^3$, $f_i < i$.

见题面 Input 部分

见题面 Output 部分