Trova il numero di alberi binari (un albero binario è un albero radicato in cui ogni vertice ha al massimo un figlio sinistro e al massimo un figlio destro) con $N$ vertici etichettati $1, 2, \dots, N$ che soddisfano tutte le seguenti condizioni, e stampa il risultato modulo $998244353$.
- Per ogni $i = 1, 2, \dots, N$, l'indice di preordine (preorder index) del vertice $i$ è $i$. In particolare, il vertice $1$ è la radice.
- Per ogni $i = 1, 2, \dots, M$, l'indice di inordine (inorder index) del vertice $A_i$ è $B_i$.
Due alberi binari sono considerati diversi se esiste un vertice $v$ tale che valga almeno una delle seguenti condizioni:
- L'esistenza o il numero del vertice del figlio sinistro di $v$ è diverso.
- L'esistenza o il numero del vertice del figlio destro di $v$ è diverso.
L'indice di preordine e l'indice di inordine di ciascun vertice $v$ in un albero binario sono definiti come i valori registrati rispettivamente in preorder[v] e inorder[v] quando si esegue dfs(root) nel seguente pseudocodice:
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)Input
L'input viene fornito nel seguente formato:
$$\begin{aligned} &N \ M \\ &A_1 \ B_1 \\ &A_2 \ B_2 \\ &\vdots \\ &A_M \ B_M \end{aligned}$$
- Tutti i valori in input sono interi.
- $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$)
Output
Stampa la risposta su una singola riga.
Esempi
Input 1
3 1 2 1
Output 1
2
Input 2
5 3 1 3 2 5 4 2
Output 2
0
Input 3
30 6 12 26 9 5 15 14 19 15 4 2 10 4
Output 3
550222816
Note
Nel primo esempio, ci sono esattamente due alberi binari che soddisfano le condizioni. Uno ha il vertice $1$ come radice, il vertice $2$ come figlio sinistro del vertice $1$ e il vertice $3$ come figlio destro del vertice $2$. L'altro ha il vertice $1$ come radice, il vertice $2$ come figlio sinistro del vertice $1$ e il vertice $3$ come figlio destro del vertice $1$. I loro indici di preordine e di inordine sono coerenti con i vincoli dati.
Nel secondo esempio, nessun albero binario soddisfa le condizioni.