Найдите количество двоичных деревьев (двоичное дерево — это корневое дерево, в котором у каждой вершины есть не более одного левого сына и не более одного правого сына) с $N$ вершинами, пронумерованными $1, 2, \dots, N$, которые удовлетворяют всем следующим условиям, и выведите результат по модулю $998244353$.
- Для каждого $i = 1, 2, \dots, N$ индекс прямого обхода (preorder index) вершины $i$ равен $i$. В частности, вершина $1$ является корнем.
- Для каждого $i = 1, 2, \dots, M$ индекс центрированного обхода (inorder index) вершины $A_i$ равен $B_i$.
Два двоичных дерева считаются различными, если существует вершина $v$, для которой выполняется хотя бы одно из следующих условий:
- Наличие или номер вершины левого сына вершины $v$ отличается.
- Наличие или номер вершины правого сына вершины $v$ отличается.
Индекс прямого обхода и индекс центрированного обхода каждой вершины $v$ в двоичном дереве определяются как значения, записанные в preorder[v] и inorder[v] соответственно при выполнении dfs(root) в следующем псевдокоде:
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)Входные данные
Входные данные даны в следующем формате:
$$\begin{aligned} &N \ M \\ &A_1 \ B_1 \\ &A_2 \ B_2 \\ &\vdots \\ &A_M \ B_M \end{aligned}$$
- Все входные значения являются целыми числами.
- $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$)
Выходные данные
Выведите ответ в единственной строке.
Примеры
Входные данные 1
3 1 2 1
Выходные данные 1
2
Входные данные 2
5 3 1 3 2 5 4 2
Выходные данные 2
0
Входные данные 3
30 6 12 26 9 5 15 14 19 15 4 2 10 4
Выходные данные 3
550222816
Примечание
В первом примере существуют ровно два двоичных дерева, удовлетворяющих условиям. В одном из них вершина $1$ является корнем, вершина $2$ — левым сыном вершины $1$, а вершина $3$ — правым сыном вершины $2$. В другом вершина $1$ является корнем, вершина $2$ — левым сыном вершины $1$, а вершина $3$ — правым сыном вершины $1$. Их индексы прямого и центрированного обходов согласуются с заданными ограничениями.
Во втором примере ни одно двоичное дерево не удовлетворяет условиям.