求滿足以下所有條件、包含 $N$ 個標號為 $1, 2, \dots, N$ 嘅頂點嘅二叉樹(二叉樹係一種有根樹,其中每個頂點最多有一個左子節點同最多一個右子節點)嘅數量,並將結果對 $998244353$ 取模後輸出。
- 對於每個 $i = 1, 2, \dots, N$,頂點 $i$ 嘅前序遍歷編號為 $i$。特別地,頂點 $1$ 係根節點。
- 對於每個 $i = 1, 2, \dots, M$,頂點 $A_i$ 嘅中序遍歷編號為 $B_i$。
如果存在一個頂點 $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
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$ 嘅左子節點,頂點 $3$ 為頂點 $2$ 嘅右子節點。另一棵以頂點 $1$ 為根,頂點 $2$ 為頂點 $1$ 嘅左子節點,頂點 $3$ 為頂點 $1$ 嘅右子節點。佢哋嘅前序同中序遍歷編號都符合畀定嘅限制條件。
喺第二個樣例入面,冇任何二叉樹滿足條件。