Background

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

Problem Description

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$.

Input Format

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

Output Format

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

10 2 3

342

Hint

Sample explanation:

He can take out $2$ boxes, $5$ boxes, or $8$ boxes. Just compute the combinations:

Constraints:

$0 \leq M < K$。

Translated by ChatGPT 5