求满足以下所有条件的标号为 $1, 2, \dots, N$ 的二叉树*的数量，并将结果对 $998244353$ 取模。

• 对于每个 $i = 1, 2, \dots, N$，顶点 $i$ 的先序遍历编号（preorder index）为 $i$。特别地，顶点 $1$ 是根节点。
• 对于每个 $i = 1, 2, \dots, M$，顶点 $A_i$ 的中序遍历编号（inorder index）为 $B_i$。

如果存在一个顶点 $v$，使得以下至少一个条件成立，则认为两棵二叉树不同：

• $v$ 的左孩子的存在性或顶点编号不同。
• $v$ 的右孩子的存在性或顶点编号不同。

二叉树中每个顶点 $v$ 的先序遍历编号和中序遍历编号定义为在执行以下伪代码中的 dfs(root) 时，记录在 preorder[v] 和 inorder[v] 中的值：

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)

输入格式

输入格式如下：

$N$ $M$ $A_1$ $B_1$ $A_2$ $B_2$ $\vdots$ $A_M$ $B_M$

• 所有输入值均为整数。
• $1 \le M \le N \le 500$
• $1 \le A_i, B_i \le N$
• $A_i \neq A_j$ ($i \neq j$)
• $B_i \neq B_j$ ($i \neq 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$ 的右孩子。它们的先序和中序遍历编号均符合给定的约束。

在第二个样例中，没有二叉树满足条件。

*二叉树是一种有根树，其中每个顶点最多有一个左孩子和最多一个右孩子。