Hitta antalet binära träd (ett binärt träd är ett rotat träd där varje hörn har högst ett vänsterbarn och högst ett högerbarn) med $N$ hörn numrerade $1, 2, \dots, N$ som uppfyller alla följande villkor, och skriv ut resultatet modulo $998244353$.
- För varje $i = 1, 2, \dots, N$ är preorder-indexet för hörn $i$ lika med $i$. Speciellt är hörn $1$ roten.
- För varje $i = 1, 2, \dots, M$ är inorder-indexet för hörn $A_i$ lika med $B_i$.
Två binära träd betraktas som olika om det finns ett hörn $v$ sådant att minst ett av följande gäller:
- Existensen eller hörnnumret för vänsterbarnet till $v$ är annorlunda.
- Existensen eller hörnnumret för högerbarnet till $v$ är annorlunda.
Preorder-indexet och inorder-indexet för varje hörn $v$ i ett binärt träd definieras som de värden som registreras i preorder[v] respektive inorder[v] när dfs(root) körs i följande pseudokod:
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)Indata
Indatan ges i följande format:
$$\begin{aligned} &N \ M \\ &A_1 \ B_1 \\ &A_2 \ B_2 \\ &\vdots \\ &A_M \ B_M \end{aligned}$$
- Alla indatavärden är heltal.
- $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$)
Utdata
Skriv ut svaret på en enda rad.
Exempel
Indata 1
3 1 2 1
Utdata 1
2
Indata 2
5 3 1 3 2 5 4 2
Utdata 2
0
Indata 3
30 6 12 26 9 5 15 14 19 15 4 2 10 4
Utdata 3
550222816
Förklaring
I det första exemplet finns det exakt två binära träd som uppfyller villkoren. Det ena har hörn $1$ som rot, hörn $2$ som vänsterbarn till hörn $1$ och hörn $3$ som högerbarn till hörn $2$. Det andra har hörn $1$ som rot, hörn $2$ som vänsterbarn till hörn $1$ och hörn $3$ som högerbarn till hörn $1$. Deras preorder- och inorder-index överensstämmer med de givna begränsningarna.
I det andra exemplet uppfyller inget binärt träd villkoren.