Trouvez le nombre d'arbres binaires (un arbre binaire est un arbre enraciné dans lequel chaque sommet possède au plus un enfant gauche et au plus un enfant droit) à $N$ sommets numérotés $1, 2, \dots, N$ qui satisfont toutes les conditions suivantes, et affichez le résultat modulo $998244353$.
- Pour chaque $i = 1, 2, \dots, N$, l'indice préfixe (preorder index) du sommet $i$ est $i$. En particulier, le sommet $1$ est la racine.
- Pour chaque $i = 1, 2, \dots, M$, l'indice infixe (inorder index) du sommet $A_i$ est $B_i$.
Deux arbres binaires sont considérés comme différents s'il existe un sommet $v$ tel qu'au moins l'une des affirmations suivantes soit vraie :
- L'existence ou le numéro du sommet de l'enfant gauche de $v$ est différent.
- L'existence ou le numéro du sommet de l'enfant droit de $v$ est différent.
L'indice préfixe et l'indice infixe de chaque sommet $v$ dans un arbre binaire sont définis comme les valeurs enregistrées respectivement dans preorder[v] et inorder[v] lors de l'exécution de dfs(root) dans le pseudocode suivant :
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)Entrée
L'entrée est donnée sous le format suivant :
$$\begin{aligned} &N \ M \\ &A_1 \ B_1 \\ &A_2 \ B_2 \\ &\vdots \\ &A_M \ B_M \end{aligned}$$
- Toutes les valeurs en entrée sont des entiers.
- $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$)
Sortie
Affichez la réponse sur une seule ligne.
Exemples
Entrée 1
3 1 2 1
Sortie 1
2
Entrée 2
5 3 1 3 2 5 4 2
Sortie 2
0
Entrée 3
30 6 12 26 9 5 15 14 19 15 4 2 10 4
Sortie 3
550222816
Note
Dans le premier exemple, il existe exactement deux arbres binaires qui satisfont les conditions. L'un a le sommet $1$ comme racine, le sommet $2$ comme enfant gauche du sommet $1$, et le sommet $3$ comme enfant droit du sommet $2$. L'autre a le sommet $1$ comme racine, le sommet $2$ comme enfant gauche du sommet $1$, et le sommet $3$ comme enfant droit du sommet $1$. Leurs indices préfixes et infixes sont cohérents avec les contraintes données.
Dans le deuxième exemple, aucun arbre binaire ne satisfait les conditions.