伝説によれば、夜の国には $n$ 個の頂点を持つ虹の木があります。虹の木は根付き木で、頂点には $0\sim n-1$ の番号が付いています。頂点 $0$ が根であり、頂点 $i$（$1\le i<n$）の親は頂点 $f_i$ です。

虹の木の各頂点は、どんな色でも表せます。色は無限にありますが、虹の木の彩りは、各部分木に現れる異なる色の数だけで決まり、具体的な色には依存しません。具体的には、頂点 $i$（$0\le i<n$）を根とする部分木に $c_i$ 種類の異なる色の頂点があるとすると、虹の木の彩りは列 $[c_0,c_1,\ldots,c_{n-1}]$ で表されます。例えば下図では、頂点 $0,1,5$ が青、頂点 $2,4$ が赤、頂点 $3$ が黄なので、虹の木の彩りは $[3,2,1,2,1,1]$ です。

雲の変化によって、虹の木の色にはある特定の規則が現れます。具体的には、各規則は頂点の部分集合 $S\subseteq\{1,2,\ldots,n-1\}$ で表されます。集合 $S$ 内の各頂点 $u$ の色は、ある祖先の色と同じです。形式的には、すべての $u\in S$ について、$u$ の祖先 $p$（$p\ne u$）で、$u$ と同じ色のものが存在します。この規則による制約を受けても、虹の木はさまざまな色を表し、異なる彩りを作ることができます。規則 $S$ を満たす虹の木の彩りの種類数を $w_S$ とします。2つの彩りが異なるのは、2つの列の少なくとも1つの要素が異なる場合に限ります。

考えられるすべての $2^{n-1}$ 種類の規則について、それぞれを満たす虹の木の彩りの種類数の総和、すなわち $\sum_{S\subseteq\{1,2,\ldots,n-1\}}w_S$ を求めてください。答えは大きくなり得るので、$998\,244\,353$ で割った余りを求めてください。

実装の詳細

main 関数を実装する必要はなく、実装してはいけません。

提出するソースファイルにはヘッダーファイル rainbow.h を含めてください。すなわち、プログラムの先頭に次のコードを加えてください。

#include "rainbow.h"

提出するソースファイル rainbow.cpp に次の関数を実装してください。

int rainbow(int c, int n, std::vector<int> f);

• $c,n$ はそれぞれテスト番号と虹の木の頂点数を表します。$c=0$ は入出力例であることを表します。
• $f$ は長さ $n$ の列であり、$f_0=0$、$f_i$（$1\le i<n$）は頂点 $i$ の親を表します。
• 関数は、各規則を満たす虹の木の彩りの種類数の総和を $998\,244\,353$ で割った余りを返してください。
• 各テストについて、採点プログラムはこの関数をちょうど1回呼び出します。

問題のディレクトリ内にある template_rainbow.cpp はサンプルコードです。これを参考に自分のコードを実装してかまいません。

プログラムのテスト方法

問題のディレクトリ内で、次のコマンドを使って実行ファイルをコンパイルできます。

g++ grader.cpp rainbow.cpp -o rainbow -O2 -std=c++14 -static

生成された実行ファイル rainbow について：

• 標準入力から次の形式のデータを読み込みます。

  • 最初の行に2つの非負整数 $c,n$ が与えられます。
  • 2行目に $n-1$ 個の非負整数 $f_1,f_2,\ldots,f_{n-1}$ が与えられます。

• 標準出力に次の形式のデータを出力します。

  • rainbow 関数の戻り値を表す非負整数を1行に1つ出力します。

入出力例

入力 1

0 3
0 0

出力 1

8

注記

• 規則 $S=\varnothing$ を満たす虹の木の彩りは、$[1,1,1],[2,1,1],[3,1,1]$ の3種類です。
• 規則 $S=\{1\}$ を満たす虹の木の彩りは、$[1,1,1],[2,1,1]$ の2種類です。
• 規則 $S=\{2\}$ を満たす虹の木の彩りは、$[1,1,1],[2,1,1]$ の2種類です。
• 規則 $S=\{1,2\}$ を満たす虹の木の彩りは、$[1,1,1]$ の1種類です。

したがって、答えは $3+2+2+1=8$ です。

入力 2

0 6
0 1 0 3 1

出力 2

279

入出力例 3

選手用ディレクトリ内の rainbow/rainbow3.in と rainbow/rainbow3.ans を参照してください。

この例はテスト番号 $3,4$ の制約を満たします。

入出力例 4

選手用ディレクトリ内の rainbow/rainbow4.in と rainbow/rainbow4.ans を参照してください。

この例はテスト番号 $5\sim7$ の制約を満たします。

入出力例 5

選手用ディレクトリ内の rainbow/rainbow5.in と rainbow/rainbow5.ans を参照してください。

この例はテスト番号 $8,9$ の制約を満たします。

入出力例 6

選手用ディレクトリ内の rainbow/rainbow6.in と rainbow/rainbow6.ans を参照してください。

この例はテスト番号 $10\sim12$ の制約を満たします。

制約

すべてのテストデータについて、次を満たします。

• $1\le n\le200$。
• すべての $1\le i<n$ について、$0\le f_i<i$ です。

特別な性質 A：すべての $1\le i<n$ について、$f_i=i-1$ です。

特別な性質 B：すべての $0\le i<n$ について、$f_j=i$ を満たす $j$ は高々2つ存在します。