perm4

Permutari 4

== include(page="template/taskheader" task_id="perm4") ==

Poveste si cerinta...

Pe langa pasiunea sa pentru numere, Zaharel este un mare pasionat de permutari. Astazi, si-a propus sa studieze numai permutarile $P$ de lungime $N$ care au o proprietate interesanta: contin $K$ pozitii distincte $1<i{~1~},i{~2~},...,i{~K~} &le; N$ pentru care $P[i{~x~}]=P[i{~x~}-1]+1$.
Scrieti un program care determina cate permutari va studia Zaharel astazi.

h2. Date de intrare

...

Pe prima linie a fisierului de intrare $perm4.in$ sunt scrise cele doua numere naturale $N$ si $K$, separate printr-un singur spatiu.

h2. Date de iesire

...

Prima linie a fisierului $perm4.out$ va contine numarul de permutari. Deoarece rezultatul poate fi foarte mare, se va afisa in schimb restul impartirii rezultatului la numarul $666013$.

h2. Restrictii

... ≤ ...

* $0 &le; K < N &le; 3.000$

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

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

| 4 1
| 9

|
h3. Explicatie

...

Cele 9 permutari sunt:
$1243$
$1342$
$1423$
$2134$
$2314$
$3421$
$3124$
$4231$
$4312$

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

1441