Background

A light drizzle fell from the sky. By the time I got home, it was already evening. As I pushed open the courtyard gate, the ground full of petals came into view. With the petals having withered over the past few days, there were not many left on the tree. Picking up a petal from the ground, my dry eyes instantly filled with tears, and they slid down my cheeks. Falling onto the flowers, was it rain, or tears...

Problem Description

Look at the flower on the tree: one flower has $n$ petals. There are $n-1$ edges connecting the petals, and all petals are connected.

As spring leaves, the petals on the tree wither and fall. Specifically, every day, one edge is chosen uniformly at random among the edges that have not been broken yet, and that edge breaks.

When the degree of every petal is at most $2$, we say that the flower has withered.

After 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$, meaning that there is an edge between petal $f_i$ and petal $i$.

Output Format

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

If you do not know how to take a fraction modulo, please refer to this problem.

4
1 2 2

1

5
1 1 2 2

739246082

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

246415365

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

587033383

Hint

[Sample 1 Explanation]

It can be seen that no matter which edge is broken first, the flower will wither. Therefore, the expected withering time is $1$.

[Sample 2 Explanation]

If the first broken edge is $(1,2)$ or $(2,4)$ or $(2,5)$, the withering time is $1$; if the first broken edge 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}$.

[Constraints and Notes]

This problem uses bundled testdata.

• 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): There is exactly one node (node $1$) whose degree 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 testdata, $1\le n\leq 5\times 10^3$, and $f_i<i$.

Translated by ChatGPT 5