Description

在 $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$。

那么，期望下，你离到达这个梦想还需要多少步呢？

Input Format

第一行，两个正整数 $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$ 在所有可能的组合中等概率随机生成。

Output Format

一行，一个整数，表示答案对 $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

Hint

【样例解释 #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$。

【数据范围】

本题采用捆绑测试且使用子任务依赖。

对于 $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$ 不是随机生成的，仅为理解题意所用。