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 $10^9 + 7$.

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.

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.

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.

Restricții și precizări

• $1 \leq N \leq 20$
• $1 \leq L \leq 100$
• $1 \leq NR \leq 100$
• Pentru $10\%$ din teste, $N \leq 5$ şi $L \leq 5$
• Pentru încă $30\%$ din teste $N \leq 15$ şi $L \leq 50$
• Cardinalul unei extinderi va fi mai mic sau egal cu $1 \ 000$
• Cuvintele candidat din fişierul de intrare vor conţine doar caractere mici ale alfabetului latin şi ?

Exemplu

afacere.in

3 2 2
ab
a?
cb
0
2

afacere.out

27
29

Explicație

Pentru prima extindere nu avem niciun caracter adiţional, deci cuvintele complete compatibile posibile sunt aa, ab, ac, $\dots$, 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, $\dots$, az, aA, aB şi cb, unde prin A şi B am notat cele două caractere adiţionale.