配点 : $600$ 点

問題文

頂点 $1$ を根とした $N$ 頂点の根付き木があります。頂点には $1,2,\ldots,N$ の番号がついています。

根から始めて深さ優先探索を行い、行きがけ順で頂点番号を記録したところ、順に $P_1,P_2,\ldots,P_N$ となりました。 ただし、深さ優先探索では、現在の頂点に複数の子がある場合、まだ探索していない頂点のうち最も番号が小さい頂点へ移動することとします。

行きがけ順とは

• 現在いる頂点 $u$ をまだ記録していなければ記録する。

• その後、$u$ の子のうち、まだ探索していないものがあればその頂点に移動する。

• そうでない時、$u$ が根であれば探索を終了する。そうでなければ、$u$ の親に移動する。

条件をみたす根付き木として考えられるものの数を $998244353$ で割った余りを求めてください。 ただし、ある $2$ つの「頂点 $1$ を根とした $N$ 頂点の根付き木」が異なるとは、ある根以外の頂点が存在して、その親が異なる事を言います。

制約

• $2 \leq N \leq 500$
• $1 \leq P_i\leq N$
• $P_1=1$
• $P_i$ はすべて異なる
• 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

$N$

$P_1$ $P_2$ $\ldots$ $P_N$

出力

条件をみたす根付き木として考えられるものの数を $998244353$ で割った余りを出力せよ。

4
1 2 4 3

3

条件をみたす根付き木としては次の $3$ 通りが考えられます。よって、 $3$ を出力します。

また、次のような木は考えられません。頂点 $2$ の子の頂点のうち、番号の小さい頂点 $3$ が頂点 $4$ より先に探索され、 このときの行きがけ順は $1,2,3,4$ となるからです。

8
1 2 3 5 6 7 8 4

202