题目背景
HQ 是传奇颜值中学的一位尽职尽责的后勤部教师,同时也是宿舍的管理成员,负责管理开关灯。
对于他来说,最令人厌烦的的就是极不一般的三班的一群猴子乱玩自己宿舍和别人宿舍的灯,但是却没法当场发现并抓捕始作俑者。
题目描述
HQ 需要管理 n 个宿舍的灯,第 i 个宿舍的同学因为有着传奇颜值而十分挑剔,只能忍受亮度为 [li,ri] 的灯。每个宿舍的灯的亮度可以在对应的可忍受范围内肆意调节。
今天陈添润决定成为总司令,对所有宿舍的灯进行调节,为了防止被 HQ 当场抓捕,他不能让 HQ 发觉宿舍的灯太过刺眼,当连续 a 个宿舍的灯亮都大于 b 的时候,宿舍的灯就刺眼了。不可以,总司令
因此,帮助陈添润数一数一共有多少灯泡调节方案能满足宿舍不刺眼,答案对 998244353 取模。
输入格式
第一行是三个正整数 n,a,b,含义如题所示。
下面一共 n 行,每行两个正整数,第 i 行的两个正整数分别表示 li,ri。
输出格式
一行一个整数,表示答案,对 998244353 取模。
提示
样例解释
对于样例 1,只有两种方案: {3,3,2} 或者 {3,3,3} 能满足条件。
对于样例 3,请将答案对 998244353 取模。
数据范围
本题采用捆绑测试。
对于所有数据,满足 1≤n≤2⋅105,1≤a≤n+1,1≤b≤109,1≤li≤ri≤109。
Subtask |
n,(a−1)≤ |
li,ri,b≤ |
特殊性质 |
分值 |
1 |
5 |
20 |
无 |
10 |
2 |
2⋅105 |
109 |
a=n+1 |
3 |
a=1 |
4 |
103 |
无 |
30 |
5 |
2⋅105 |
40 |