无尽的黄金 (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}$