Micul String

Se numește subsecvență a unui șir de caractere $s$ un șir de caractere $t$ cu proprietatea că există doi indici $i$ și $j$ cu $0 \leq i \leq j < |s|$ astfel încât $t=\overline{s_is_{i+1}s_{i+2}...{s_j}}$.

Pentru un tuplu de șiruri de caractere $(s_0, s_1, s_2, ..., s_{K-1})$ vom defini $f(s_0,s_1,s_2,...,s_{K-1})$ ca fiind șirul minim lexicografic$^1$ ce se poate obține prin următorul procedeu:

• Pentru fiecare șir $s_i$, se alege o subsecvență nevidă $t_i$ a sa;
• Se concatenează $t_0, t_1, t_2,..., t_{K-1}$, șirul obținut fiind rezultatul procedeului.

$^1$ Un șir de caractere $\overline{a_0a_1 \ldots a_{n-1}}$ este mai mic lexicografic decât un alt șir de caractere $\overline{b_0b_1 \ldots b_{m-1}}$ dacă și numai dacă:

• Există un indice $i$ ($0 \le i < \min(n,m)$) pentru care $\overline{a_0a_1 \ldots a_{i-1}}=\overline{b_0b_1 \ldots b_{i-1}}$ și $a_i<b_i$; sau
• $n<m$ și $\overline{a_0a_1 \ldots a_{n-1}}=\overline{b_0b_1 \ldots b_{n-1}}$.

Cerință

Se dau un număr natural $N$, un șir de caractere de lungime $N$, notat $w$, un număr natural $K$ și un șir de $K$ numere naturale nenule $l_0, l_1, l_2,..., l_{K-1}$. Să se numere câte tupluri de $K$ șiruri de caractere, $(s_0, s_1, s_2, ..., s_{K-1})$ respectă următoarele condiții:

• Toate șirurile conțin doar litere mici ale alfabetului englez
• $|s_i|=l_i$, $\forall 1 \leq i \leq K$
• $f(s_0, s_1, s_2, ..., s_{K - 1})=w$

Deoarece acest număr poate fi mare, se cere restul acestuia la împărțirea prin $998 \ 244 \ 353$.

Detalii de implementare

Concurenții vor avea de implementat o singură funcție:

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

care primește ca parametri:

• $N$, numărul de caractere din șirul $w$
• $K$, numărul de șiruri dintr-un tuplu
• Șirul $w$ (indexat de la $0$)
• $l$, reprezentând lungimile șirurilor (indexat de la $0$)

Funcția solve va fi apelată o singură dată.

Restricții

• $1 \leq K \leq N \leq 200$
• $1 \leq l_i \leq 200$, $0 \leq i \leq N - 1$
• Șirul $w$ este format doar din litere mici ale alfabetului englez
• Vom considera $w_i$ al $i$-lea caracter din șirul $w$

Exemplul 1

input

4 3
babz
1 2 1

output

1

Explicație

Pentru primul exemplu, singurul tuplu valid este ("b", "ab", "z").

Exemplul 2

input

4 3
babz
1 3 1

output

26

Exemplul 3

input

6 4
abcbzz
3 3 3 3

output

1849