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ța

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 1.000.000.009.

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 1.000.000.009 al numărului de cuvinte comune distincte.

Restricții și precizări

• 1 ≤ K ≤ N ≤ 22
• 1 ≤ M ≤ 22
• Cele N display-uri pot afișa doar litere mici ale aflabetului englez.
• Pentru 11 puncte, K = N
• Pentru 13 puncte, 1 ≤ N, M ≤ 15 și toate cele N display-uri pot afișa doar caractere din mulțimea {a, b}.
• Pentru 14 puncte, 1 ≤ M ≤ 4
• Pentru 25 puncte, 1 ≤ N ≤ 10
• Pentru 22 puncte, 1 ≤ M ≤ 10, 1 ≤ N ≤ 20
• Pentru 15 puncte, Fără restricții suplimentare.

Exemplu:

comun.in

4 3 2
ab bc ad
ba bc dz
bx yzc da
ax cd zwyhd

comun.out

7

Explicație

Sunt 4 display-uri care pot afișa cuvinte de lungime 3. Cuvintele care pot fi afișate pe cel puțin două display-uri sunt: bca, abd, bbd, acd, bcd, xcd și acz.