题目描述

我们有一个有根树，其中的顶点编号为$1,2,\dots,N$。
该树以顶点$1$为根，顶点$i \ge 2$的父节点是顶点$P_i(<i)$。
对于每个整数$k=1,2,\dots,N$，求解以下问题：

选择位于$1$和$k$之间编号的一些顶点，使得顶点$1$被选择的方式有$2^{k-1}$种。
有多少种方式满足以下条件：由选定顶点集合形成的子图是以顶点$1$为根的完全二叉树（其中$d$是正整数，对应该完全二叉树的顶点数为$2^d-1$）？
由于计数可能非常大，将结果对$998244353$取模后输出。

什么是诱导子图？

设$S$是图$G$的顶点集的子集。由该顶点集$S$诱导出的子图$H$的构造如下：

• $H$的顶点集等于$S$。

• 然后，我们按照以下方式向$H$添加边：

• 对于在$S$中的所有顶点对$(i, j)$，满足$i,j \in S, i < j$，如果$G$中存在连接$i$和$j$的边，则将顶点$i$和$j$之间添加一条边到$H$中。

什么是完全二叉树？完全二叉树是满足以下条件的有根树：

• 非叶节点每个都恰好有$2$个孩子。
• 所有叶节点到根的距离相等。

在这里，我们还将只有$1$个顶点和$0$条边的图视为完全二叉树。

约束条件

• 输入中的所有值都是整数。
• $1 \le N \le 3 \times 10^5$
• $1 \le P_i < i$

---

输入

输入遵循以下格式，从标准输入中给出：

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

输出

输出 $N$ 行。第 $i$ 行（$1 \le i \le N$）应包含当 $k=i$ 时的整数答案。

---

示例输入 1

10
1 1 2 1 2 5 5 5 1

示例输出 1

1
1
2
2
4
4
4
5
7
10

应计数以下选择顶点的方式：

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

---

示例输入 2

1

示例输出 2

1

如果 $N=1$，则输入的第 $2$ 行为空。

---

示例输入 3

10
1 2 3 4 5 6 7 8 9

示例输出 3

1
1
1
1
1
1
1
1
1
1

---

示例输入 4

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

示例输出 4

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