Bestimme die Anzahl der Binärbäume (ein Binärbaum ist ein gewurzelter Baum, in dem jeder Knoten höchstens ein linkes Kind und höchstens ein rechtes Kind hat) mit $N$ Knoten, die mit $1, 2, \dots, N$ beschriftet sind und alle folgenden Bedingungen erfüllen, und gib das Ergebnis modulo $998244353$ aus.
- Für jedes $i = 1, 2, \dots, N$ ist der Preorder-Index von Knoten $i$ gleich $i$. Insbesondere ist Knoten $1$ die Wurzel.
- Für jedes $i = 1, 2, \dots, M$ ist der Inorder-Index von Knoten $A_i$ gleich $B_i$.
Zwei Binärbäume gelten als verschieden, wenn es einen Knoten $v$ gibt, sodass mindestens eine der folgenden Aussagen zutrifft:
- Die Existenz oder die Knotennummer des linken Kindes von $v$ ist unterschiedlich.
- Die Existenz oder die Knotennummer des rechten Kindes von $v$ ist unterschiedlich.
Der Preorder-Index und der Inorder-Index jedes Knotens $v$ in einem Binärbaum sind definiert als die Werte, die in preorder[v] bzw. inorder[v] gespeichert werden, wenn dfs(root) im folgenden Pseudocode ausgeführt wird:
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)Eingabe
Die Eingabe erfolgt im folgenden Format:
$$\begin{aligned} &N \ M \\ &A_1 \ B_1 \\ &A_2 \ B_2 \\ &\vdots \\ &A_M \ B_M \end{aligned}$$
- Alle Eingabewerte sind ganze Zahlen.
- $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$)
Ausgabe
Gib die Antwort in einer einzigen Zeile aus.
Beispiele
Eingabe 1
3 1 2 1
Ausgabe 1
2
Eingabe 2
5 3 1 3 2 5 4 2
Ausgabe 2
0
Eingabe 3
30 6 12 26 9 5 15 14 19 15 4 2 10 4
Ausgabe 3
550222816
Hinweis
Im ersten Beispiel gibt es genau zwei Binärbäume, welche die Bedingungen erfüllen. Einer hat Knoten $1$ als Wurzel, Knoten $2$ als linkes Kind von Knoten $1$ und Knoten $3$ als rechtes Kind von Knoten $2$. Der andere hat Knoten $1$ als Wurzel, Knoten $2$ als linkes Kind von Knoten $1$ und Knoten $3$ als rechtes Kind von Knoten $1$. Ihre Preorder- und Inorder-Indizes stimmen mit den gegebenen Bedingungen überein.
Im zweiten Beispiel erfüllt kein Binärbaum die Bedingungen.