407674: GYM102870 D Data Structure Master and Orz Pandas

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

Description

D. Data Structure Master and Orz Pandastime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

Master wang9897 is the First Data Structure Master in Xidian University. Today he is teaching some Orz Pandas to learn Link-Cut Tree (LCT). As a practice, wang9897 has given an interesting problem to the Orz Pandas.

Note that you don't need to know LCT to solve this problem.

Given a rooted tree with $$$n$$$ nodes whose root is numbered $$$1$$$. In LCT each node $$$u$$$ can be assigned one preferred child $$$v$$$. Certainly $$$v$$$ must be a child of $$$u$$$. Initially there is no preferred child assigned to each node.

Then $$$m$$$ "LCT access" operations are performed as follow. For each operation, a node $$$v$$$ is chosen from all nodes uniformly. The path from the root to $$$v$$$, $$$(v_1,v_2,\cdots,v_k)$$$ is then found, where $$$v_1 = 1$$$, and $$$v_k = v$$$. For $$$i = 1, 2, \cdots, k - 1$$$, if $$$v_i$$$ is not assigned a preferred child, or it is assigned to a preferred child which is not $$$v_{i+1}$$$, the preferred child of $$$v_i$$$ is reassigned to $$$v_{i+1}$$$.

Let $$$f(m)$$$ be the time of reassignments of preferred child in total. Master wang9897 want the Orz Pandas to calculate $$$$$$ \lim_{m\rightarrow\infty} \frac{f(m)}{m} $$$$$$

Please solve the problem so wang9897 can compare the Orz Pandas' answer to yours.

Input

There is only one test case in the input file.

The first line contains a integer $$$n$$$, the size of the tree. The second line contains $$$n-1$$$ integers $$$p_2,p_3,\cdots,p_{n-1}$$$. $$$p_i$$$ is the parent of the node $$$i$$$.

It's guaranteed that $$$1 \leq p_i \leq n \leq 10^5$$$.

Output

Output one line, containing an integer, the answer modulo $$$998244353$$$.

ExampleInput
5
1 1 2 2
Output
499122177
Note

For the sample, the answer is $$$1 / 2$$$, so $$$1 \cdot 2^{-1}$$$ should be outputed.

加入题单

上一题 下一题 算法标签: