5. Už nemáme čo jesť

Je to tak, už ste všetko zjedli. Je načase ísť pracovať. Dnes sa na programovaní naučíte pracovať s Unixovým terminálom. Ako prvý sa naučíte 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 prídete k príkazom, ktoré začnú mať príliš krátke a nezrozumiteľné mená. Začne 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čne zhoršovať (aj si hovoríte že ste mali jest pomalšie ale už je neskoro). Potom prídete napríklad k príkazom chmod (change mode), tar (tape archiver), tr (transform) či chgrp (change group). Vy sa snažíte sústrediť ale jediné čo vám chodí po rozume je jedlo a to že kedy bude dalšie.

Nič si nezapamätáte, ale zato večeru už máte premyslenú. Idete radšej programovať v jazyku C. Vôbec si však nepomôžete, práve naopak. Tu sú mená funkcií nielen prikrátke, ale priam až kryptické. Napríklad strrchr. Po dlhých minútach zamyslenia (rozptyľuje vás predstava blížiacej sa večere) zistíte ž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 vás to premýšľanie začalo bolieť, rozhodli ste sa už druhýkrát zmeniť predmet svojho záujmu. Vybrali ste si jazyk SNOBOL. Ale toto vám už nedalo. Prečo práve SNOBOL? Ako k tomu došli? Vraj StriNg Oriented symBOlic Language. To nijak nedáva zmysel. Napokon ste došli 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 (kiežby ste aj k tej večery už konečne došli). Z každého slova musíte vybrať aspoň jedno písmeno. A žiadne ďalšie pravidlá zrejme neplatia. Vy by ste si chceli vedieť overovať, či je daná skratka platná ale chcete to automatizovať aby sa pri tom dalo jesť. Tak šup šup, už začína večera ale vy nemôžte ísť kým nevylúštite zvyšok.

Ú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.