Problem Description

A battle consists of $n$ moments. The $i$-th moment has a probability of $\frac{x_i}{x_i+y_i}$ to be safe.

During safe moments, you can perform a "gathering". It is required that in any consecutive sequence of $a$ moments, there must be at least $b$ moments where gathering is performed. Under this condition, you want to minimize the number of moments used for gathering; if this condition cannot be met, the number of moments used for gathering is considered to be $0$. Calculate the expected number of moments used for gathering, and output the result modulo $998244353$.

Input Format

The first line contains three integers $n, a, b$, as described above.

The next $n$ lines each contain two integers $x_i, y_i$, indicating that the $i$-th moment has a probability of $\frac{x_i}{x_i+y_i}$ to be safe.

Output Format

Output a single integer, which is the expected number of moments used for gathering modulo $998244353$.

Sample Input and Output

Sample Input #1

5 3 1
1 0
2 0
3 0
4 0
114514 0

Sample Output #1

1

Sample Input #2

3 2 1
1 0
1 1
1 1

Sample Output #2

1

Sample Input #3

4 2 1
3 2
2 0
1 1
3 1

Sample Output #3

249561090

Sample Input #4

15 5 2
4 0
2 0
3 1
0 1
1 4
2 0
0 4
1 4
0 4
1 0
2 2
4 1
0 4
1 0
4 0

Sample Output #4

63887640

Notes

Sample Explanation:

Use 1 to denote a safe moment and 0 to denote an unsafe moment.

For the first sample, the sequence of safety can only be 11111. In every consecutive three moments, at least one moment must be used for gathering. The third moment can be chosen for gathering, which meets the condition. The number of gathering moments is $1$, and it can be proven that it cannot be less than $1$. Since there is only one possibility, the expected value is also $1$.

For the second sample, the sequences of safety are 100, 101, 110, and 111 with equal probability of $\frac{1}{4}$. The number of gathering moments for each sequence is $0, 2, 1, 1$ respectively, and the expected value is $\frac{0+2+1+1}{4} = 1$.

Data Range:

This problem uses subtask testing.

For $100\%$ of the data, $1 < n \leq 1.5 \times 10^4$, $1 \leq b < a \leq \min(n, 9)$, $x_i, y_i \geq 0$, and $0 < x_i + y_i < 998244353$.

见题面 Input 部分

见题面 Output 部分