AT_utpc2025_b Binary Tree Counting

頂点 $ 1, 2, \dots, N $ の $ N $ 頂点からなる二分木であって、以下の条件を全て満たすものの個数を $ 998244353 $ で割った余りを求めてください。 - 各 $ i = 1, 2, \dots, N $ に対し、頂点 $ i $ の**行きがけ順**は $ i $ である。特に、頂点 $ 1 $ が根である。 - 各 $ i = 1, 2, \dots, M $ に対し、頂点 $ A_i $ の**通りがけ順**は $ B_i $ である。 ただし、 $ 2 $ つの二分木が異なるとは、ある頂点 $ v $ が存在して、以下のいずれかが成り立つことを指します。 - $ v $ の左の子の有無または頂点番号が異なる。 - $ v $ の右の子の有無または頂点番号が異なる。 二分木とは 二分木とは、各頂点が高々 $ 1 $ 個の左の子と高々 $ 1 $ 個の右の子を持つ根付き木です。 行きがけ順・通りがけ順とは 二分木の各頂点 $ v $ の行きがけ順・通りがけ順は、以下の擬似コードにおいて `dfs(根)` を実行した際に記録される `preorder[v]` および `inorder[v]` の値として定義されます。 ``` pre_cnt = 1; in_cnt = 1 def dfs(v): preorder[v] = pre_cnt; pre_cnt += 1 if v の左の子が存在する: dfs(v の左の子) inorder[v] = in_cnt; in_cnt += 1 if v の右の子が存在する: dfs(v の右の子) ```

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ A_1 $ $ B_1 $ $ A_2 $ $ B_2 $ $ \vdots $ $ A_M $ $ B_M $

答えを $ 1 $ 行に出力せよ。

### Sample Explanation 1 次の $ 2 $ つの二分木が条件を満たします。 - 頂点 $ 1 $ が根で、頂点 $ 2 $ が頂点 $ 1 $ の左の子で、頂点 $ 3 $ が頂点 $ 2 $ の右の子である二分木。この二分木において、 - 頂点 $ 1 $ の行きがけ順は $ 1 $ 、通りがけ順は $ 3 $ です。 - 頂点 $ 2 $ の行きがけ順は $ 2 $ 、通りがけ順は $ 1 $ です。 - 頂点 $ 3 $ の行きがけ順は $ 3 $ 、通りがけ順は $ 2 $ です。 - 頂点 $ 1 $ が根で、頂点 $ 2 $ が頂点 $ 1 $ の左の子で、頂点 $ 3 $ が頂点 $ 1 $ の右の子である二分木。 この二分木において、 - 頂点 $ 1 $ の行きがけ順は $ 1 $ 、通りがけ順は $ 2 $ です。 - 頂点 $ 2 $ の行きがけ順は $ 2 $ 、通りがけ順は $ 1 $ です。 - 頂点 $ 3 $ の行きがけ順は $ 3 $ 、通りがけ順は $ 3 $ です。 ### Sample Explanation 2 条件を満たす二分木は存在しません。 ### Constraints - 入力は全て整数 - $ 1 \leq M \leq N \leq 500 $ - $ 1 \leq A_i, B_i \leq N $ - $ A_i \neq A_j \ (i \neq j) $ - $ B_i \neq B_j \ (i \neq j) $