分数: 600 点
问题陈述
有 N 单元格编号为 1 to N。最初,没有单元格被涂上任何颜色。
有 M 颜色类型,以及 i-th 颜色,您可以在单元格中绘制任意数量的单元格 L_i,L_i+1,\ldots,R_i.
求模数 998244353,绘制满足以下条件的单元格的方法:
- 对于每个单元格 i,如果该单元格涂有颜色,则正好是其中一个单元格 i-1 和 i+1 涂有与单元格相同的颜色 i.
- 这里,细胞 0 和 N+1 被认为未涂有任何颜色。
约束
- 1\leq N,M \leq 5\times 10^5
- 1\leq L_i \leq R_i \leq N
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N M L_1 R_1 \vdots L_M R_M
输出
输出答案。
示例输入 1
5 2 1 3 1 5
示例输出 1
11
第一种颜色可以绘制细胞 1,2,3,第二种颜色可以绘制单元格 1,2,3,4,5.
有 11 满足条件的绘画方式,如下:

示例输入 2
3 3 1 1 2 2 3 3
示例输出 2
1
不绘制任何单元格的一种方法满足条件。
示例输入 3
500000 10 1 499999 2 499998 3 499997 4 499996 5 499995 6 499994 7 499993 8 499992 9 499991 10 499990
示例输出 3
775503999
求计数模数 998244353.