问题陈述
有一天,我的奶奶留下了 $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