Encuentra el número de árboles binarios (un árbol binario es un árbol con raíz en el que cada vértice tiene como máximo un hijo izquierdo y como máximo un hijo derecho) con $N$ vértices etiquetados $1, 2, \dots, N$ que satisfacen todas las condiciones siguientes, e imprime el resultado módulo $998244353$.
- Para cada $i = 1, 2, \dots, N$, el índice en preorden del vértice $i$ es $i$. En particular, el vértice $1$ es la raíz.
- Para cada $i = 1, 2, \dots, M$, el índice en inorden del vértice $A_i$ es $B_i$.
Dos árboles binarios se consideran diferentes si existe un vértice $v$ tal que se cumple al menos una de las siguientes condiciones:
- La existencia o el número de vértice del hijo izquierdo de $v$ es diferente.
- La existencia o el número de vértice del hijo derecho de $v$ es diferente.
El índice en preorden y el índice en inorden de cada vértice $v$ en un árbol binario se definen como los valores registrados en preorder[v] e inorder[v], respectivamente, al ejecutar dfs(root) en el siguiente pseudocódigo:
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)Entrada
La entrada se proporciona en el siguiente formato:
$$\begin{aligned} &N \ M \\ &A_1 \ B_1 \\ &A_2 \ B_2 \\ &\vdots \\ &A_M \ B_M \end{aligned}$$
- Todos los valores de entrada son enteros.
- $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$)
Salida
Imprime la respuesta en una sola línea.
Ejemplos
Entrada 1
3 1 2 1
Salida 1
2
Entrada 2
5 3 1 3 2 5 4 2
Salida 2
0
Entrada 3
30 6 12 26 9 5 15 14 19 15 4 2 10 4
Salida 3
550222816
Nota
En el primer ejemplo, hay exactamente dos árboles binarios que satisfacen las condiciones. Uno tiene el vértice $1$ como raíz, el vértice $2$ como hijo izquierdo del vértice $1$ y el vértice $3$ como hijo derecho del vértice $2$. El otro tiene el vértice $1$ como raíz, el vértice $2$ como hijo izquierdo del vértice $1$ y el vértice $3$ como hijo derecho del vértice $1$. Sus índices en preorden e inorden son consistentes con las restricciones dadas.
En el segundo ejemplo, ningún árbol binario satisface las condiciones.