#6696. 复读机 加强版

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: EntropyIncreaser

题目描述

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

小飞机(FFjet)觉得这题的 d 太小了,于是想考考你,能不能做更难的情况?

输入格式

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

输出格式

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

样例

样例输入 1

8 3 4

样例输出 1

213

样例输入 2

12 4 6

样例输出 2

5548

数据范围与提示

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

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

对于 100\% 的数据,保证 n\le 10^9