分数: 900 点
问题陈述
给定一个整数 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