P5224 Candies
题目背景
JerryC 有一大袋糖果，他正以 $1\ \textrm{t/ms}$ 的速度食用着这一袋糖果......
题目描述
JerryC 的糖果有 $N$ 箱（两两之间不同）。他一开始想挑 $M$ 箱出来，但是觉得吃起来不过瘾，所以又想要多拿一些出来。由于他比较喜欢数字 $K$，所以只要拿出来的糖的量 $x$（$x \ge M$）满足：$x \equiv M\pmod{K}$，JerryC 就会得到满足感。
求有多少种方案使得 JerryC 得到满足感。请输出方案数 $\bmod\ 1004535809$ 的结果。
输入格式
一行三个非负整数 $N,M,K$。
输出格式
一行一个非负整数，表示方案数 $\bmod\ 1004535809$ 的结果。
说明/提示
样例解释：
可以拿出来：$2$ 箱 $5$ 箱 $8$ 箱，组合数算一下就是了：
$$\binom{10}{2}+\binom{10}{5}+\binom{10}{8}=342$$
数据范围：
|测试点编号|$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$。