== 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 29989**.

h2. Restricţii

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

* $1 ≤ N ≤ 2 000$
* $1 ≤ K ≤ L ≤ N$

h2. Exemplu