Fișierul intrare/ieșire	carti.in, carti.out	Sursă	Baraj Shumen 2012, Seniori
Autor	Victor Manz	Adăugată de	Victor Manz • vmanz
Timp de execuție pe test	0.2 sec	Limită de memorie	750 KB
Scorul tău	N/A	Dificultate	2.75

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

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

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