Fete și Băieți

Fetiţele şi băieţii Powerpraff s-au aşezat într-un şir $s$ de lungime $K$, ei fiind reprezentaţi în şir prin caracterele f şi b. Cum până la apariţia noilor episoade s-a descoperit şi clonarea, acest şir a fost multiplicat de $N$ ori, iar şirul nou obţinut, de lungime $N \cdot K$, se aşează în ordine, pe linii de câte $D$ caractere. Doi băieţi sunt prieteni dacă se învecinează pe orizontală sau verticală în noua aşezare pe linii. Doi băieţi $B_x$ şi $B_y$ sunt în aceeaşi gaşcă dacă sunt prieteni sau dacă există un şir de băieţi $B_1, B_2, \dots, B_m$ (eventual $m$ poate fi şi $0$) astfel încât în şirul $B_x, B_1, B_2, \dots, B_m, B_y$ oricare doi băieţi alăturaţi sunt prieteni. O gaşcă poate fi formată din cel puţin un băiat.

Cerință

Cunoscând valorile lui $K$, $N$ şi $D$, precum şi caracterele din şirul $s$, aflaţi numărul de găşti care se pot forma, ştiind că fiecare băiat face parte dintr-o singură gaşcă.

Date de intrare

Fișierul de intrare fsb.in conține pe prima linie numerele $K$, $N$ şi $D$, în această ordine, iar pe a doua linie cele $K$ caractere ale şirului $s$.

Date de ieșire

Fișierul de ieșire fsb.out va conține pe prima linie numărul găştilor care se pot forma.

Restricții și precizări

• $1 \leq K \leq D \leq 2 \ 000$
• $1 \leq N \leq 1 \ 000 \ 000$
• $N$ este divizibil cu $D$.
• Pentru teste în valoare de $23$ de puncte avem $K = D$.
• Pentru alte teste, în valoare de $31$ de puncte, avem $N = D$ și $K < D$.
• Pentru alte teste, în valoare de $46$ de puncte, nu avem alte restricții.

Exemplul 1

fsb.in

3 3 3
fbb

fsb.out

1

Explicație

După multiplicarea de $3$ ori şirul $s =$ fbb devine fbbfbbfbb. Acesta se aşează pe linii de lungime $3$, obţinându-se aşezarea:

fbb
fbb
fbb

Se formează o gaşcă, toţi băieţii fiind în aceeaşi gaşcă.

Exemplul 2

fsb.in

2 3 3
fb

fsb.out

3

Explicație

După multiplicarea de $3$ ori, şirul $s =$ fb devine fbfbfb. Acesta se aşează pe linii de lungime $3$, obţinându-se aşezarea:

fbf
bfb

Se obţin $3$ găşti, fiecare formată dintr-un singur băiat.

Exemplul 3

fsb.in

3 8 4
fbb

fsb.out

3

Explicație

După multiplicarea de $8$ ori şirul $s =$ fbb devine fbbfbbfbbfbbfbbfbbfbbfbb. Acesta se aşează pe linii de lungime $4$, obţinându-se:

fbbf
bbfb
bfbb
fbbf
bbfb
bfbb

Se obțin $3$ găști.