题目描述

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

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

输入格式

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

输出格式

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

8 3 4

213

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