siruri

Sa se numere cate siruri crescatoare de lungime N se pot forma cu numere naturale din intervalul [1,M] astfel incat fiecare sir sa contina maxim K numere distincte.

Date de intrare

Pe prima linie a fisierului de intrare siruri.in sunt scrise cele trei numere naturale N , M , K , separate prin spatii.

Date de iesire

Prima linie a fisierului siruri.out va contine un singur numar natural reprezentand numarul de siruri care indeplinesc conditiile din enunt.

Restrictii

1 <= N <= 8 000
1 <= M <= 100 000
1 <= K <= 2 000
Rezultatul va avea cel mult 7000 cifre.

Exemplu

siruri.in

siruri.out

Explicatie

4 3 2

12

Cele 12 siruri sunt:
1 1 1 1
1 1 1 2
1 1 1 3
1 1 2 2
1 1 3 3
1 2 2 2
1 3 3 3
2 2 2 2
2 2 2 3
2 2 3 3
2 3 3 3
3 3 3 3

Timp maxim de executie/test: 0.5 secunde
Memorie disponibila: 2 MB, din care 1 MB pentru stiva.

Adrian Diaconu
Universitatea Bucuresti, Facultatea de Matematica si Informatica
ditzone@gmail.com