有一天，奶奶留下了 $N$ 块饼干。我和姐姐打算立刻把它们吃掉，但有一条说明：

• 饼干会变质；你必须在 $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$ 取模的结果。

样例

样例输入 1

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

样例输出 1

4
7
52
0
0
563144298