prop

Asa cum stiti deja, lui B.A. ii plac multe lucruri. Ultimul lucru interesant pe care l-a gasit sunt numerele de fix N cifre scrise in baza K. Doar ca pentru B.A. notiunea de numar este mai speciala: spre exemplu, pentru numerele de 3 cifre in baza 10, 13 este scris ca 013. Asadar, numerele pot incepe si cu 0. Pe de alta parte, B.A. nu considera ca toate numerele sunt interesante, ci doar cele care respecta anumite proprietati. Aceste proprietati se refera la frecventa de aparitie in numarul respectiv a cifrelor din baza K. Evident, numerele care sa respecte toate conditiile date de B.A. sunt foarte greu de gasit asa ca el doreste sa fie respectate cel putin M proprietati referitoare la cele K cifre posibile ale unui numar. Sa luam, de exemplu, numerele de 3 cifre in baza 5, cu urmatoarele proprietati:

Cifra 0 1 2 3 4
Frecventa de aparitie 5 1 2 0 6

Numarul 124 indeplineste doua proprietati: exista un singur 1 si nici un 3.
Numarul 223 indeplineste o proprietate: apare de doua ori cifra 2.
Pentru M=3, singurele numere care sa indeplineasca 3 conditii sunt 122, 212, 221.
Pentru M=2, numerele care indeplinesc cel putin 2 conditii dintre cele 5 sunt:
122, 212, 221 (care indeplinesc 3 proprietati, deci implicit indeplinesc si doua)
100, 102, 104, 120, 122, 124, 140, 142, 144
010, 012, 014, 210, 212, 214, 410, 412, 414
001, 021, 041, 201, 221, 241, 401, 421, 441
220, 221, 224
202, 212, 242
022, 122, 422

Avem in total 39 de numere care respecta cel putin doua dintre cele cinci proprietati. Dar am numarat pe 122, 212, 211 de trei ori, asa ca trebuie sa le scadem din total. Astfel, exista 33 de numere care sa respecte cel putin doua conditii.

Cerinta
Din totalul de KN numere de N cifre scrise in baza K, aflati cate au cel putin M proprietati dintre cele date, modulo 9901.

Date de intrare

Fisierul prop.in va contine pe prima linie valorile N, K si M separate prin exact un spatiu. Pe urmatoarele K linii se vor afla proprietatile care trebuie respectate de fiecare cifra. Pe linia i se va afla un numar, care reprezinta frecventa exacta de aparitie a cifrei (i-1) in cadrul numarului cautat.

Date de iesire

Fisierul prop.out va contine un singur numar, modulo 9901, care va reprezenta numarul de numere de N cifre scrise in baza K care respecta cel putin M dintre proprietatile date de B.A.

Restrictii Exemplu

prop.in

prop.out

 Explicatii

3 5 2
5
1
2
0
6

33

Se cauta numerele de 3 cifre in baza 5 care au cel putin doua din urmatoarele proprietati: cifra 0 apare de 5 ori; cifra 1 apare o data; cifra 2 apare de doua ori; cifra 3 nu apare niciodata; cifra 4 apare de 6 ori;
Numerele acestea sunt: 122, 212, 221 (care respecta trei proprietati); orice numar de forma 1yy, y1y,yy1 (y<>1; y<>3); orice numar de forma 22z; 2z2;z22(z<>2; z<>3)

Timp maxim de executie/test: 1 secunda.