3084. [HSOI 2019&HEOI 2017] 组合数问题（加强版）

【题目描述】

$hs$ 的糖果有 $N$ 箱(两两之间不同)。他一开始想挑 $M$ 箱出来，但是觉得吃起来不过瘾，所以又想要多拿一些出来。由于他比较喜欢数字 $K$，所以只要拿出来的糖的量 $x(x ≥ M)$ 满足：$x≡M (mod$ $K)$，$hs$就会得到满足感。

求有多少种方案使得 $hs$ 得到满足感。请输出方案数 $\bmod$ $1004535809$ 的结果。

【输入格式】

一行三个非负整数 $N,M,K$。

【输出格式】

一行一个非负整数，表示方案数 $mod$ $1004535809$ 的结果。

【样例输入】

10 2 3

【样例输出】

342

【提示】

$10\%$ $k=1$;

$20\%$ $n \leq 10^6,k \leq 10$;

$40\%$ $n \leq 10^{12},k \leq 100$;

$60\%$ $n \leq 10^{12},k \leq 1000$;

$100\%$ $n \leq 10^{18},k \leq 10000，m < k$;