問題文

頂点 1 を根とする N 頂点の根付き木があり、頂点 i の親は P_i です。また、各頂点には 1 つの非負整数を書くことができます。

あなたは、まずこの木の全ての葉、すなわち子を 1 つも持たない頂点に 0 か 1 を書きます。その後、葉でない頂点全てに対し、その子の頂点に書かれた数の集合の \mathrm{mex} を書きます。

厳密には、頂点 v に書く非負整数を A_v としたとき、以下の条件を満たすようにします。

• 頂点 v が葉のとき、A_v = 0 または A_v = 1
• 頂点 v が葉でないとき、頂点 v の子を C_1,C_2,\ldots,C_M とすると、 A_v = \mathrm{mex}(\{A_{C_1},A_{C_2},\ldots,A_{C_M}\})

ただし、ある非負整数の集合 S に対し、 \mathrm{mex}(S) は S に含まれない最小の非負整数を表します。

葉の個数を L とすると、頂点への非負整数の書き方は 2^L 通りあります。k = 0,1,2,\ldots,N のそれぞれについて、 2^L 通りの書き方の中で最終的に頂点 1 に k が書かれるようなものの個数を 998244353 で割った余りを求めてください。

制約

• 1 \leq N \leq 2 \times 10^{5}
• 1 \leq P_i < i (2 \leq i \leq N)
• 入力は全て整数

小課題

1. (4 点) 葉の個数は 5 個以下
2. (8 点) P_i = 1 (2 \leq i \leq N)
3. (8 点) P_i = \lfloor \frac{i}{2} \rfloor (2 \leq i \leq N)
4. (15 点) N \leq 100
5. (25 点) N \leq 5000
6. (40 点) 追加の制約はない

入力例 1

5
1 1 2 2 

出力例 1

3
3
2
0
0
0

この入力例では、葉は頂点 3, 4, 5 です。例えば、これらにそれぞれ 0, 1, 0 を書いた場合、

• 頂点 2 の子は 頂点 4, 5 で、それぞれ 1, 0 が書かれているため、頂点 2 には \mathrm{mex}(\{0,1\}) = 2 を書きます。
• 頂点 1 の子は 頂点 2, 3 で、それぞれ 2, 0 が書かれているため、頂点 1 には \mathrm{mex}(\{0,2\}) = 1 を書きます。

よって、この場合頂点 1 に書かれる数は 1 です。

このサンプルは小課題 1,3,4,5,6 を満たします。

入力例 2

9
1 2 2 1 2 3 2 5 

出力例 2

15
15
2
0
0
0
0
0
0
0

このサンプルは小課題 1,4,5,6 を満たします。