問題文

頂点 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 の右の子の有無または頂点番号が異なる。

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 の右の子)

制約

• 入力は全て整数
• 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)

入力例 1

3 1
2 1

出力例 1

2

次の 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 です。

入力例 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