Score : $600$ points

Problem Statement

We have a rooted tree with $N$ vertices numbered $1,2,\dots,N$. The tree is rooted at Vertex $1$, and the parent of Vertex $i \ge 2$ is Vertex $P_i(. For each integer$k=1,2,\dots,N$, solve the following problem:

There are $2^{k-1}$ ways to choose some of the vertices numbered between $1$ and $k$ so that Vertex $1$ is chosen. How many of them satisfy the following condition: the subgraph induced by the set of chosen vertices forms a perfect binary tree (with $2^d-1$ vertices for a positive integer $d$) rooted at Vertex $1$? Since the count may be enormous, print the count modulo $998244353$.

Constraints

• All values in input are integers.
• $1 \le N \le 3 \times 10^5$
• $1 \le P_i < i$

Input

Input is given from Standard Input in the following format:

$N$

$P_2$ $P_3$ $\dots$ $P_N$

Output

Print $N$ lines. The $i$-th ($1 \le i \le N$) line should contain the answer as an integer when $k=i$.

10
1 1 2 1 2 5 5 5 1

1
1
2
2
4
4
4
5
7
10

The following ways of choosing vertices should be counted:

• $\{1\}$ when $k \ge 1$
• $\{1,2,3\}$ when $k \ge 3$
• $\{1,2,5\},\{1,3,5\}$ when $k \ge 5$
• $\{1,2,4,5,6,7,8\}$ when $k \ge 8$
• $\{1,2,4,5,6,7,9\},\{1,2,4,5,6,8,9\}$ when $k \ge 9$
• $\{1,2,10\},\{1,3,10\},\{1,5,10\}$ when $k = 10$

1

1

If $N=1$, the $2$-nd line of the Input is empty.

10
1 2 3 4 5 6 7 8 9

1
1
1
1
1
1
1
1
1
1

13
1 1 1 2 2 2 3 3 3 4 4 4

1
1
2
4
4
4
4
4
7
13
13
19
31