== include(page="template/taskheader" task_id="afacere") ==
Lunasorab s-a decis să îşi deschidă o afacere. Astfel, el s-a apucat de spart coduri (contra cost, bineînţeles). El primeşte o listă de $N$ cuvinte candidat, de aceeaşi lungime $L$ şi trebuie să afle câte cuvinte complete distincte compatibile cu cel puţin unul dintre ele există. Un cuvânt se numeşte candidat dacă conţine numai litere mici din alfabetul latin şi caracterul $?$ (care poate fi înlocuit cu orice literă mică a alfabetului latin). Spunem că un cuvânt este complet dacă este format doar din litere mici ale alfabetului latin, şi spunem că un cuvânt complet este compatibil cu un cuvânt candidat dacă există o asignare a caracterelor $?$ astfel încât cele două cuvinte să devină identice.
Totuşi, deoarece este vorba de mulţi bani şi crede că poate fi singura lui şansă de „a face succes”, el vă testează dându-vă $NR$ extinderi ale alfabetului. O extindere a alfabetului constă din reuniunea literelor mici ale alfabetului latin cu un set de caractere adiţionale distincte (doar cardinalul extinderilor este important). Aceste caractere din extindere pot reprezenta asignări posibile ale caracterelor $?$.
Deoarece răspunsul pe care Lunasorab îl caută poate fi destul de mare, el vă cere rezultatul modulo $1 000 000 007$.
h2. Cerinţă
Dată fiind o listă de cuvinte candidat şi $NR$ extinderi, să se determine câte cuvinte complete distincte compatibile cu cel puţin unul dintre cuvintele candidat există, pentru fiecare extindere.
Poveste şi cerinţă...
h2. Date de intrare
Fişierul de intrare $afacere.in$ conţine pe prima linie numerele naturale $N$ $L$ $NR$. Pe următoarele $N$ linii se vor afla cuvintele candidat. Pe următoarele $NR$ linii fiecare linie va conţine un număr natural $v$, reprezentând cardinalul unei extinderi.
Fişierul de intrare $afacere.in$ ...
h2. Date de ieşire
Fişierul de ieşire $afacere.out$ va conţine pentru fiecare dintre cele $NR$ extinderi câte o linie pe care se va scrie un număr natural reprezentând numărul de cuvinte complete distincte compatibile cu cel puţin unul dintre cuvintele candidat din listă, folosind alfabetul format din literele alfabetului latin împreună cu un număr adiţional de caractere egal cu cardinalul extinderii.
În fişierul de ieşire $afacere.out$ ...
h2. Restricţii
* $1 ≤ N ≤ 20$
* $1 ≤ L ≤ 100$
* $1 ≤ NR ≤ 100$
* Pentru $10%$ din teste, $N ≤ 5$ şi $L ≤ 5$.
* Pentru încă $30%$ din teste $N ≤ 15$ şi $L ≤ 50$.
* Cardinalul unei extinderi va fi mai mic sau egal cu $1000$.
* Cuvintele candidat din fişierul de intrare vor conţine doar caractere mici ale alfabetului latin şi $?$.
* $... ≤ ... ≤ ...$
h2. Exemplu
table(example). |_. afacere.in |_. afacere.out |
| 3 2 2
ab
a?
cb
0
2
| 27
29
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicaţie
Pentru prima extindere nu avem niciun caracter adiţional, deci cuvintele complete compatibile posibile sunt $aa$, $ab$, $ac$, …, $az$ şi $cb$. Pentru al doilea exemplu, avem două caractere adiţionale în care poate fi transformat $?$, deci cuvintele complete compatibile posibile sunt $aa$, $ab$, $ac$, …, $az$, $aA$, $aB$ şi $cb$, unde prin $A$ şi $B$ am notat cele două caractere adiţionale.
...
== include(page="template/taskfooter" task_id="afacere") ==
