3110 - 三班不一般

HQ 是传奇颜值中学的一位尽职尽责的后勤部教师,同时也是宿舍的管理成员,负责管理开关灯。

对于他来说,最令人厌烦的的就是极不一般的三班的一群猴子乱玩自己宿舍和别人宿舍的灯,但是却没法当场发现并抓捕始作俑者。

HQ 需要管理 n 个宿舍的灯,第 i 个宿舍的同学因为有着传奇颜值而十分挑剔,只能忍受亮度为 [l_i,r_i] 的灯。每个宿舍的灯的亮度可以在对应的可忍受范围内肆意调节。

今天陈添润决定成为总司令,对所有宿舍的灯进行调节,为了防止被 HQ 当场抓捕,他不能让 HQ 发觉宿舍的灯太过刺眼,当连续 a 个宿舍的灯亮都大于 b 的时候,宿舍的灯就刺眼了。\color{white}\text{不可以,总司令}

因此,帮助陈添润数一数一共有多少灯泡调节方案能满足宿舍不刺眼,答案对 998244353 取模。

输入

第一行是三个正整数 n,a,b,含义如题所示。

下面一共 n 行,每行两个正整数,第 i 行的两个正整数分别表示 l_i,r_i

输出

一行一个整数,表示答案,对 998244353 取模。

样例

输入

3 1 3
3 4
3 3
2 4

输出

2

输入

5 2 5
2 4
1 6
5 10
1 1
5 6

输出

186

输入

12 9 66
41 76
33 61
10 25
84 86
20 49
43 59
26 56
44 71
48 79
1 35
27 83
49 76

输出

358014651

提示

对于样例 1,只有两种方案: {3,3,2} 或者 {3,3,3} 能满足条件。

对于所有数据,满足 1\le n\le 2\cdot 10^51\le a\le n+11\le b\le 10^91\le l_i\le r_i\le 10^9

来源

DBOI

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题