题目描述

给定整数 $N$ 和 $M$ 对整数。第 $i$ 对是 $(L_i,R_i)$。

找到可以按照以下方式生成的整数序列 $x=(x_1,x_2,\\cdots,x_M)$ 的数量，取模 $998244353$。

• 提供一个排列 $p=(p_1,p_2,\\cdots,p_N)$ of $(1,2,\\cdots,N)$。
• 对于每个 $i$ ($1 \\leq i \\leq M$)，令 $x_i$ 是 $p_{L_i},p_{L_i+1},\\cdots,p_{R_i}$ 中最大元素的索引。也就是说，$\\max(p_{L_i},p_{L_i+1},\\cdots,p_{R_i})=p_{x_i}$。

约束条件

• $2 \\leq N \\leq 300$
• $1 \\leq M \\leq N(N-1)/2$
• $1 \\leq L_i < R_i \\leq N$
• $(L_i,R_i) \\neq (L_j,R_j)$ ($i \\neq j$)
• 输入中的所有值都是整数。

输入

从标准输入读入数据，数据格式如下：

$N$ $M$ $L_1$ $R_1$ $L_2$ $R_2$ $\\vdots$ $L_M$ $R_M$

输出

打印答案。

示例输入 1

3 2
1 2
1 3

示例输出 1

4

例如，对于 $p=(2,1,3)$，我们将得到 $x=(1,3)$。

满足要求的四个序列是 $x=(1,1),(1,3),(2,2),(2,3)$。

示例输入 2

6 3
1 2
3 4
5 6

示例输出 2

8

示例输入 3

10 10
8 10
5 8
5 7
2 5
1 7
4 5
5 9
2 8
7 8
3 9

示例输出 3

1060