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