无尽的黄金 (gold.cpp/in/out)

时间限制：3s / 空间限制：512MB / 打开-O2优化

题目描述

探险家Lunk发现了一个藏在大山深处的洞穴。经过五天五夜的探索，Lunk在洞中发现了一个非常神奇的地方。这里有一个不断生成黄金的小口，每分钟可以取出一个黄金，不然这个黄金就会马上消失。取出的黄金自然会变成Lunk的了。贪婪的资本家绝对不会错过这个发财的大好时机，Lunk想要取走大量的黄金。

然而在这旁边却立着一个牌子，上面写着：

Hello, Lunk,

恭喜你，你非常机智地发现了这个奇妙的地方，我早已知道你到底想干什么。不如我们来玩个游戏，你可随意取走黄金，但是任意连续的 $K$ 分钟内，你不可以取走过多的黄金，否则，你将找不到出去的路。

Best wishes

——XL

这让Lunk感到十分害怕，它担心自己一不留神就会触犯的这个可怕的规则。但是贪婪的资本家是不会放弃的，Lunk想知道究竟有多少种取走黄金的方法（可以全都不取），使得自己不会葬身于山洞之中。

Lunk现在还有一些时间，希望你能够快速给出答案。

输入格式

每个数据仅一行，包含三个整数 $T$ ， $K$ 和 $C$ 。

$T$ 表示Lunk还剩下的时间，单位为分钟。

$K$ 和 $C$ 表示Lunk在任意连续的 $K$ 分钟内可以取走少于 $C$ 个黄金。

输出格式

输出一行一个整数，表示Lunk取走黄金的方案数。由于答案可能非常大，所以请将答案对 $1073741824$ 取模。

样例输入

2 2 2

样例输出

样例解释

只要Lunk不把所有黄金取走就好了，共有三种取法。

数据限制

本题采用捆绑测试，共 $6$ 个子任务。

每个子任务和数据点约定如下：

子任务 (分值)	$T$ 的限制	$K$ 的限制	$C$ 的限制
$1$ ( $10\%$ )	$\le 10^3$	$= 2$	$= 2$
$2$ ( $10\%$ )	$\le 10^3$	$= 3$	$= 2$
$3$ ( $10\%$ )	$\le 10^3$	$\le 9$	$\le K$
$4$ ( $20\%$ )	$\le 10^5$	$\le 9$	$\le K$
$5$ ( $20\%$ )	$\le 2 \times 10^7$	$\le 6$	$\le K$
$6$ ( $30\%$ )	$\le 2 \times 10^7$	$\le 9$	$\le K$

对于 $100\%$ 的数据，均保证 $1 \le T \le 2 \times 10^7$ ， $1 \le K \le 9$ ， $0 \le C \le K$ 。

时间限制： $2\text{s}$

空间限制： $512\text{MB}$