题目描述

整数 $N$ と整数の組が $M$ 個与えられます． $i$ 番目の組は $(L_i,R_i)$ です．

以下の手順で生成されうる整数列 $x=(x_1,x_2,\cdots,x_M)$ の個数を $998244353$ で割った余りを求めて下さい．

• $(1,2,\cdots,N)$ の順列 $p=(p_1,p_2,\cdots,p_N)$ を用意する．
• 各 $i$ ($1\ \leq\ i\ \leq\ M$) について，$p_{L_i},p_{L_i+1},\cdots,p_{R_i}$ の中で最も大きい値の index を $x_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$

输出格式

答えを出力せよ．

题目大意

给定整数 $n$ 以及 $m$ 对整数。第 $i$ 对整数为 $(l_i, r_i)$ 。

请输出可以通过如下方式生成的整数序列 $x = (x_1, x_2,\cdots,x_m)$ 的个数。答案对 $998244353$ 取模。

生成方式：

• 取排列 $p = (p_1, p_2,\cdots,p_n)$，满足其为一个 $1$ 至 $n$ 的排列。
• 对于任意 $1\le i \le m$ 的 $i$，令 $x_i$ 为 $p_{l_i}， p_{l_i + 1},\cdots ,p_{r_i}$ 中最大值对应的下标。即 $p_{x_i} = \max\{p_{l_i}， p_{l_i + 1},\cdots, p_{r_i}\}$。

$2\le n\le 300,\ 1\le m\le \frac{n(n - 1)}2$。

3 2
1 2
1 3

4

6 3
1 2
3 4
5 6

8

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\ N(N-1)/2$
• $1\ \leq\ L_i\ <\ R_i\ \leq\ N$
• $(L_i,R_i)\ \neq\ (L_j,R_j)$ ($i\ \neq\ j$)
• 入力される値はすべて整数である

Sample Explanation 1

例えば，$p=(2,1,3)$ とした場合は $x=(1,3)$ となります． 条件を満たす数列は，$x=(1,1),(1,3),(2,2),(2,3)$ の $4$ 通りです．