== include(page="template/taskheader" task_id="miculstring") ==

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 &le; i &le; j < |s|$ astfel încât $t = s{~i~}s{~i+1~}s{~i+2~}&hellip;s{~j~}$.

Poveste şi cerinţă...

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* ce se poate obţine prin următorul procedeu:

h2. Date de intrare

* 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.

Fişierul de intrare $miculstring.in$ ...

Un şir de caractere $a{~0~}a{~1~}…a{~n-1~}$ este mai mic lexicografic decât un alt şir de caractere $b{~0~}b{~1~}…b{~m-1~}$ dacă şi numai dacă:

h2. Date de ieşire

* Există un indice $i$ $0 &le; i < min(n, m)$ pentru care $a{~0~}a{~1~}&hellip;a{~i-1~} = b{~0~}b{~1~}&hellip;b{~i-1~}$ şi $a{~i~} < b{~i~}$; sau
* $n < m$ şi $a{~0~}a{~1~}&hellip;a{~n-1~} = b{~0~}b{~1~}&hellip;b{~n-1~}$.

În fişierul de ieşire $miculstring.out$ ...

h2. 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~}$, $∀ 1 ≤ i ≤ 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$.
 
h2. Detalii de implementare
 
Concurenţii vor avea de implementat o singură funcţie:
 
bc. 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ă per proces.
 
{**Din cauza limitărilor impuse de infoarena şi pentru a reproduce condiţiile din concurs, recomandăm să foloseşti template-urile de 'aici':problema/miculstring?template.cpp .**}

h2. Restricţii

{**Totodată, unele teste au fost omise. Prin urmare, în situaţii rare pot exista diferenţe între punctajul de pe inforarena şi punctajul care s-ar fi obţinut în concurs .**}

* $... ≤ ... ≤ ...$

h2. Restricţii

h2. Exemplu

* $1 ≤ K ≤ N ≤ 200$
* $1 ≤ l{~i~} ≤ 200$, $0 ≤ i ≤ N - 1$
* Şirul $w$ este format doar din litere mici ale alfabetului englez.
* Vom considera $w{~i~}$ al $i$-lea caracter din şirul $w$.
 
table(example). |_. # |_. Punctaj |_. Restricţii |
| $1$ | $7$  | $1 ≤ K ≤ N ≤ 7$, $∑{~i=0~}^{K-1}^ l{~i~} ≤ 8$ şi $w$ conţine doar caracterele $a$, $b$, $c$, $d$ |
| $2$ | $8$  | $1 &le; K &le; N &le; 25$ şi $l{~i~} = 3$, $&forall; 0 &le; i < N$ |
| $3$ | $11$ | $K = 2$ |
| $4$ | $14$ | $1 &le; K &le; N &le; 120$, $1 &le; l{~i~} &le; 120$ şi $w{~i~} &le; w{~i+1~}$, $&forall; 0 &le; i < N - 1$ (şirul $w$ este crescător) |
| $5$ | $23$ | $1 &le; K &le; N &le; 90$ şi $1 &le; l{~i~} &le; 90$, $&forall; 0 &le; i < N$ |
| $6$ | $21$ | $1 &le; K &le; N &le; 150$ şi $1 &le; l{~i~} &le; 150$, $&forall; 0 &le; i < N$ |
| $7$ | $16$ | Fără restricţii suplimentare |
 
h2. Exemple
 
table(example). |_. Fişier de intrare |_. Fişier de ieşire |
| 4 3
babz
1 2 1
| 1
|
| 4 3
babz
1 3 1
| 26
|
| 6 4
abcbzz
3 3 3 3
| 1849
|

table(example). |_. miculstring.in |_. miculstring.out |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|

h3. Explicaţii

h3. Explicaţie

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

...

== include(page="template/taskfooter" task_id="miculstring") ==

== include(page="template/taskfooter" task_id="miculstring") ==