5. Éra krátkych skratiek

Janko sa začal učiť pracovať s Unixovým terminálom. Ako prvý sa naučil príkaz echo s veľmi príznačným menom, ktorý ako ozvena vypíše svoje parametre na štandardný výstup.

Potom však došiel k príkazom, ktoré začali mať príliš krátke a nezrozumiteľné mená. Začínalo to úplne nebadane, príkazmi cp, mv a rm na kopírovanie, presúvanie a mazanie súborov, ktorých mená vznikli jednoducho z CoPy, MoVe a ReMove. Neskôr sa to začalo zhoršovať. Janko sa dozvedel napríklad o príkazoch chmod (change mode), tar (tape archiver), tr (transform) či chgrp (change group). Janko si príkazy nedokázal zapamätať a v skriptoch, ktoré napísal, sa už chvíľu nato nedokázal vyznať. Ale malo to aj svoje výhody: menej búchania do klávesnice, menej prenesených mobilných dát¹ , …, a tu to aj skončilo.

Kto si má všetky tie skratky pamätať, pomyslel si Janko a začal sa radšej učiť programovať v jazyku C. Vôbec si však nepomohol, práve naopak. Tu mená funkcií boli nielen prikrátke, ale priam až kryptické. Napríklad strrchr. Po dlhých minútach zamyslenia zistil, že to str znamená string, r znamená reverse a chr znamená character a funkcia teda hľadá výskyt znaku v reťazci odzadu.

Keďže ho však premýšľanie začalo bolieť, rozhodol sa už druhýkrát zmeniť predmet svojho záujmu. Vybral si jazyk SNOBOL. Ale toto už Jankovi nedalo. Prečo práve SNOBOL? Ako k tomu došli? Vraj StriNg Oriented symBOlic Language. To nijak nedáva zmysel.

Napokon došiel k tomu, že vo všeobecnosti skratka vzniká tak, že len jednoducho vyberieme niektoré znaky názvu, pričom zachováme ich poradie a zapíšeme ich za seba. Z každého slova musíme vybrať aspoň jedno písmeno. A žiadne ďalšie pravidlá zrejme neplatia.

Janko by chcel vedieť overovať, či je daná skratka platná. Ale rozmýšľanie ho už po lúštení strrchr a SNOBOLu veľmi bolí, rád by to teda nechal na vás.

Úloha

Vašou úlohou je spočítať počet možností, ako mohla vzniknúť skratka \(S\) z názvu \(T\).

Aby skratka \(S\) mohla vzniknúť z textu \(T\), musí platiť, že písmenám v \(S\) vieme priradiť písmená v \(T\), pričom musíme zachovať poradie (teda ak priradíme písmenko z \(S\) nejakému písmenku z \(T\), ďalšiemu môžeme priradiť len nejaké napravo v \(T\)) a z každého slova \(T\) musíme použiť aspoň jedno písmeno.

Keďže počet možností je v niektorých prípadoch naozaj veľký, vypíšte len jeho zvyšok po delení \(10^9+7\).

Formát vstupu

Na prvom riadku sa nachádza číslo \(w\) – počet slov textu, z ktorého má byť utvorená skratka.

Na druhom riadku sa nachádza skratka - reťazec \(S\) a na treťom riadku sa nachádza text \(T\), ktorého skratka to má byť. Oba reťazce na vstupe pozostávajú len z malých písmen anglickej abecedy a medzier. Jednotlivé slová \(T\) sú oddelené práve jednou medzerou (medzier je teda \(w-1\)). Skratka žiadne medzery neobsahuje.

Formát výstupu

Vypíšte jedno číslo – počet možností, ako možno priradiť písmenám skratky \(S\) písmená textu \(T\) tak, aby tvorili platnú skratku, modulo \(10^9+7\). Ak to nie je možné, vypíšte \(0\).

Hodnotenie

Nech \(M\) je dĺžka skratky a \(N\) dĺžka textu. Sú \(4\) sady vstupov. V jednotlivých sadách platia nasledovné obmedzenia:

1. \(M \leq 5\), \(N \leq 12\)
2. \(M \leq 12\), \(N \leq 50\)
3. \(M \leq 120\), \(N \leq 200\)
4. \(M \leq 200\), \(N \leq 10000\)

Príklady

Input:

2
tar
tape archiver

Output:

4

Možnosti sú TApe aRchiver, TApe archiveR, Tape ARchiver a Tape ArchiveR.

Input:

4
snobol
string oriented symbolic language

Output:

1

Input:

3
strrchr
string reverse char

Output:

3

Input:

4
radar
radio detection and ranging

Output:

1

Jediná možnosť je RAdio Detection And Ranging. RADio detection And Ranging nie je platná možnosť, pretože zo slova detection sme nepoužili žiadne písmeno.

Input:

4
acm
academy of computer makers

Output:

0

Skratka je jednak prikrátka, a jednak neobsahuje žiadne z písmen slova of.