Možno si viete predstaviť, aké množstvo zbytočných vecí sa nazbiera za roky v T2. Miška sa rozhodla to zmeniť a vyhodiť všetky zbytočné veci. Zobrala jednu zbytočnú vec zo všetkých miest, kde sa skrývala, a vyniesla ju do koša. Kým sa však stihla vrátiť, všetky uvoľnené miesta už boli zapratané ďalšou kopou vecí. To ju neskutočne naštvalo, a tak zase zobrala nejakú vec a vyniesla ju preč. Keď sa však vrátila, našla ešte väčší neporiadok… To sa už všetci vo všetkom začali strácať. Dá sa vôbec ešte zistiť, koľko máme čoho?

Úloha

Majme reťazec zložený z malých písmen anglickej abecedy. Postupne prebehne $m$ zmien, pričom pri každej nahradíme všetky výskyty jedného konkrétneho písmena novým reťazcom písmen. Zistite počet výskytov hľadaného písmena po všetkých zmenách.

Formát vstupu

V prvom riadku vstupu sú medzerou oddelené dve čísla $n$ a $m$, kde $n$ udáva počet znakov vo vstupnom reťazci a $m$ udáva počet zmien.

V druhom riadku sa nachádza reťazec, ktorý popisuje uloženie vecí na začiatku. Nasleduje $m$ riadkov, v ktorých sa nachádza medzerou oddelené písmeno a reťazec, ktorým máme písmeno nahradiť. Všetky reťazce sa skladajú výhradne z malých písmen anglickej abecedy.

Na poslednom riadku sa nachádza písmeno, na ktoré sa pýtame.

V jednotlivých sadách platia nasledujúce obmedzenia:

Maximálna dĺžka nahrádzajúceho reťazca je v prvých troch sadách $50$ a v poslednej $1\,000$.

Formát výstupu

Vypíšte jedno číslo - počet výskytov písmena, na ktoré sa pýtame v poslednom riadku vstupu. Keďže toto číslo môže byť veľmi veľké, vypíšte ho ako zvyšok po delení $10^9+7$.

Príklad

5 5
abcde
a aha
b tu
u je
e volne
v miesto
t

3

Postupne nám vychádzajú reťazce: abcde –> ahabcde –> ahatucde –> ahatjecde –> ahatjvolnecdvolne –> ahatjmiestoolnecdmiestoolne. Vidíme, že na konci sa v reťazci nachádzajú tri písmená t.