| Fişierul intrare/ieşire: | sandokan.in, sandokan.out | Sursă | preONI 2008, Runda finala |
| Autor | Adrian Airinei | Adăugată de |  Airinei Adrian •astronomy |
| Timp execuţie pe test | 0.05 sec | Limită de memorie | 5120 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Sandokan
Sandokan a ales un numar natural K si a gasit pe canapea un sir cu N numere naturale distincte. El se joaca cu acest sir de numere si aplica succesiv asupra sirului urmatoarea operatie: alege K elemente distincte din sir si le elimina pe toate mai putin elementul care are valoarea maxima (dintre cele alese). Daca la un moment dat sirul are strict mai putin decat K elemente se opreste si scrie acest sir pe o foaie magica, altfel aplica in continuare operatii pe sirul rezultat. Ne este greu sa aflam ce sir a scris Sandokan, de aceea vrem doar sa aflam numarul total de posibiltati distincte de a scrie un sir pe foaia magica. Fiindca pot fi destul de multe posibilitati, vrem sa stim doar restul impartirii acestui numar la 2 000 003.
Date de intrare
Fisierul de intrare sandokan.in contine pe prima linie numerele N si K, avand semnificatia din enunt. Pe linia urmatoare urmeaza cele N numere naturale distincte.
Date de iesire
Pe prima linie a fisierului de iesire sandokan.out se afla numarul total de posibilitati distincte de a scrie un sir pe foaia magica modulo 2 000 003.
Restrictii
- 2 ≤ K ≤ N ≤ 5 000
- Cele N numere initiale sunt naturale si nu depasesc 2 miliarde
- Doua posibilitati de a scrie un sir sunt distincte daca exista macar un numar care apare intr-un sir si nu apare in celalalt
Exemplu
| sandokan.in | sandokan.out |
|---|---|
| 3 3 1 2 3 | 1 |
