409830: GYM103800 G Ginger's password
Description
Ginger forgot his password, but Ginger has a habit of setting passwords, except for the first bit, each bit is not lexicographically smaller than the previous bit, in another word, the entire password string is non-descending, and each letter has a number limit.
Now Ginger only remembers a subsequence of the password string $$$s$$$ and the length of the original password string $$$k$$$. Can you help Ginger calculate how many possible original password string modulo $$$998\,244\,353$$$.
If the original password is not found, output $$$\text{NO SOLUTION!}$$$
InputThe first line contains two integers $$$n, k$$$ $$$(1\le n,k \le 2 \times 10 ^ 3)$$$ indicating the lenth of the password string subsequence that Ginger remembers and the lenth of entire password string.
The second line contains $$$26$$$ integers $$$a_1,a_2,\cdots,a_n$$$ $$$(0 \le a_i \le 10 ^ 9)$$$ indicating Occurrence limit of each letter from $$$\texttt{a}$$$ to $$$\texttt{z}$$$.
The third line contains a string $$$s$$$, contains only lowercase letters.
OutputPrint the ways of possible original password string modulo $$$998\,244\,353$$$ if it's exist,
otherwise print $$$\text{NO SOLUTION!}$$$
ExamplesInput3 3 1 1 4 5 1 4 1 9 1 9 8 1 0 1 1 4 5 1 4 1 9 1 9 8 1 0 abcOutput
1Input
3 4 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 aabOutput
NO SOLUTION!Note
Subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements.