== 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 pe foaia magica, de aceea vrem doar sa aflam numarul total de posibiltati distincte de a scrie un sir pe aceasta foaie. 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 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