追寻 | Pursuit of Dream

“遇到自己喜欢的人或事情的时候，千万不要放弃” “要一直追寻下去…” “因为即使成功希望渺茫，也有可能” 有谁和我说过这句话，脑海中忽然闪过一下，被当做无用的激励一同忘却了。现在想要回忆，却总也记不起来。 好不容易来人间一趟，那就别留下遗憾。 房檐落下的雨滴有规律的敲着石砖，那夜的雨声中，却也悄无声息了。 逆着风吹干眼泪，说不出口的痛越藏越多，腐烂在肚子里，却又不知道彼此心知且肚明，所以无法孕育出美好的结局，只会是恋者相残的戏码不停上演。 --- 看见了漫天星野坠落在你的眼底，从此甘愿在那海底般低压的梦境中堕落。 三千尺星空的光辉映照不出那人的身影，璀璨中徒留神明思故人；那人却散入了或许碎散的星辰大海，让神明寻觅了一生。 那些无法兑现的渴望，会日渐荒芜，然后梦境会失去生机，裂缝中会蔓出黑暗，泪无葬身之地。 是神明告诉我的，可是我不信，因为没有时间还等着我空想了。 神明还说，人死了以后，提前离开的亲人都会在另外一个世界等你。 其实，我也会想，这一定就是另外一个世界。

在 $n$ 维空间中有一个梦想。这梦想坐落在 $(d_1, d_2, \ldots, d_n)$ 的地方。而你从 $(0, 0, \ldots, 0)$ 开始，开启寻梦的旅程。 你的步伐轻缓，每一步只能走一个单位长度。你并不知道你的梦想位于哪里，所以你只能随机选择 $n$ 个正方向中的一个，然后向这个方向走一步。也就是说，在 $[1, n]$ 中均匀随机选择一个正整数 $h$，然后，使你在第 $h$ 维的坐标变成原来的坐标加一。 然而，天有不测风云。在你走每一步的过程中，你会有 $p = \sum_{i = 1}^k p_i$ 的概率散入天际，并开始一段新的旅程。你会在 $k$ 个地点中的一个重新开始这段旅程，其中第 $i$ 个地点的坐标是 $(a_{i,1}, a_{i,2}, \ldots, a_{i,n})$，从这里重新开始的概率为 $p_i$。 那么，期望下，你离到达这个梦想还需要多少步呢？

第一行，两个正整数 $n,k$。 第二行，$n$ 个非负整数 $d_1, d_2, \ldots, d_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}$。 输入的 $x_i$ 保证了 $p_i > 0$ 且 $p < 1$。 保证每个 $x_i$ 在所有可能的组合中等概率随机生成。

一行，一个整数，表示答案对 $998244353$ 取模的结果。 如果你不知道如何进行实数取模：可以说明答案一定是有限的，且是有理数，设它的最简分数形式为 $\frac{p}{q}$。如果存在一个整数 $x$ 满足 $x \cdot q \equiv p \pmod{998244353}$ 且 $0 \le x < 998244353$，那么你只需输出 $x$ 的值即可。 由于保证了 $x_i$ 是随机生成的，可以说明以接近 $1$ 的概率答案在模意义下存在。事实上，一个当 $x_i$ 尚不确定时以合理地高的概率给出正确答案的算法足以通过本题，考察复杂的模意义下的有理数的处理不是我们的本意。

2 1
1 1
0 0 50000000

14

2 1
1 2
0 0 20000000

291154624

3 3
2 3 4
2 1 0 30000000
1 2 3 19000000
2 3 4 1000000

430536142

**【样例解释 \#1】** 这是你的一种追寻梦想的方式： 你从 $(0,0)$ 出发，走一步到 $(1,0)$，再走一步到 $(2,0)$，再走一步到 $(3,0)$，但是在路上散入天际，从 $(0,0)$ 重新开始旅程。 然后继续从 $(0,0)$ 出发，走一步到 $(0,1)$，再走一步到 $(1,1)$，但是在路上散入天际，从 $(0,0)$ 重新开始旅程。 接着从 $(0,0)$ 出发，走一步到 $(1,0)$，再走一步到 $(1,1)$，找到了你的梦想。 在这种情况下，你需要 $7$ 步到达这个梦想。发生这种情况的概率是 $4^{-7}$。 --- **【样例解释 \#2】** 答案为 $\frac{505}{24} \approx 21.041667$。 不难验证 $291154624 \times 24 \equiv 505 \pmod{998244353}$，故应输出 $291154624$。 --- **【样例解释 \#3】** 答案为 $\frac{1399505}{21519} \approx 65.035782$。 --- **【数据范围】** **本题采用捆绑测试且使用子任务依赖。** | 子任务编号 | 特殊限制 | 分值 | | :----------: | :----------: | :----------: | | 1 | $n=1$，$k=1$ | 11 | | 2 | $n=1$ | 12 | | 3 | $k=1$ | 12 | | 4 | $n=2$，$1 \le d_1 \cdot d_2 \le 200$ | 13 | | 5 | $k \le 200$ | 22 | | 6 | 无特殊限制 | 30 | 对于 $100 \%$ 的数据： - $1 \le n \le 100$，$1 \le k \le 10000$。 - $d_i \ge 0$，$\sum_i d_i \le 10^7$。 - $0 \le a_{i, j} \le {10}^7$。 - $x_i \ge 1$，$\sum_i x_i < {10}^8$。此即保证了 $p_i > 0$ 和 $p < 1$。 - 保证存在一个 $i \in [1, k]$ 使得对于每个 $j \in [1, n]$ 均有 $a_{i,j} \le d_j$。 - 保证每个 $(a_{i, 1}, a_{i, 2}, \ldots, a_{i, n})$ 作为空间中的点互不相同。 - 保证每个 $x_i$ 在所有可能的组合中等概率随机生成。 --- **【提示】** 由于保证了 $x_i$ 是随机生成的，可以说明以接近 $1$ 的概率答案在模意义下存在。事实上，一个当 $x_i$ 尚不确定时以合理地高的概率给出正确答案的算法足以通过本题，考察复杂的模意义下的有理数的处理不是我们的本意。 样例中的 $x_i$ 不是随机生成的，仅为理解题意所用。