Description

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.

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

Input Format

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

Output Format

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

4
1 1 3

499122180

3
1 2

3

13
1 1 1 3 5 4 2 3 7 4 4 6

776412285

Hint

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.

Translated by ChatGPT 5