Etsi sellaisten $N$-solmuisten binääripuiden (binääripuu on juurellinen puu, jossa jokaisella solmulla on enintään yksi vasen lapsi ja enintään yksi oikea lapsi) lukumäärä, joiden solmut on numeroitu $1, 2, \dots, N$ ja jotka täyttävät kaikki seuraavat ehdot, ja tulosta tulos modulo $998244353$.
- Jokaiselle $i = 1, 2, \dots, N$ solmun $i$ esijärjestysindeksi (preorder index) on $i$. Erityisesti solmu $1$ on juuri.
- Jokaiselle $i = 1, 2, \dots, M$ solmun $A_i$ sisäjärjestysindeksi (inorder index) on $B_i$.
Kaksi binääripuuta katsotaan erilaisiksi, jos on olemassa solmu $v$ siten, että vähintään toinen seuraavista pätee:
- Solmun $v$ vasemman lapsen olemassaolo tai solmunumero on eri.
- Solmun $v$ oikean lapsen olemassaolo tai solmunumero on eri.
Binääripuun jokaisen solmun $v$ esijärjestysindeksi ja sisäjärjestysindeksi määritellään arvoiksi, jotka tallentuvat taulukoihin preorder[v] ja inorder[v], kun suoritetaan dfs(root) seuraavassa pseudokoodissa:
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)Syöte
Syöte annetaan seuraavassa muodossa:
$$\begin{aligned} &N \ M \\ &A_1 \ B_1 \\ &A_2 \ B_2 \\ &\vdots \\ &A_M \ B_M \end{aligned}$$
- Kaikki syötteen arvot ovat kokonaislukuja.
- $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$)
Tuloste
Tulosta vastaus yhdelle riville.
Esimerkit
Syöte 1
3 1 2 1
Tuloste 1
2
Syöte 2
5 3 1 3 2 5 4 2
Tuloste 2
0
Syöte 3
30 6 12 26 9 5 15 14 19 15 4 2 10 4
Tuloste 3
550222816
Huomautus
Ensimmäisessä esimerkissä on täsmälleen kaksi ehdot täyttävää binääripuuta. Toisessa solmu $1$ on juuri, solmu $2$ on solmun $1$ vasen lapsi ja solmu $3$ on solmun $2$ oikea lapsi. Toisessa solmu $1$ on juuri, solmu $2$ on solmun $1$ vasen lapsi ja solmu $3$ on solmun $1$ oikea lapsi. Niiden esijärjestys- ja sisäjärjestysindeksit ovat sopusoinnussa annettujen rajoitteiden kanssa.
Toisessa esimerkissä mikään binääripuu ei täytä ehtoja.