Знайдіть кількість двійкових дерев (двійкове дерево — це кореневе дерево, у якому в кожної вершини є не більше одного лівого сина та не більше одного правого сина) з $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$. Їхні індекси прямого та симетричного обходів узгоджуються із заданими обмеженнями.
У другому прикладі жодне двійкове дерево не задовольняє умови.