Jožko má playlist pozostávajúci z $n$ pesničiek. Každá pesnička je charakterizovaná svojim žánrom (klasika, pop...). V záležitosti na jeho nálade chce Jožko počúvať pesničky rôznych žánrov — pre každú náladu vie, ktorých $l$ žánrov sa mu páči; všetky ostatné žánre sa mu vtedy nepáčia.
Chcel by si počúvnut nejaký súvislý úsek jeho playlistu — teda vyberie si začiatočnú a konečnú pesničku, a vypočuje si všetky pesničky medzi nimi v danom poradí, bez preskakovania. Je ochotný pritom tolerovať niekoľko pesničiek iných žánrov ako tie, ktoré sa mu momentálne páčia, ale nie viac ako $t$.
Jožko by chcel vedieť, koľko rôznych postupností pesničiek si môže vypočut — teda koľko rôznych súvislých úsekov jeho playlistu obsahuje najviac $t$ pesničiek iných žánrov ako tých, ktoré sa mu práve páčia. Dve postupnosti pesničiek sú rôzne, ak sa ich zápis (každá pesnička reprezentovaná jej žánrom) líši aspoň na jednej pozícií (Jožko teda dve pesničky rovnakého žánru považuje za ekvivalentné).
Žáner pesničky môže byť reprezentovaný malým písmenkom anglickej abecedy; ako dôsledok sa Jožkov playlist dá zapísat ako reťazec dĺžky $n$, a žánre ktoré sa mu páčia ako reťazec dĺžky $l$ pozostávajúci z navzájom rôznych písmen.
Spočítajte koľko existuje rôznych podreťazcov Jožkovho playlistu, ktoré obsahujú najviac $t$ pesničiek iného žánru ako tých ktoré sa mu páčia.
V prvom riadku je kladné číslo $n$: počet pesničiek v Jožkovom playliste. V druhom riadku je $n$ malých písmen anglickej abecedy — samotný playlist. V treťom riadku je číslo $l$: počet žánrov ktoré sa mu páčia. Štvrtý riadok obsahuje $l$ navzájom rôznych písmen — žánre ktoré sa Jožkovi páčia. Piaty a posledný riadok vstupu obsahuje číslo $t$: najväčší počet pesničiek žánrov ktoré sa Jožkovi nepáčia, ale ešte ich bude tolerovať.
Vypíšte jediné číslo — počet rôznych podreťazcov Jožkovho playlistu, ktoré obsahujú najviac $t$ pesničiek iného žánru ako tých ktoré sa mu páčia.
Je päť sád vstupov.
V prvej je $n$ najviac $10$.
V druhej, $500$.
V ostatných neprekročí $2\,048$.
$0 \leq l \leq 26$, $0 \leq t \leq 2\,048$.
4
bbbc
1
b
0
3
7
abacaba
1
a
1
9