Šeštadieninė informatikos olimpiadininkų mokykla

Simbolių eilutes sudaro simboliai iš dviejų nesikertančių aibių ir . Dvi simbolių eilutės laikomos lygiomis, jeigu egzistuoja bijekcija iš į , kurią pritaikius pirmosios simbolių eilutės simboliams gauname antrąją simbolių eilutę.

Naudodami pastarąjį simbolių eilučių lygybės apibrėžimą sakykime, jog duotam šablonui simbolių eilutėje yra jo atitikmuo, jei egzistuoja poeilutė lygi .

Duota simbolių eilutė ir šablonas . Raskite, kiek simbolių eilutėje yra atitikmenų.

Pradiniai duomenys

Pirmoje eilutėje yra skaičiai ir – aibių ir dydžiai (). Antroje eilutėje yra simbolių, o trečioje – simbolių, kurie atitinka aibių ir elementus. Ketvirtoje eilutėje yra , penktoje – .

Aibes ir gali sudaryti mažosios ir didžiosios lotynų abėcėlės raidės. ir ilgiai neviršija .

Rezultatai

Išveskite vieną sveikąjį skaičių – kiek yra atitikmenų simbolių eilutėje .

Pavyzdys

2 3
Ls
abv
Labas
va

2