lkperm

Lkperm

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

Poveste şi cerinţă...

Afrodita a decis ca singurele permutari frumoase sunt $LK$-permutarile. O $LK$-permutare este o permutare ce respecta urmatoarea conditie: pentru orice subsecventa de $L$ elemente consecutive, elementul maxim al acestei subsecvente se afla in primele $K$ elemente ale subsecventei. Mai exact pentru o permutare $P$ cu $N$ elemente, orice subsecventa $Pi, Pi+1, ..., Pi+L-1$ ( $i+L-1 ≤ N$ ) cu $Pk = max(Pi, Pi+1, ..., Pi+L-1)$ respecta $i ≤ k ≤ i + K - 1$. Cine o va ajuta pe Afrodita sa afle cate $LK$-permutari cu $N$ elemente exista, va fi rasplatit cu frumuseste fara margini.

h2. Date de intrare

Fişierul de intrare $lkperm.in$ ...

Fisierul de intrare $lkperm.in$ va contine pe prima linie trei numere naturale $N$, $L$ si $K$ separate prin cate un spatiu, avand semnificatia din enunt.

h2. Date de ieşire

În fişierul de ieşire $lkperm.out$ ...

In fisierul de iesire $lkperm.out$ veti afisa un singur numar reprezentand numarul de LK-permutari cu $N$ elemente **modulo 100 019**.

h2. Restricţii

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

* $1 ≤ N ≤ 100 000$
* $1 ≤ K ≤ L ≤ N$
* Pentru $40%$ din teste $N ≤ 1 000$
* Pentru $60%$ din teste $N ≤ 10 000$ si $K ≤ 1 000$

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

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

| 4 3 2
| 10

|
h3. Explicaţie

...

Toate $32$-permutarile cu $4$ elemente sunt: $1 4 2 3$, $1 4 3 2$, $2 4 1 3$, $2 4 3 1$, $3 4 1 2$, $3 4 2 1$, $4 1 3 2$, $4 2 3 1$, $4 3 1 2$, $4 3 2 1$.

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

4843