题目描述

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

请你求出，按照以下步骤可以生成的整数序列 $x=(x_1, x_2, \cdots, x_M)$ 的种数，答案对 $998244353$ 取模。

• 准备一个 $1$ 到 $N$ 的排列 $p=(p_1, p_2, \cdots, p_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}$。

输入格式

输入按以下格式从标准输入读入。

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

输出格式

输出答案。

样例 1

输入

3 2
1 2
1 3

输出

4

样例 2

输入

6 3
1 2
3 4
5 6

输出

8

样例 3

输入

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

输出

1060

说明/提示

限制条件

• $2 \leq N \leq 300$
• $1 \leq M \leq \dfrac{N(N-1)}{2}$
• $1 \leq L_i < R_i \leq N$
• $(L_i, R_i) \neq (L_j, R_j)$（$i \neq j$）
• 所有输入的值均为整数

样例解释 1

例如，当 $p=(2,1,3)$ 时，$x=(1,3)$。满足条件的数列有 $x=(1,1),(1,3),(2,2),(2,3)$ 共 $4$ 种。

由 ChatGPT 4.1 翻译