Fişierul intrare/ieşire:carti.in, carti.outSursăBaraj Shumen 2012, Seniori
AutorVictor ManzAdăugată devmanzVictor Manz vmanz
Timp execuţie pe test0.8 secLimită de memorie750 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

Carti

Coriolan Nepriceputeanu este un intelectual desăvârşit, care are o colecţie impresionantă formată din N cărţi. Fiecare dintre acestea are asociat un cod ISBN format din cel mult 9 cifre. Fiind foarte ataşat de cărţile sale lui Coriolan i-ar plăcea ca acestea să fie ordonate riguros, după anumite reguli, care unor neiniţiaţi le-ar putea părea uşor bizare. Astfel, pe primul raft, pe care încap exact M cărţi, el ar vrea să pună volume având suma codurilor ISBN divizibilă cu 100. Cum însă matematica nu e punctul lui forte, vă roagă pe voi să-l ajutaţi să calculeze numărul de variante de alegere a celor M cărţi conform criteriului impus de el. Fiind vorba de un număr foarte mare, Coriolan preferă să afle restul la împărţirea cu 9001 a acestuia.

Date de intrare

Fişierul de intrare carti.in conţine pe prima linie numerele N şi M, iar pe următoarele N linii codurile ISBN C1, C2, ..., CN ale acestora, câte unul pe fiecare rând.

Date de ieşire

În fişierul de ieşire carti.out se va afişa un singur număr, reprezentând restul la împărţirea cu 9001 a numărului de variante de alegere a cărţilor de pe primul sertar.

Restricţii

  • 1 ≤ M ≤ N ≤ 1000
  • 0 ≤ Ci ≤ 999999999 pentru 1 ≤ i ≤ N
  • Ordinea în care sunt plasate cărţile pe raft nu contează ; (1,2,4) şi (4,1,2) reprezintă o singură variantă de alegere şi deci nu vor fi numărate separat.

Exemplu

carti.incarti.out
5 2
53
200
47
400
300
4

Explicaţie

Cele 4 variante de alegere sunt următoarele:
- Se aleg cărţile cu codurile 53 şi 47
- Se aleg cărţile cu codurile 200 şi 400
- Se aleg cărţile cu codurile 200 şi 300
- Se aleg cărţile cu codurile 400 şi 300

Trebuie sa te autentifici pentru a trimite solutii. Click aici