{"raw_statement":[{"iden":"background","content":"“遇到自己喜欢的人或事情的时候，千万不要放弃”\n\n“要一直追寻下去…”\n\n“因为即使成功希望渺茫，也有可能”\n\n有谁和我说过这句话，脑海中忽然闪过一下，被当做无用的激励一同忘却了。现在想要回忆，却总也记不起来。\n\n好不容易来人间一趟，那就别留下遗憾。\n\n房檐落下的雨滴有规律的敲着石砖，那夜的雨声中，却也悄无声息了。\n\n逆着风吹干眼泪，说不出口的痛越藏越多，腐烂在肚子里，却又不知道彼此心知且肚明，所以无法孕育出美好的结局，只会是恋者相残的戏码不停上演。\n\n---\n\n 看见了漫天星野坠落在你的眼底，从此甘愿在那海底般低压的梦境中堕落。\n\n三千尺星空的光辉映照不出那人的身影，璀璨中徒留神明思故人；那人却散入了或许碎散的星辰大海，让神明寻觅了一生。\n\n那些无法兑现的渴望，会日渐荒芜，然后梦境会失去生机，裂缝中会蔓出黑暗，泪无葬身之地。\n\n是神明告诉我的，可是我不信，因为没有时间还等着我空想了。\n\n神明还说，人死了以后，提前离开的亲人都会在另外一个世界等你。\n\n其实，我也会想，这一定就是另外一个世界。"},{"iden":"statement","content":"在 $n$ 维空间中有一个梦想。这梦想坐落在 $(d_1, d_2, \\ldots, d_n)$ 的地方。而你从 $(0, 0, \\ldots, 0)$ 开始，开启寻梦的旅程。\n\n你的步伐轻缓，每一步只能走一个单位长度。你并不知道你的梦想位于哪里，所以你只能随机选择 $n$ 个正方向中的一个，然后向这个方向走一步。也就是说，在 $[1, n]$ 中均匀随机选择一个正整数 $h$，然后，使你在第 $h$ 维的坐标变成原来的坐标加一。\n\n然而，天有不测风云。在你走每一步的过程中，你会有 $p = \\sum_{i = 1}^k p_i$ 的概率散入天际，并开始一段新的旅程。你会在 $k$ 个地点中的一个重新开始这段旅程，其中第 $i$ 个地点的坐标是 $(a_{i,1}, a_{i,2}, \\ldots, a_{i,n})$，从这里重新开始的概率为 $p_i$。\n\n那么，期望下，你离到达这个梦想还需要多少步呢？"},{"iden":"input","content":"第一行，两个正整数 $n,k$。\n\n第二行，$n$ 个非负整数 $d_1, d_2, \\ldots, d_n$。\n\n接下来 $k$ 行，第 $i$ 行 $n + 1$ 个整数 $a_{i, 1}, a_{i, 2}, \\ldots, a_{i, n}, x_i$，每行最后一个整数 $x_i$ 表示 $p_i=x_i\\times 10^{-8}$。\n\n输入的 $x_i$ 保证了 $p_i > 0$ 且 $p < 1$。\n\n保证每个 $x_i$ 在所有可能的组合中等概率随机生成。"},{"iden":"output","content":"一行，一个整数，表示答案对 $998244353$ 取模的结果。\n\n如果你不知道如何进行实数取模：可以说明答案一定是有限的，且是有理数，设它的最简分数形式为 $\\frac{p}{q}$。如果存在一个整数 $x$ 满足 $x \\cdot q \\equiv p \\pmod{998244353}$ 且 $0 \\le x < 998244353$，那么你只需输出 $x$ 的值即可。\n\n由于保证了 $x_i$ 是随机生成的，可以说明以接近 $1$ 的概率答案在模意义下存在。事实上，一个当 $x_i$ 尚不确定时以合理地高的概率给出正确答案的算法足以通过本题，考察复杂的模意义下的有理数的处理不是我们的本意。"},{"iden":"note","content":"**【样例解释 \\#1】**\n\n这是你的一种追寻梦想的方式：\n\n你从 $(0,0)$ 出发，走一步到 $(1,0)$，再走一步到 $(2,0)$，再走一步到 $(3,0)$，但是在路上散入天际，从 $(0,0)$ 重新开始旅程。\n\n然后继续从 $(0,0)$ 出发，走一步到 $(0,1)$，再走一步到 $(1,1)$，但是在路上散入天际，从 $(0,0)$ 重新开始旅程。\n\n接着从 $(0,0)$ 出发，走一步到 $(1,0)$，再走一步到 $(1,1)$，找到了你的梦想。\n\n在这种情况下，你需要 $7$ 步到达这个梦想。发生这种情况的概率是 $4^{-7}$。\n\n---\n\n**【样例解释 \\#2】**\n\n答案为 $\\frac{505}{24} \\approx 21.041667$。  \n不难验证 $291154624 \\times 24 \\equiv 505 \\pmod{998244353}$，故应输出 $291154624$。\n\n---\n\n**【样例解释 \\#3】**\n\n答案为 $\\frac{1399505}{21519} \\approx 65.035782$。\n\n---\n\n**【数据范围】**\n\n**本题采用捆绑测试且使用子任务依赖。**\n\n| 子任务编号 | 特殊限制 | 分值 |\n| :----------: | :----------: | :----------: |\n| 1 | $n=1$，$k=1$ | 11 |\n| 2 | $n=1$ | 12 |\n| 3 | $k=1$ | 12 |\n| 4 | $n=2$，$1 \\le d_1 \\cdot d_2 \\le 200$ | 13 |\n| 5 | $k \\le 200$ | 22 |\n| 6 | 无特殊限制 | 30 |\n\n对于 $100 \\%$ 的数据：\n\n- $1 \\le n \\le 100$，$1 \\le k \\le 10000$。\n- $d_i \\ge 0$，$\\sum_i d_i \\le 10^7$。\n- $0 \\le a_{i, j} \\le {10}^7$。\n- $x_i \\ge 1$，$\\sum_i x_i < {10}^8$。此即保证了 $p_i > 0$ 和 $p < 1$。\n- 保证存在一个 $i \\in [1, k]$ 使得对于每个 $j \\in [1, n]$ 均有 $a_{i,j} \\le d_j$。\n- 保证每个 $(a_{i, 1}, a_{i, 2}, \\ldots, a_{i, n})$ 作为空间中的点互不相同。\n- 保证每个 $x_i$ 在所有可能的组合中等概率随机生成。\n\n---\n\n**【提示】**\n\n由于保证了 $x_i$ 是随机生成的，可以说明以接近 $1$ 的概率答案在模意义下存在。事实上，一个当 $x_i$ 尚不确定时以合理地高的概率给出正确答案的算法足以通过本题，考察复杂的模意义下的有理数的处理不是我们的本意。\n\n样例中的 $x_i$ 不是随机生成的，仅为理解题意所用。"}],"translated_statement":null,"sample_group":[["2 1\n1 1\n0 0 50000000\n","14\n"],["2 1\n1 2\n0 0 20000000\n","291154624\n"],["3 3\n2 3 4\n2 1 0 30000000\n1 2 3 19000000\n2 3 4 1000000\n","430536142\n"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}