AT_agc056_b.[AGC056B] Range Argmax

给定一个整数 $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$

输出答案。

限制条件

• $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 翻译