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 aplica urmatoarea operatie asupra sirului:
 
* Daca sirului are $1$ element sau cel mult $K-1$ elemente il scrie pe o foaie magica, altfel alege $K$ elemente din sir si le elimina pe toate mai putin elementul care are valoarea maxima dintre cele alese. Continua apoi sa aplice aceasta operatie pe sirul ramas.

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

Fisierul de intrare $sandokan.in$ ...

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.

h2. Date de iesire

In fisierul de iesire $sandokan.out$ ...

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

* $... ≤ ... ≤ ...$

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