Micul String

A subsequence of a string of characters $s$ is a string of characters $t$ with the property that there exist two indices $i$ and $j$ with $0 \leq i \leq j < |s|$ such that $t=\overline{s_is_{i+1}s_{i+2}...{s_j}}$.

For a tuple of strings $(s_0, s_1, s_2, ..., s_{K-1})$ we define $f(s_0,s_1,s_2,...,s_{K-1})$ as the lexicographically smallest$^1$ string that can be obtained through the following procedure:

• For each string $s_i$, choose a nonempty substring $t_i$ of it;
• Concatenate $t_0, t_1, t_2,..., t_{K-1}$, the resulting string being the outcome of the procedure.

$^1$ A string $\overline{a_0a_1 \ldots a_{n-1}}$ is lexicographically smaller than another string $\overline{b_0b_1 \ldots b_{m-1}}$ if and only if:

• There exists an index $i$ ($0 \le i < \min(n,m)$) for which $\overline{a_0a_1 \ldots a_{i-1}}=\overline{b_0b_1 \ldots b_{i-1}}$ and $a_i<b_i$; or
• $n<m$ and $\overline{a_0a_1 \ldots a_{n-1}}=\overline{b_0b_1 \ldots b_{n-1}}$.

Requirement

You are given a natural number $N$, a string of length $N$ denoted $w$, a natural number $K$, and a sequence of $K$ nonzero natural numbers $l_0, l_1, l_2,..., l_{K-1}$. Count how many tuples of $K$ strings, $(s_0, s_1, s_2, ..., s_{K-1})$ satisfy the following conditions:

• All strings contain only lowercase letters of the English alphabet
• $|s_i|=l_i$, $\forall 1 \leq i \leq K$
• $f(s_0, s_1, s_2, ..., s_{K - 1})=w$

Since this number can be large, output its remainder modulo $998 \ 244 \ 353$.

Implementation Details

You must implement a single function:

int solve(int N, int K, std::string w, std::vector<int> l);

which receives as parameters:

• $N$, the number of characters in the string $w$
• $K$, the number of strings in a tuple
• The string $w$ (indexed from $0$)
• $l$, representing the lengths of the strings (indexed from $0$)

The solve function will be called exactly once.

Constraints

• $1 \leq K \leq N \leq 200$
• $1 \leq l_i \leq 200$, $0 \leq i \leq N - 1$
• The string $w$ consists only of lowercase letters of the English alphabet
• We denote by $w_i$ the $i$-th character of the string $w$

Example 1

input

4 3
babz
1 2 1

output

1

Explanation

For the first example, the only valid tuple is ("b", "ab", "z").

Example 2

input

4 3
babz
1 3 1

output

26

Example 3

input

6 4
abcbzz
3 3 3 3

output

1849