Fișierul intrare/ieșire	comun.in, comun.out	Sursă	ONI 2023, Clasa a 10-a
Autor	OSEPI	Adăugată de	Teodor Plop • teodor94
Timp de execuție pe test	3 sec	Limită de memorie	524288 KB
Scorul tău	N/A	Dificultate	N/A

Vezi soluțiile trimise | Statistici

Comun (Clasa a 10-a)

Kida și El Bandito Inofensivo au N display-uri digitale care pot afișa litere mici din alfabetul englez. Fiecare dintre cele N display-uri are câte M celule. Pentru fiecare display i, cunoaștem literele care pot fi afișate în fiecare celulă j a sa.

Spre exemplu, dacă M = 3 și un display poate afișa pe prima poziție literele {b, x}, pe a doua poziție literele {y, z, c} și pe a treia poziție literele {d, a}, putem forma, de exemplu, cuvintele byd, bya, bza, etc.

El Bandito Inofensivo consideră că un cuvânt de lungime M este comun dacă acesta se poate forma pe cel puțin K dintre cele N display-uri. Auzind asta, Kida vă roagă să o ajutați să calculeze numărul de cuvinte comune distincte.

Cerință

Ajutați-o pe Kida să calculeze numărul de cuvinte comune distincte. De vreme ce acest număr poate să fie foarte mare, se cere restul său la împărțirea prin 10⁹ + 9.

Date de intrare

Pe prima linie din fișierul de intrare comun.in se află trei numere: N, M și K, cu semnificația din enunț. Pe următoarele N linii se află câte M șiruri de caractere, formate din litere mici distincte ale alfabetului englez, separate prin câte un spațiu. Al j-lea șir de caractere de pe linia i + 1 din fișierul de intrare reprezintă caracterele pe care le poate afișa al i-lea display pe poziția j.

Date de ieșire

Fișierul de ieșire comun.out va conține restul la împărțirea cu 10⁹ + 9 al numărului de cuvinte comune distincte.

Restricții

• 1 ≤ K ≤ N ≤ 22
• 1 ≤ M ≤ 22
• Cele N display-uri pot afișa doar litere mici ale aflabetului englez.

Punctaj

Mențiune

Rezultatele evaluării pot fi diferite față de cele din concurs.

Limitele acestei probleme nu sunt încă definitivate.

Exemplu