Background

HQ is a diligent logistics teacher at the legendary good-looking high school, and also a member of the dormitory management team, responsible for managing switching the lights on and off.

For him, the most annoying thing is that a group of “monkeys” from the very unusual Class 3 mess around with the lights in their own dorms and other dorms, yet he cannot catch and arrest the culprit on the spot.

Problem Description

HQ needs to manage the lights of $n$ dormitories. Students in dormitory $i$ are very picky because of their legendary good looks, and they can only tolerate lights with brightness in $[l_i,r_i]$. The brightness of each dormitory’s light can be adjusted freely within its tolerable range.

Today, Chen Tianrun decided to become the commander-in-chief and adjust the lights of all dormitories. To avoid being caught by HQ on the spot, he cannot let HQ notice that the dormitory lights are too dazzling. When the brightness of the lights in $a$ consecutive dormitories are all greater than $b$, the dormitory lights become dazzling. $\color{white}\text{No, commander-in-chief.}$

Therefore, help Chen Tianrun count how many light-bulb adjustment plans can ensure the dormitories are not dazzling. Output the answer modulo $998244353$.

Input Format

The first line contains three positive integers $n,a,b$, with meanings as described in the statement.

Then there are $n$ lines. Each line contains two positive integers. The two integers on line $i$ are $l_i,r_i$, respectively.

Output Format

Output one integer on a single line, the answer modulo $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

Hint

Sample Explanation

For sample $1$, there are only two valid plans: $\{3,3,2\}$ or $\{3,3,3\}$.

For sample $3$, please output the answer modulo $998244353$.

Constraints

This problem uses bundled testdata.

For all testdata, $1\le n\le 2\cdot 10^5$, $1\le a\le n+1$, $1\le b\le 10^9$, $1\le l_i\le r_i\le 10^9$.

Translated by ChatGPT 5