Se consideră trei numere naturale nenule n, k și w.

Cerința

Să se scrie un program care determină numărul m al mulțimilor de forma {x[1], x[2], … ,x[k]} având ca elemente numere naturale nenule, ce satisfac simultan condițiile:

• 1 ≤ x[1] < x[2] < ... < x[k] ≤ n
• x[i+1] - x[i] ≥ w, 1 ≤ i ≤ k - 1

Date de intrare

Fișierul de intrare nmult.in conține pe prima linie trei numere naturale nenule n, k, w separate prin câte un spaţiu, cu semnificaţia de mai sus.

Date de ieșire

Fișierul de ieșire nmult.out va conține pe prima linie restul împărţirii numărului m la 666013.

Restricții și precizări

• 1 ≤ n, k, w ≤ 1.000.000;

Exemplul 1

nmult.in

5 2 2

nmult.out

6

Explicație

n=5, k=2, w=2

Există 6 mulțimi cu 2 elemente, astfel încât diferența între oricare 2 termeni consecutivi să fie cel puțin 2: {1,3}, {1,4}, {1,5}, {2,4}, {2,5}, {3,5}

Exemplul 2

nmult.in

10 3 4

nmult.out

4

Explicație

n=10, k=3, w=4

Există 4 mulțimi cu 3 elemente, astfel încât diferența între oricare 2 termeni consecutivi să fie cel puțin 4: {1,5,9}, {1,5,10}, {1,6,10}, {2,6,10}.

Exemplul 3

nmult.in

10 4 4

nmult.out

0

Explicație

n=10, k=4, w=4

Nu există nicio mulțime de 4 elemente în care condițiile să fie îndeplinite.