P6048 Optimality Pruning.

Nauuo is a problem setter. As everyone knows, some problem setters are very lazy, so “[random brute force search](https://www.luogu.com.cn/discuss/show/185420)” plus an “[optimality pruning](https://www.luogu.com.cn/discuss/show/184641)” can pass. Nauuo decides to break all these naive brute-force solutions.

Nauuo decides to break a brute-force search program, so she constructs a set of testdata. To simplify the problem, you are given the search tree $T$ generated by this testdata. $T$ contains $n$ nodes, numbered $1 \sim n$ in order, where node $1$ is the root of $T$. The depth of a node is the number of nodes on the simple path from it to node $1$. The pseudocode of this program is as follows. ```cpp answer := inf procedure dfs(node,depth) if (node is leaf) answer := min(answer,depth) return if (depth < answer) for i in children of node dfs(i,depth+1) dfs(1,1) ``` Here, `:=` denotes assignment. In plain words, this brute-force search program traverses the search tree in **depth-first** order. When it reaches a leaf node, it updates the answer using the depth of that leaf node. Meanwhile, this program has an optimality pruning. That is, when the program reaches any node whose depth equals the current answer, it will not visit this node’s children. However, poor Nauuo does not know the order in which the program visits a node’s children. Therefore, she assumes that for each node, the order of visiting its children is uniformly random among all possible orders. Clearly, there are $\prod d_i!$ possible cases in total, where $d_i$ is the number of children of node $i$. Now she wants to know the expected number of nodes visited by this program, to determine whether the program will be broken by her testdata. To avoid floating-point errors, take the answer modulo $998244353$. The answer is guaranteed to be representable as an irreducible fraction $\frac{p}{q}$. You only need to output an $x (0\leq x < 998244353)$ such that $qx \equiv p \pmod {998244353}$.

The first line contains an integer $n$. The second line contains $n-1$ integers $p_2, p_3 \cdots p_n$, where $p_i$ is the index of the parent of node $i$.

One line with an integer, the required $x$.

#### Sample Explanation For the first sample, the true answer is $\frac{7}{2}$. There are only two cases in total. If node $1$ traverses node $3$ first, then the program will visit all nodes in the search tree. If node $1$ traverses node $2$ first, then node $4$ will not be visited. In the second sample, each non-leaf node has only one child, so there is only one possible case, and all nodes will definitely be visited. For the third sample, the true answer is $\frac{94}{9}$. --- #### Constraints **This problem uses bundled test cases.** For all test points, it is guaranteed that $1 \leq n \leq 3\times 10^5$, $1 \leq p_i < i$. $\text{Subtask 1 (11 pts)}$ $n \leq 9$. $\text{Subtask 2 (18 pts)}$ $n \leq 100$. $\text{Subtask 3 (19 pts)}$ $n\leq 10^3$. $\text{Subtask 4 (4 pts)}$ $p_i = i-1$. $\text{Subtask 5 (8 pts)}$ $p_i =\lfloor \frac{i}{2} \rfloor$. $\text{Subtask 6 (40 pts)}$ No special constraints. --- #### Hint If you do not know how to take a fraction modulo a number, you can refer to [here](https://www.luogu.com.cn/problem/P3811). Translated by ChatGPT 5