microvirus
Un microcontroller poate
fi considerat un microprocesor in miniatura: are registri, memorie, executa
instructiuni dar toate sunt la dimensiuni mult mai mici. Atat de mici, incat
s-ar putea numara cate programe diferite se pot scrie pentru un
anume microcontroller.
Vom considera setul de instructiuni al unui microcontroller
ca fiind o multime de simboluri sigma={s1,s2,...,sk}.
Un program de lungime N, este un sir de N astfel de
simboluri din sigma.
Desi microcontroller-ele au aceste limitari, autorii
de virusi nu au fost intimidati si ca atare exista in circulatie mai multi
virusi foarte periculosi. Un virus este tot un program,
deci va fi definit ca mai sus.
Cerinta
Se cere sa numarati cate programe
de lungime N se pot scrie pentru microcontroller, care nu contin virusul dat.
Date de intrare
s1s2
... sK
v1v2
... vM
N
Prima linie a fisierului microvirus.in va contine multimea sigma,
formata din K simboluri distincte. Un simbol este un caracter din multimea {A..Z,a..z,0..9}.
A doua linie va contine programul
virusului, care este un sir de M simboluri din sigma (nu neaparat distincte).
A treia linie contine numarul intreg N.
Fisierul de intrare nu contine spatii.
Date de iesire
Se va scrie pe prima linie a
fisierului microvirus.out un numar intreg reprezentand cate programe de
lungime N exista, care nu contin virusul.
Restrictii
1 < K <=50
1 <=M <=N <=50
Numarul cerut va fi mai mic decat 263.
Exemplu
|
microvirus.in |
microvirus.out |
|
ab ab 3 |
4 |
Timp maxim de executie/test: 0.1 secunde
Batog Bogdan
UPB
bbbb@ss.pub.ro