Fişierul intrare/ieşire:	siruri2.in, siruri2.out	Sursă	.campion 2007-2008, runda 5, grupa M
Autor	Adrian Diaconu	Adăugată de	Adrian Diaconu •DITzoneC
Timp execuţie pe test	0.1 sec	Limită de memorie	6144 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Siruri 2

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

Fisierul de intrare siruri2.in contine pe prima linie trei numere naturale N, M, K cu seminificatia din enunt.

Date de iesire

In fisierul de iesire siruri2.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

Explicatie

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

Cum se trimit solutii?