题目描述

有 $N$ 个方块按照从左到右的顺序排列，编号为 $1$ 到 $N$。高桥会在这些方块上堆积积木，上面还没有积木。

他希望将积木均匀地堆积在方块上，因此他会重复以下操作，直到每个方块上都有 $H$ 个积木：

• 设 $M$ 和 $m$ 分别是当前在一个方块上堆积的积木的最多和最少数量。选择一个已经堆积了 $m$ 个积木的方块（如果存在多个这样的方块，选择其中任意一个），在该方块上添加一定数量的积木，使得该方块上的积木数量至少为 $M$，至多为 $M + D$。

告诉他通过重复执行此操作有多少种方式可以使得每个方块上都有 $H$ 个积木。由于方式可能非常多，以 $10^9+7$ 为模打印该数量。

约束条件

• $2 \leq N \leq 10^6$
• $1 \leq D \leq H \leq 10^6$
• 输入中的所有值均为整数。

输入

输入从标准输入读取，格式如下：

$N$ $H$ $D$

输出

以 $10^9+7$ 为模打印使得每个方块上都有 $H$ 个积木的方式的数量。

示例输入 1

2 2 1

示例输出 1

6

（方块 $1$ 上的积木数量，方块 $2$ 上的积木数量）的可能变化如下：

• $(0, 0)$ -> $(0, 1)$ -> $(1, 1)$ -> $(1, 2)$ -> $(2, 2)$

• $(0, 0)$ -> $(0, 1)$ -> $(1, 1)$ -> $(2, 1)$ -> $(2, 2)$

• $(0, 0)$ -> $(0, 1)$ -> $(2, 1)$ -> $(2, 2)$

• $(0, 0)$ -> $(1, 0)$ -> $(1, 1)$ -> $(1, 2)$ -> $(2, 2)$

• $(0, 0)$ -> $(1, 0)$ -> $(1, 1)$ -> $(2, 1)$ -> $(2, 2)$

• $(0, 0)$ -> $(1, 0)$ -> $(1, 2)$ -> $(2, 2)$

因此，有 $6$ 种方式使得每个方块上都有 $2$ 个积木。

示例输入 2

2 30 15

示例输出 2

94182806

示例输入 3

31415 9265 3589

示例输出 3

312069529

请记得以 $10^9+7$ 为模打印该数量。