Problem Description

The four bases of a DNA molecule are denoted as A, T, G, and C. Each person’s gene sequence can be regarded as a string of length $n$ consisting of the four characters A, T, G, and C.

Xiaolan is studying a disease. He observes that this disease has a fixed susceptible sequence (which can also be regarded as a string consisting of A, T, G, and C). If a person’s gene sequence contains a substring that is exactly equal to this susceptible sequence, then this person is called “susceptible”. If none of the substrings of the gene sequence is equal to this susceptible sequence, then this person is called “not susceptible”.

Xiaolan hopes to estimate the proportion of “susceptible” people in the city based on the gene sequences of the population.

However, it is very difficult to directly obtain the complete gene sequence of every person in the city. Therefore, Xiaolan uses sampling statistics: through extensive sampling, he estimates, for each position in the city, the proportion of people whose base at that position is A, T, G, or C. We can understand this as: among all people’s gene sequences, what are the proportions of A, T, G, and C at the $i$-th position, respectively.

To simplify the model, Xiaolan makes the following assumption: for any person, the base distribution at each position of their gene sequence is exactly the same as the sampling result, and bases at different positions are independent. That is, even if the bases at some positions are already determined, the bases at the remaining positions are still generated independently according to the distributions of the corresponding positions.

Now, Xiaolan decides to compute these probabilities modulo $998244353$: if the proportion of “susceptible” people is $\frac{p}{q}$, then Xiaolan wants to obtain an integer $x$ such that $x \times q \equiv p \pmod{998244353}$. Given the susceptible sequence and the probability distribution of the four bases at each position, please help Xiaolan compute and output this integer $x$.

Input Format

The first line contains two positive integers $n, m$, representing the length of the gene sequence and the length of the susceptible sequence, respectively.

The second line contains a string $s$ of length $m$, consisting only of A, T, G, and C, representing the susceptible sequence corresponding to the disease.

The next $n$ lines each contain four non-negative integers $a_i, t_i, g_i, c_i$. Here:

• $a_i$ denotes the probability that the base at position $i$ is A (modulo $998244353$).
• $t_i$ denotes the probability that the base at position $i$ is T (modulo $998244353$).
• $g_i$ denotes the probability that the base at position $i$ is G (modulo $998244353$).
• $c_i$ denotes the probability that the base at position $i$ is C (modulo $998244353$).

It is guaranteed that for any $i$, $(a_i + t_i + g_i + c_i) \bmod 998244353 = 1$.

Output Format

Output one line containing a non-negative integer, representing the proportion of people whose gene sequence contains the susceptible sequence as a substring, under modulo $998244353$.

3 2
AA
499122177 499122177 0 0
499122177 0 499122177 0
499122177 0 0 499122177

623902721

Hint

Sample Explanation

The gene sequence has $3$ positions:

• At position $1$, the probability is $\frac{1}{2}$ to be $A$, and $\frac{1}{2}$ to be $T$.
• At position $2$, the probability is $\frac{1}{2}$ to be $A$, and $\frac{1}{2}$ to be $G$.
• At position $3$, the probability is $\frac{1}{2}$ to be $A$, and $\frac{1}{2}$ to be $C$.

The susceptible sequence is $AA$. Therefore, a person is considered “susceptible” if and only if their gene sequence contains the substring $AA$.

Among all possible generated gene sequences, there are $3$ that satisfy the condition: $AAC$, $TAA$, and $AAA$. Each of these three sequences occurs with probability $\frac{1}{8}$, so the total proportion of “susceptible” people is $\frac{1}{8} + \frac{1}{8} + \frac{1}{8} = \frac{3}{8}$, and its result modulo $998244353$ is $623902721$.

Constraints

For $30\%$ of the testdata, $1 \le m \le n \le 5$.

There is another $20\%$ of the testdata where $a_i = t_i = g_i = c_i$.

For $100\%$ of the testdata, $1 \le m \le n \le 3000$, $0 \le a_i, t_i, g_i, c_i < 998244353$.

Translated by ChatGPT 5