Polyglot

Viitorel, pregătindu-se intens pentru concursuri internaționale, vrea să învețe cât mai multe limbi (momentan se concentrează numai pe una). Pentru aceasta, mai întâi trebuie să cunoască sunetele limbii și modul de formare a cuvintelor. El deschide manualul și observă că la început sunt prezentate două șiruri de caractere: $w$ reprezentând șirul vocalelor și $k$ reprezentând șirul consoanelor.

Mai mult, această limbă are reguli stricte în legătură cu forma pe care o poate avea o silabă. Modelul unei silabe reprezintă un șir format din caracterele C (consoană obligatorie), c (consoană opțională) și V (vocală). Există exact o vocală în fiecare silabă.

De exemplu, o silabă poate avea modelul cCVc, adică o vocală precedată de una sau două consoane și urmată de o consoană sau niciuna. Considerând șirurile $w$ și $k$ cele corespunzătoare din limba română, cuvântul revista poate fi despărțit în silabe după acel model (re-vis-ta), în timp ce cuvântul ziar nu, deoarece vocala a nu este precedată de consoană.

Cerințe

Viitorel a încercat să spună o propoziție în limba pe care o învață, dar s-a blocat și îți cere să-l ajuți.

1. Determină câte despărțiri în silabe valide are fiecare cuvânt din propoziție.
2. Pentru a-și ușura munca, Viitorel ia fiecare cuvânt și îi rearanjează literele (în toate modurile posibile). Calculează, pentru fiecare cuvânt din propoziție, câte astfel de rearanjări sunt cuvinte valide (inclusiv cuvântul inițial).

Date de intrare

Fișierul polyglot.in va conține:

• Pe primele două linii, șirurile $w$ și $k$.
• Pe a treia linie, modelul unei silabe.
• Pe a patra linie, numerele naturale $C$ și $N$ separate printr-un spațiu, reprezentând cerința care trebuie rezolvată, respectiv numărul de cuvinte din propoziție.
• Pe a cincea linie, $N$ cuvinte separate printr-un spațiu.

Date de ieșire

Fișierul polyglot.out va conține pe prima linie $N$ numere naturale, reprezentând răspunsurile la cerința $C$, modulo $10^9 + 7$!

Restricții și precizări

• Sunetele limbii sunt doar vocale și consoane, nu și semivocale.
• Fiecare sunet reprezintă o unică literă și invers (există o bijecție între sunete și litere).
• Șirurile $w$ și $k$ sunt formate din litere mici ale alfabetului englez.
• $w \cap k = \varnothing$
• $c \subset (w \cup k)$, pentru oricare cuvânt $c$ din propoziție.
• Se garantează că modelul unei silabe are exact o vocală.
• O silabă are între $1$ și $100$ sunete inclusiv.
• Un cuvânt are între $1$ și $2 \ 000$ litere inclusiv.
• $1 \leq N \leq 50 \ 000$.

Exemplul 1

polyglot.in

aeiou
bcdfghjklmnpqrstvwxyz
cCVc
1 3
revista este scumpa

polyglot.out

2 0 2

Explicație

Se rezolvă cerința 1. Primul cuvânt are două despărțiri valide în silabe (re-vis-ta, re-vi-sta), al doilea nu are niciuna (primul e nu este precedat de consoană), ultimul are două (scum-pa, scu-mpa).

Exemplul 2

polyglot.in

aeiou
bcdfghjklmnpqrstvwxyz
cCVc
2 2
cumpar masa

polyglot.out

192 2

Explicație

Se rezolvă cerința 2. Al doilea cuvânt poate fi aranjat masa sau sama.