Problem Description

In an $n$-dimensional space, there is a dream located at $(d_1, d_2, \ldots, d_n)$. You start your journey from $(0, 0, \ldots, 0)$.

Your steps are gentle; each step can only move one unit length. You don't know where your dream is, so you can only randomly choose one of the $n$ positive directions and move one step in that direction. That is, uniformly randomly select an integer $h$ from $[1, n]$, and then increase your coordinate in the $h$-th dimension by one.

However, unpredictable events may occur. At each step, there is a probability $p = \sum_{i = 1}^k p_i$ that you will scatter into the sky and start a new journey. You will restart this journey at one of $k$ locations, where the coordinates of the $i$-th location are $(a_{i,1}, a_{i,2}, \ldots, a_{i,n})$, and the probability of restarting from here is $p_i$.

What is the expected number of steps you need to reach the dream?

Input Format

The first line contains two positive integers $n, k$.

The second line contains $n$ non-negative integers $d_1, d_2, \ldots, d_n$.

The next $k$ lines, the $i$-th line contains $n + 1$ integers $a_{i, 1}, a_{i, 2}, \ldots, a_{i, n}, x_i$, where $x_i$ represents $p_i = x_i \times 10^{-8}$.

The input guarantees that $p_i > 0$ and $p < 1$.

Each $x_i$ is randomly generated with equal probability among all possible combinations.

Output Format

One line, an integer representing the result modulo $998244353$.

If you don't know how to perform modulo with real numbers: the answer is guaranteed to be finite and rational. Let its simplest fraction form be $\frac{p}{q}$. If there exists an integer $x$ such that $x \cdot q \equiv p \pmod{998244353}$ and $0 \le x < 998244353$, then you just need to output the value of $x$.

Since $x_i$ is guaranteed to be randomly generated, it can be shown that the answer exists modulo $998244353$ with probability close to $1$. In fact, an algorithm that gives a correct answer with a reasonably high probability when $x_i$ is not yet determined is sufficient to pass this problem; examining complex handling of rational numbers under modulo is not our intention.

Sample Input and Output

Input Sample #1

2 1
1 1
0 0 50000000

Output Sample #1

14

Input Sample #2

2 1
1 2
0 0 20000000

Output Sample #2

291154624

Input Sample #3

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

Output Sample #3

430536142

Notes/Hints

Since $x_i$ is guaranteed to be randomly generated, it can be shown that the answer exists modulo $998244353$ with probability close to $1$. In fact, an algorithm that gives a correct answer with a reasonably high probability when $x_i$ is not yet determined is sufficient to pass this problem; examining complex handling of rational numbers under modulo is not our intention.

The $x_i$ in the samples are not randomly generated; they are only for understanding the problem.

见题面 Input 部分

见题面 Output 部分