题目描述

頂点 $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$ $P_1$ $P_2$ $\ldots$ $P_N$

输出格式

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

题目大意

存在一棵 $n$ 个点的树，给定序列 $P_n$ 表示树的先序遍历，特别地，已知当一个节点有多个儿子的时候会优先遍历编号较小的儿子。求满足条件的树的方案数。对 $998244353$ 取模。

4
1 2 4 3

3

8
1 2 3 5 6 7 8 4

202

提示

制約

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

Sample Explanation 1

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