← 返回题目列表

AtCoder · abc435_g

G. 多米诺骨牌排列

中文机器翻译题面 查看原题

分数: 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 满足条件的绘画方式,如下:

Figure


示例输入 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.