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

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.

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

Fisierul de intrare $sandokan.in$ ...

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 modulo $2 000 003$.

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

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 |

| 3 3
  1 2 3
| 1

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

|

h3. Explicatie
 
...
 

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

2918