AT_abc252_g [ABC252G] Pre-Order

[problemUrl]: https://atcoder.jp/contests/abc252/tasks/abc252_g 頂点 $ 1 $ を根とした $ N $ 頂点の根付き木があります。頂点には $ 1,2,\ldots,N $ の番号がついています。 根から始めて深さ優先探索を行い、行きがけ順で頂点番号を記録したところ、順に $ P_1,P_2,\ldots,P_N $ となりました。 ただし、深さ優先探索では、現在の頂点に複数の子がある場合、まだ探索していない頂点のうち最も番号が小さい頂点へ移動することとします。 行きがけ順とは 根から始めて次の手順を繰り返して根付き木上の頂点を列挙します。 2. 現在いる頂点 $ u $ をまだ記録していなければ記録する。 3. その後、$ u $ の子のうち、まだ探索していないものがあればその頂点に移動する。 4. そうでない時、$ u $ が根であれば探索を終了する。そうでなければ、$ u $ の親に移動する。 この時、列挙された頂点を順に並べたものが行きがけ順です。 条件をみたす根付き木として考えられるものの数を $ 998244353 $ で割った余りを求めてください。 ただし、ある $ 2 $ つの「頂点 $ 1 $ を根とした $ N $ 頂点の根付き木」が異なるとは、ある根以外の頂点が存在して、その親が異なる事を言います。

N/A

N/A

### 制約 - $ 2\ \leq\ N\ \leq\ 500 $ - $ 1\ \leq\ P_i\leq\ N $ - $ P_1=1 $ - $ P_i $ はすべて異なる - 入力は全て整数 ### Sample Explanation 1 条件をみたす根付き木としては次の $ 3 $ 通りが考えられます。よって、 $ 3 $ を出力します。 !\[\](https://img.atcoder.jp/abc252/554e2b202029960276be7564aaa0576b.png) また、次のような木は考えられません。頂点 $ 2 $ の子の頂点のうち、番号の小さい頂点 $ 3 $ が頂点 $ 4 $ より先に探索され、 このときの行きがけ順は $ 1,2,3,4 $ となるからです。 !\[\](https://img.atcoder.jp/abc252/a6f35bb1addccc64564d36b812669d55.png)