Considerăm trei numere naturale nenule: n, k şi x. Denumim o kx-descompunere a numărului n o posibilitate de a scrie numărul n ca sumă de k numere naturale nenule astfel încât diferenţa între oricare doi termeni ai sumei este cel puţin egală cu x.

Cerinţă

Fiind date trei numere naturale n, k şi x, să se determine câte kx-descompuneri distincte există. Două kx-descompuneri sunt distincte dacă diferă prin cel puţin un termen.

Date de intrare

Fişierul desc.in conţine pe prima linie trei valori naturale nenule reprezentând numerele n, k şi x.

Date de ieşire

Fişierul desc.out va conţine o singură valoare reprezentând restul împărţirii numărului de kx-descompuneri distincte la numărul 10007.

Restricţii şi precizări

• Pentru 20% din teste 0 < n ≤ 200; pentru celelalte 80% din teste, 200 < n ≤ 10000;
• 1 ≤ x, k ≤ n

Exemplu

desc.in

20 2 3

desc.out

8

Explicaţii

Numărul de kx-descompuneri în acest caz este 8. Acestea sunt formate din numerele 1 şi 19; 2 şi 18; 3 şi 17; 4 şi 16; 5 şi 15; 6 şi 14; 7 şi 13; 8 şi 12

desc.in

2000 19 7

desc.out

3184