题目背景

-传播-由-缺失-它们-子民-思想-哦-思想-信念-

-它们-途径-缺失-切除-哦-虚空-全部-多样性-

-同族-内部-意志-缺失-容器-永远-屈服-哦-

-放-入-物质-全部-缺失-噫-空洞-壳-封印-

题目描述

一场战斗由 $n$ 个时刻组成，第 $i$ 个时刻有 $\frac{x_i}{x_i+y_i}$ 的概率是安全的。

在安全的时刻，你可以进行“聚集”。要求每连续的 $a$ 个时刻都至少要有 $b$ 个时刻进行聚集，在此前提下希望进行聚集的时刻数量尽量少；若不能满足此前提则认为进行聚集的时刻数量为 $0$。求进行聚集的时刻数量的期望，答案对 $998244353$ 取模。

输入格式

第一行输入三个整数 $n,a,b$，含义如上所述。

接下来 $n$ 行，第 $(i+1)$ 行输入两个整数 $x_i,y_i$，表示第 $i$ 个时刻有 $\frac{x_i}{x_i+y_i}$ 的概率是安全的。

输出格式

输出一个整数，表示期望对 $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

提示

样例说明：

用 1 表示当前时刻是安全的，0 表示不是。

对于样例一，安全性序列只能是 11111，每连续三个时刻至少要有一个时刻用来聚集，可以选择第 $3$ 个时刻聚集，满足条件。聚集时刻数量为 $1$，可以证明不会小于 $1$。只有一种可能性，故期望也为 $1$。

对于样例二，安全性序列为 100，101，110，111 的概率相等，均为 $\frac14$，聚集时刻数量分别为 $0,2,1,1$，期望为 $\frac{0+2+1+1}4=1$。

---

数据范围：

本题采用捆绑测试。

编号	限制	分数
0	$n\le20$	10pts
1	$\forall i$，$x_i=0$ 或 $y_i=0$
2	$n\le3\times 10^3$	30pts
3	无	50pts

对于 $100\%$ 的数据，$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$。