#P18002. Binary Tree Counting

Binary Tree Counting

Binary Tree Counting

求有多少棵含 NN 个顶点、顶点编号为 1,2,…,N1,2,\ldots,N 的二叉树,满足:

  • 对每个 ii,顶点 ii 的先序遍历序号恰好为 ii,因此根为顶点 11。
  • 对每个 i=1,…,Mi=1,\ldots,M,顶点 AiA_i 的中序遍历序号为 BiB_i。

答案对 998244353998244353 取模。

这里二叉树是每个顶点至多有一个左儿子和一个右儿子的有根树。只要存在某个顶点,其左儿子或右儿子的存在性或编号不同,两棵树就视为不同。仅有一个儿子时,左儿子和右儿子的情况也不同。

先序、中序遍历序号由以下过程定义,两个计数器初值均为 11:

dfs(v):
    preorder[v] = pre_cnt; pre_cnt += 1
    如果 v 有左儿子:dfs(v 的左儿子)
    inorder[v] = in_cnt; in_cnt += 1
    如果 v 有右儿子:dfs(v 的右儿子)

对根调用 dfs。

输入格式

第一行两个整数 N,MN,M。接下来 MM 行,每行两个整数 Ai,BiA_i,B_i。

输出格式

输出满足条件的二叉树数量对 998244353998244353 取模的结果。

数据范围

1≤M≤N≤5001\le M\le N\le500,1≤Ai,Bi≤N1\le A_i,B_i\le N。所有 AiA_i 两两不同,所有 BiB_i 两两不同。

样例 1

输入

3 1
2 1

输出

2

样例 2

输入

5 3
1 3
2 5
4 2

输出

0

样例 3

输入

30 6
12 26
9 5
15 14
19 15
4 2
10 4

输出

550222816