Finn antallet binære trær (et binært tre er et rotfestet tre der hver node har høyst ett venstrebarn og høyst ett høyrebarn) med $N$ noder merket $1, 2, \dots, N$ som tilfredsstiller alle følgende betingelser, og skriv ut resultatet modulo $998244353$.
- For hver $i = 1, 2, \dots, N$ er preorder-indeksen til node $i$ lik $i$. Spesielt er node $1$ roten.
- For hver $i = 1, 2, \dots, M$ er inorder-indeksen til node $A_i$ lik $B_i$.
To binære trær regnes som forskjellige hvis det finnes en node $v$ slik at minst én av følgende gjelder:
- Eksistensen eller nodenummeret til venstrebarnet til $v$ er forskjellig.
- Eksistensen eller nodenummeret til høyrebarnet til $v$ er forskjellig.
Preorder-indeksen og inorder-indeksen til hver node $v$ i et binært tre er definert som verdiene som registreres i henholdsvis preorder[v] og inorder[v] når dfs(root) kjøres i følgende pseudokode:
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)Inndata
Inndataene gis på følgende format:
$$\begin{aligned} &N \ M \\ &A_1 \ B_1 \\ &A_2 \ B_2 \\ &\vdots \\ &A_M \ B_M \end{aligned}$$
- Alle inndataverdier er heltall.
- $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å én enkelt linje.
Eksempler
Inndata 1
3 1 2 1
Utdata 1
2
Inndata 2
5 3 1 3 2 5 4 2
Utdata 2
0
Inndata 3
30 6 12 26 9 5 15 14 19 15 4 2 10 4
Utdata 3
550222816
Forklaring
I det første eksempelet er det nøyaktig to binære trær som tilfredsstiller betingelsene. Det ene har node $1$ som rot, node $2$ som venstrebarn til node $1$, og node $3$ som høyrebarn til node $2$. Det andre har node $1$ som rot, node $2$ som venstrebarn til node $1$, og node $3$ som høyrebarn til node $1$. Deres preorder- og inorder-indekser stemmer overens med de gitte begrensningene.
I det andre eksempelet tilfredsstiller ingen binære trær betingelsene.