Znajdź liczbę drzew binarnych (drzewo binarne to drzewo ukorzenione, w którym każdy wierzchołek ma co najwyżej jedno lewe dziecko i co najwyżej jedno prawe dziecko) o $N$ wierzchołkach oznaczonych $1, 2, \dots, N$, które spełniają wszystkie poniższe warunki, i wypisz wynik modulo $998244353$.
- Dla każdego $i = 1, 2, \dots, N$, indeks preorder wierzchołka $i$ wynosi $i$. W szczególności wierzchołek $1$ jest korzeniem.
- Dla każdego $i = 1, 2, \dots, M$, indeks inorder wierzchołka $A_i$ wynosi $B_i$.
Dwa drzewa binarne uznajemy za różne, jeśli istnieje wierzchołek $v$, dla którego zachodzi co najmniej jeden z poniższych warunków:
- Istnienie lub numer wierzchołka lewego dziecka $v$ różni się.
- Istnienie lub numer wierzchołka prawego dziecka $v$ różni się.
Indeks preorder oraz indeks inorder każdego wierzchołka $v$ w drzewie binarnym definiuje się jako wartości zapisane odpowiednio w preorder[v] oraz inorder[v] podczas wykonania dfs(root) w poniższym pseudokodzie:
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)Wejście
Wejście podawane jest w następującym formacie:
$$\begin{aligned} &N \ M \\ &A_1 \ B_1 \\ &A_2 \ B_2 \\ &\vdots \\ &A_M \ B_M \end{aligned}$$
- Wszystkie wartości na wejściu są liczbami całkowitymi.
- $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$)
Wyjście
Wypisz odpowiedź w jednym wierszu.
Przykłady
Wejście 1
3 1 2 1
Wyjście 1
2
Wejście 2
5 3 1 3 2 5 4 2
Wyjście 2
0
Wejście 3
30 6 12 26 9 5 15 14 19 15 4 2 10 4
Wyjście 3
550222816
Uwaga
W pierwszym przykładzie istnieją dokładnie dwa drzewa binarne spełniające warunki. Jedno z nich ma wierzchołek $1$ jako korzeń, wierzchołek $2$ jako lewe dziecko wierzchołka $1$ oraz wierzchołek $3$ jako prawe dziecko wierzchołka $2$. Drugie ma wierzchołek $1$ jako korzeń, wierzchołek $2$ jako lewe dziecko wierzchołka $1$ oraz wierzchołek $3$ jako prawe dziecko wierzchołka $1$. Ich indeksy preorder oraz inorder są zgodne z podanymi więzami.
W drugim przykładzie żadne drzewo binarne nie spełnia warunków.