以下の条件をすべて満たす、$N$ 個の頂点に $1, 2, \dots, N$ の番号が付けられた二分木(二分木とは、各頂点が高々 $1$ つの左の子と高々 $1$ つの右の子を持つ根付き木のことです)の個数を求め、結果を $998244353$ で割った余りを出力してください。
- 各 $i = 1, 2, \dots, N$ について、頂点 $i$ の行きがけ順(preorder)の番号は $i$ である。特に、頂点 $1$ は根である。
- 各 $i = 1, 2, \dots, M$ について、頂点 $A_i$ の通りがけ順(inorder)の番号は $B_i$ である。
$2$ つの二分木は、以下の少なくとも一方が成り立つような頂点 $v$ が存在するとき、異なるとみなされます:
- $v$ の左の子の有無または頂点番号が異なる。
- $v$ の右の子の有無または頂点番号が異なる。
二分木の各頂点 $v$ の行きがけ順の番号および通りがけ順の番号は、以下の擬似コードにおいて dfs(root) を実行した際に、それぞれ preorder[v] および inorder[v] に記録される値として定義されます:
pre_cnt = 1; in_cnt = 1
def dfs(v):
preorder[v] = pre_cnt; pre_cnt += 1
if v has a left child:
dfs(left child of v)
inorder[v] = in_cnt; in_cnt += 1
if v has a right child:
dfs(right child of v)入力
入力は以下の形式で与えられます:
$$\begin{aligned} &N \ M \\ &A_1 \ B_1 \\ &A_2 \ B_2 \\ &\vdots \\ &A_M \ B_M \end{aligned}$$
- 入力される値はすべて整数である。
- $1 \le M \le N \le 500$
- $1 \le A_i, B_i \le N$
- $A_i \ne A_j$ ($i \ne j$)
- $B_i \ne B_j$ ($i \ne j$)
出力
答えを $1$ 行で出力してください。
入出力例
入力例 1
3 1 2 1
出力例 1
2
入力例 2
5 3 1 3 2 5 4 2
出力例 2
0
入力例 3
30 6 12 26 9 5 15 14 19 15 4 2 10 4
出力例 3
550222816
注記
$1$ 番目の例では、条件を満たす二分木はちょうど $2$ つあります。一方は頂点 $1$ を根とし、頂点 $2$ が頂点 $1$ の左の子、頂点 $3$ が頂点 $2$ の右の子である木です。もう一方は頂点 $1$ を根とし、頂点 $2$ が頂点 $1$ の左の子、頂点 $3$ が頂点 $1$ の右の子である木です。これらの行きがけ順および通りがけ順の番号は、与えられた制約と整合しています。
$2$ 番目の例では、条件を満たす二分木は存在しません。