Finndu fjölda tvíundartrjáa (tvíundartré er rótað tré þar sem hver hnútur hefur í mesta lagi eitt vinstra barn og í mesta lagi eitt hægra barn) með $N$ hnútum merktum $1, 2, \dots, N$ sem uppfylla öll eftirfarandi skilyrði, og prentaðu niðurstöðuna modulo $998244353$.
- Fyrir hvert $i = 1, 2, \dots, N$ er forraðarvísir (preorder index) hnúts $i$ jafn $i$. Sér í lagi er hnútur $1$ rótin.
- Fyrir hvert $i = 1, 2, \dots, M$ er innraðarvísir (inorder index) hnúts $A_i$ jafn $B_i$.
Tvö tvíundartré teljast ólík ef til er hnútur $v$ þannig að að minnsta kosti annað af eftirfarandi gildir:
- Tilvist eða hnútanúmer vinstra barns $v$ er ólíkt.
- Tilvist eða hnútanúmer hægra barns $v$ er ólíkt.
Forraðarvísir og innraðarvísir hvers hnúts $v$ í tvíundartré eru skilgreindir sem gildin sem skráð eru í preorder[v] og inorder[v], í sömu röð, þegar dfs(root) er keyrt í eftirfarandi sauðakóða:
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)Inntak
Inntakið er gefið á eftirfarandi sniði:
$$\begin{aligned} &N \ M \\ &A_1 \ B_1 \\ &A_2 \ B_2 \\ &\vdots \\ &A_M \ B_M \end{aligned}$$
- Öll inntaksgildi eru heiltölur.
- $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$)
Úttak
Prentaðu svarið á einni línu.
Dæmi
Inntak 1
3 1 2 1
Úttak 1
2
Inntak 2
5 3 1 3 2 5 4 2
Úttak 2
0
Inntak 3
30 6 12 26 9 5 15 14 19 15 4 2 10 4
Úttak 3
550222816
Athugasemd
Í fyrsta dæminu eru nákvæmlega tvö tvíundartré sem uppfylla skilyrðin. Annað hefur hnút $1$ sem rót, hnút $2$ sem vinstra barn hnúts $1$ og hnút $3$ sem hægra barn hnúts $2$. Hitt hefur hnút $1$ sem rót, hnút $2$ sem vinstra barn hnúts $1$ og hnút $3$ sem hægra barn hnúts $1$. Forraðar- og innraðarvísar þeirra eru í samræmi við gefnar skorður.
Í öðru dæminu uppfyllir ekkert tvíundartré skilyrðin.