← 返回题目列表

AtCoder · icpc2014autumn_g

G. 饼干柜台

中文机器翻译题面 查看原题

问题陈述

有一天,我的奶奶留下了 $N$ 饼干。 我和姐姐本来打算马上吃,但是有指示。 它说

  • Cookie 会变质;您应该在 $D$ 天内吃完所有这些。
  • 小心暴饮暴食;你每天吃的饼干应该严格少于$X$。

姐姐说:“有多少种方法可以吃掉所有的饼干?我们来数一数吧!”

如果存在一天,两种方式吃的饼干数量不同,则认为两种方式不同。 例如,如果$N$、$D$和$X$分别为$5$、$2$和$5$,则路数为$4$:

  • 第一天吃 $1$ 饼干,第二天吃 $4$ 饼干。
  • 第一天吃 $2$ 饼干,第二天吃 $3$ 饼干。
  • 第一天吃 $3$ 饼干,第二天吃 $2$ 饼干。
  • 第一天吃$4$饼干,第二天吃$1$饼干。

我注意到路数会非常多,我妹妹还没数完就死了。 于是,我尝试用电脑程序来计算,以挽救妹妹的生命。


输入

输入由多个数据集组成。 数据集数量不超过 100 美元。 对于每个数据集,三个数字 $N$ ($1 \le N \le 2{,}000$)、$D$ ($1 \le D \le 10^{12}$) 和 $X$ ($1 \le X \le 2{,}000$) 写在一行中并用空格分隔。 输入的结尾由包含三个零的行表示。

输出

打印每个数据集一行中以 $1{,}000{,}000{,}007$ 为模的路数。


示例输入

5 2 5
3 3 3
5 4 5
4 1 2
1 5 1
1250 50 50
0 0 0

样本输入的输出

4
7
52
0
0
563144298