Se consideră trei numere naturale nenule n, k şi w.
Cerinţă
Să se scrie un program care determină numărul m al mulţimilor de forma {x1, x2, … ,xk} având ca elemente numere naturale nenule, ce satisfac simultan condiţiile:
• 1 ≤ x1 < x2 < ... < xk ≤ n
• xi+1 - xi ≥ 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
• 1 ≤ n, k, w ≤ 1 000 000
Exemple
nmult.in
nmult.out
Explicaţii
5 2 2
6
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}
10 3 4
4
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};
10 4 4
0
n=10, k=4, w=4
Nu există nicio mulţime de 4 elemente în care condiţiile să fie îndeplinite.