sandokan

Sandokan

== include(page="template/taskheader" task_id="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 un element sau 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 pe foaie magica, de aceea vrem doar sa aflam numarul total de posibiltati distincte de a scrie un sir pe foaia magica.

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

h2. Date de intrare

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

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

h2. Restrictii

* $1 ≤ K ≤ N ≤ 5000$

* $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

h2. Exemplu
table(example). |_. sandokan.in |_. sandokan.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 3 3
  1 2 3
| 1

|

h3. Explicatie
 
...
 

== include(page="template/taskfooter" task_id="sandokan") ==

2918