P5224 Candies

JerryC has a big bag of candies, and he is eating this bag at a speed of $1\ \textrm{t/ms}$.

JerryC has $N$ boxes of candies (all different from each other). At first, he wanted to pick $M$ boxes, but he felt it was not enough, so he wants to take some more. Since he likes the number $K$, as long as the number of boxes he takes out $x$ ($x \ge M$) satisfies $x \equiv M\pmod{K}$, JerryC will feel satisfied. Find how many ways can make JerryC feel satisfied. Output the number of ways $\bmod\ 1004535809$.

One line with three non-negative integers $N, M, K$.

One line with one non-negative integer, the number of ways $\bmod\ 1004535809$.

Sample explanation: He can take out $2$ boxes, $5$ boxes, or $8$ boxes. Just compute the combinations: $$\binom{10}{2}+\binom{10}{5}+\binom{10}{8}=342$$ Constraints: |Test Point ID|$N\le$|$K\le$| |:-------:|:-------:|:-------:| |$1$|$1$|$1$| |$2-3$|$10^6$|$10$| |$4-8$|$10^{12}$|$100$| |$9-12$|$10^{15}$|$10^3$| |$12-20$|$10^{18}$|$10^4$| $0 \leq M < K$。 Translated by ChatGPT 5