分数: 1000 点
问题陈述
栗色的暑假持续了 N 从当天算起的天数 1 到白天 N。 放假期间, M 电影编号自 1 通过 M 预定上映,电影 i 可以从 Day 开始观看 L_i 到白天 R_i.
对于子集 s 所有电影,定义 f(s) 如下:
- f(s) 是电影的最大数量 s 整个假期都可以观看,每天最多可以看一部电影。 在这里,多次观看同一部电影算作一部电影。
有 2^M 可能的设置 s。 求总和,取模 998244353,属于 f(s) 超过所有这些。
约束
- 1 \leq N \leq 100
- 1 \leq M \leq N \times (N+1) /2
- 1 \leq L_i \leq 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
2 3 1 1 2 2 1 2
示例输出 1
11
f(s)=|s| 适用于大多数 s。 唯一的例外是 s=\{1,2,3\},其中 f(s)=2。 总和 f(s) 总的来说 s is 11.
示例输入 2
3 3 1 1 2 2 3 3
示例输出 2
12
示例输入 3
4 10 3 3 2 4 2 3 4 4 3 4 1 3 1 1 2 2 1 2 1 4
示例输出 3
3796
示例输入 4
7 20 1 3 4 5 3 3 3 5 1 4 4 7 2 3 1 7 6 7 4 6 2 4 6 6 3 6 2 5 7 7 3 4 2 2 5 5 2 6 1 2
示例输出 4
7113137