Background

-Spread-by-missing-their-people's-thoughts-oh-thoughts-belief-

-Their-paths-missing-cut-off-oh-void-all-diversity-

-Within-the-same-kind-will-missing-container-forever-submit-oh-

-Put-into-matter-all-missing-yi-hollow-shell-seal-

Problem Description

A battle consists of $n$ moments. At moment $i$, the probability of being safe is $\frac{x_i}{x_i+y_i}$.

During safe moments, you may perform "gathering". It is required that in every consecutive $a$ moments, at least $b$ moments perform gathering. Under this condition, you want the number of moments that perform gathering to be as small as possible. If this condition cannot be satisfied, then the number of gathering moments is considered to be $0$. Find the expected number of gathering moments, and output the answer modulo $998244353$.

Input Format

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

The next $n$ lines: the $(i+1)$-th line contains two integers $x_i,y_i$, meaning that at moment $i$, the probability of being safe is $\frac{x_i}{x_i+y_i}$.

Output Format

Output one integer, the expected value modulo $998244353$.

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

1

3 2 1
1 0
1 1
1 1

1

4 2 1
3 2
2 0
1 1
3 1

249561090

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

63887640

Hint

Sample Explanation:

Use 1 to indicate that the current moment is safe, and 0 otherwise.

For sample 1, the safety sequence can only be 11111. In every consecutive three moments, at least one moment must be used for gathering. You can choose moment $3$ to gather, which satisfies 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 possible case, the expectation is also $1$.

For sample 2, the safety sequences 100, 101, 110, 111 have equal probability, all being $\frac14$. The numbers of gathering moments are $0,2,1,1$ respectively, so the expectation is $\frac{0+2+1+1}4=1$.

Constraints:

This problem uses bundled testdata.

For $100\%$ of the testdata, $1<n\le1.5\times10^4$, $1\le b<a\le\min(n,9)$, $x_i,y_i\ge0$, $0<x_i+y_i<998244353$.

Translated by ChatGPT 5