Nmult

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 $\{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 $666 \ 013$.

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.