[AdditionalFile6696.zip](file://AdditionalFile6696.zip?type=additional_file)

#6696. 复读机 加强版

标签: 传统 | 时间限制: 1000 ms | 内存限制: 256 MiB |

题目描述

见 UOJ #450. 【集训队作业2018】复读机

小飞机（FFjet）觉得这题的 $d$ 太小了，于是想考考你，能不能做更难的情况？

输入格式

一行三个正整数 $n, k, d$，意义如题目描述所述。

输出格式

一行一个正整数，表示方案数对 $19491001$ 取模的值。

样例 1

输入

8 3 4

输出

213

样例 2

输入

12 4 6

输出

5548

数据范围与提示

对于 $50\%$ 的数据，$d = 4, k\le 2\times 10^3$。

对于另外 $50\%$ 的数据，$d = 6, k\le 10^3$。

对于 $100\%$ 的数据，保证 $n\le 10^9$。