3. Základ úspechu

V tejto úlohe sa dozviete ako prebieha dvorenie u robotov.

Každý robot má vo svojej pamäti uložené posledné udalosti, ktoré sa v jeho/jej okolí odohrali. Každá udalosť má nejakú tému. Pre jednoduchosť si budeme pamäť každého robota predstavovať ako reťazec malých písmen anglickej abecedy. Každé písmeno označuje nejakú tému. Napr. “abca” je pamäť obsahujúca 4 rôzne udalosti, pričom prvá a posledná udalosť majú tú istú tému.

Proces dvorenia je vo svojej podstate veľmi jednoduchý. Každý robot si vyberie nejaký neprázdny súvislý úsek svojej pamäte a prerozpráva ho druhému robotovi. Dvorenie prebehlo úspešne práve vtedy, ak v úsekoch, ktoré si prerozprávali, nájdu nejakú spoločnú tému. Napríklad ak jeden robot povie “bca” a druhý “efccg”, tak dvorenie bolo úspešné, lebo obaja spomenuli tému c.

Android Helboj má veľký úspech u fembotiek. Fembotky za ním samé chodia a ako prvé mu hovoria svoje zážitky. No a Helboj to už má potom ľahké – stačí, aby si vybral nejaký úsek svojich spomienok, ktorý má s tými od fembotky nejakú spoločnú tému, a má vyhraté.

Úloha

Na vstupe dostanete dva reťazce. Prvý predstavuje postupnosť \(f\) spomienok, ktorú nejaká fembotka povedala Helbojovi. Druhý predstavuje postupnosť \(h\) spomienok, ktorá tvorí celú Helbojovu pamäť.

Helboj má presne \(h(h+1)/2\) možností, ktorý úsek spomienok prerozprávať fembotke. (Dve možnosti považujeme za rôzne, ak sa líšia indexom začiatku alebo konca, a to aj vtedy, ak im zodpovedajú rovnaké postupnosti znakov – ide síce o rovnakú tému, ale rôzne výskyty toho istého znaku predstavujú rôzne udalosti.) Váš program by mal vypočítať, koľko spomedzi týchto možností povedie k úspešnému dvoreniu.

Vstup

Prvý riadok vstupu obsahuje prirodzené čísla \(f\) a \(h\) (\(1 \leq f, h \leq 100\,000\)).

Druhý riadok obsahuje \(f\) malých písmen anglickej abecedy – úsek pamäte prerozprávaný fembotkou.

Tretí riadok obsahuje \(h\) malých písmen anglickej abecedy – celú pamäť Helboja.

Výstup

Vypíšte jeden riadok a v ňom jedno číslo – počet takých podreťazcov Helbojovej pamäte, že zdieľajú niektorú tému s fembotkiným reťazcom pamäte.

Príklady

Input:

2 2
aa
ba

Output:

2

Helboj môže povedať jeden z reťazcov “b”, “a” a “ba”. Ak by ale povedal len “b”, nenašli by s fembotkou spoločnú tému. Musí si teda vybrať jednu zo zvyšných dvoch možností.

Input:

3 6
bdb
acaabd

Output:

11

V tomto prípade vyhovujú všetky podreťazce Helbojovej pamäte, ktoré končia piatym alebo šiestym znakom.

Input:

1 10
a
aaaaaaaaaa

Output:

55

Tu si všimnite, že odpoveď je 55 a nie 10.