Expected Node Visitation in Randomized DFS

Nauuo has constructed a search tree \(T\) of \(n\) nodes numbered from \(1\) to \(n\) (node \(1\) is the root). For any node, its depth is defined as the number of nodes on the simple path from the root to that node.

The following pseudo-code describes a depth-first search (DFS) algorithm with an optimal pruning condition:

answer \(:=\; \infty\)
procedure dfs(node, depth):
if (node is leaf) then
answer (:=; min(answer, depth)
return
if (depth < answer) then
for each child of node:
dfs(child, depth + 1)
dfs(1, 1)

</p>

The program traverses the tree in DFS order. When a leaf is visited, the global answer is updated to that leaf's depth. The pruning rule is: when a node is reached with a depth equal to the current answer, its children will not be further explored.

However, Nauuo does not know the order in which a node's children will be visited; she assumes that every ordering is equally likely. In other words, if node \(i\) has \(d_i\) children then all \(d_i!\) orders are equiprobable.

Your task is to compute the expected number of nodes visited by the DFS (including the node where the DFS call occurs even if its subtree is not expanded because of pruning). It can be proved that the answer can be written as an irreducible fraction \(\frac{p}{q}\). To avoid floating point errors, output an integer \(x\) \((0 \le x < 998244353)\) such that \[ q x \equiv p \pmod{998244353}. \]

Tree Generation:

• The first line contains an integer \(n\) \((1 \le n \le 10^5)\), the number of nodes in the tree.
• The second line contains \(n-1\) space‐separated integers. For \(i = 2, 3, \dots, n\), the \(i\)th integer is the parent of node \(i\). It is guaranteed that these edges form a tree with node \(1\) as the root.

Explanation:

Let a node \(u\) have \(k\) children. Suppose that among these children, \(L\) are leaves and the remaining \(k-L\) are internal nodes. When DFS is performed on node \(u\) (with the DFS call made in "full mode" i.e. when the parent’s depth is less than the current answer), all children are visited. However, if a leaf is encountered among the children then the DFS call for all children that appear after the first leaf is pruned (i.e. only the node itself is counted, without further recursion). For an internal (non-leaf) child \(v\), if its DFS call is performed in full mode, let \(F(v)\) be the number of nodes that would be visited in the subtree rooted at \(v\); if it is pruned the call returns 1 (since the node \(v\) is visited but not expanded). One may show that the expected full DFS visitation count \(F(u)\) (when the DFS call is not pruned at node \(u\)) satisfies \[ F(u) = \begin{cases} 1, & \text{if } u \text{ is a leaf},\\ 1 + k + \frac{1}{L+1} \sum_{v \in \{\text{non-leaf children of } u\}} (F(v)-1), & \text{otherwise}. \end{cases} \] The answer to output is \(F(1)\) as calculated modulo \(998244353\), by finding \(x\) such that \((q)x \equiv p\) modulo \(998244353\) (which is equivalent to outputting the rational number \(F(1)\) in the finite field \(\mathbb{F}_{998244353}\)).

inputFormat

The first line contains a single integer \(n\) (the number of nodes).

The second line contains \(n-1\) integers \(p_2, p_3, \dots, p_n\), where \(p_i\) is the parent of node \(i\) (\(1 \le p_i < i\)).

It is guaranteed that the given input forms a tree with node \(1\) as the root.

outputFormat

Output a single integer \(x\) \((0 \le x < 998244353)\) such that if the expected number of visited nodes is represented as \(\frac{p}{q}\) in lowest terms, then \(q\,x \equiv p \pmod{998244353}\).

sample

3
1 1

3

</p>