P8504 "CGOI-2" No will to break

-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-

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$.

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 one integer, the expected value modulo $998244353$.

### 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.** | ID | Limit | Score | | :-: | :-: | :-: | | 0 | $n\le20$ | 10pts | | 1 | $\forall i$，$x_i=0$ or $y_i=0$ | 10pts | | 2 | $n\le3\times 10^3$ | 30pts | | 3 | None | 50pts | For $100\%$ of the testdata, $1