3777 PBINFO


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 x 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 Bx şi By sunt în aceeaşi gaşcă dacă sunt prieteni sau dacă există un şir de băieţi B1, B2, …, Bm (eventual m poate fi şi 0) astfel încât în şirul Bx, B1, B2, …, Bm, By oricare doi băieţi alăturaţi sunt prieteni. O gaşcă poate fi formată din cel puţin un băiat.

Cerința
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 fetesibaieti.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 fetesibaieti.out va conține pe prima linie numărul găştilor care se pot forma.

Restricții și precizări
1 ≤ K ≤ D ≤ 2.000
1 ≤ N ≤ 1.000.000
N este divizibil cu D.
Exemplul 1:
fetesibaieti.in

3 3 3
fbb
fetesibaieti.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:
fetesibaieti.in

2 3 3
fb
fetesibaieti.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:
fetesibaieti.in

3 8 4
fbb
fetesibaieti.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.