{"raw_statement":[{"iden":"background","content":"-传播-由-缺失-它们-子民-思想-哦-思想-信念-\n\n-它们-途径-缺失-切除-哦-虚空-全部-多样性-\n\n-同族-内部-意志-缺失-容器-永远-屈服-哦-\n\n-放-入-物质-全部-缺失-噫-空洞-壳-封印-"},{"iden":"statement","content":"一场战斗由 $n$ 个时刻组成，第 $i$ 个时刻有 $\\frac{x_i}{x_i+y_i}$ 的概率是安全的。\n\n在安全的时刻，你可以进行“聚集”。要求每连续的 $a$ 个时刻都至少要有 $b$ 个时刻进行聚集，在此前提下希望进行聚集的时刻数量尽量少；若不能满足此前提则认为进行聚集的时刻数量为 $0$。求进行聚集的时刻数量的期望，答案对 $998244353$ 取模。"},{"iden":"input","content":"第一行输入三个整数 $n,a,b$，含义如上所述。\n\n接下来 $n$ 行，第 $(i+1)$ 行输入两个整数 $x_i,y_i$，表示第 $i$ 个时刻有 $\\frac{x_i}{x_i+y_i}$ 的概率是安全的。"},{"iden":"output","content":"输出一个整数，表示期望对 $998244353$ 取模的值。"},{"iden":"note","content":"### 样例说明：\n\n用 `1` 表示当前时刻是安全的，`0` 表示不是。\n\n对于样例一，安全性序列只能是 `11111`，每连续三个时刻至少要有一个时刻用来聚集，可以选择第 $3$ 个时刻聚集，满足条件。聚集时刻数量为 $1$，可以证明不会小于 $1$。只有一种可能性，故期望也为 $1$。\n\n对于样例二，安全性序列为 `100`，`101`，`110`，`111` 的概率相等，均为 $\\frac14$，聚集时刻数量分别为 $0,2,1,1$，期望为 $\\frac{0+2+1+1}4=1$。\n\n---\n\n### 数据范围：\n\n**本题采用捆绑测试。**\n\n| 编号| 限制 | 分数 |\n| :-: | :-: | :-: |\n| 0 | $n\\le20$ | 10pts |\n| 1 | $\\forall i$，$x_i=0$ 或 $y_i=0$ | 10pts |\n| 2 | $n\\le3\\times 10^3$ | 30pts |\n| 3 | 无 | 50pts |\n\n对于 $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$。"}],"translated_statement":null,"sample_group":[["5 3 1\n1 0\n2 0\n3 0\n4 0\n114514 0","1"],["3 2 1\n1 0\n1 1\n1 1","1"],["4 2 1\n3 2\n2 0\n1 1\n3 1","249561090"],["15 5 2\n4 0\n2 0\n3 1\n0 1\n1 4\n2 0\n0 4\n1 4\n0 4\n1 0\n2 2\n4 1\n0 4\n1 0\n4 0","63887640"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}