AT_diverta2019_2_e.Balanced Piles

有 $N$ 个格子横向排列，从左到右依次编号为 $1$ 到 $N$。高桥君打算在这些格子上堆积木。初始时，每个格子上都没有积木。

高桥君希望将积木堆得均匀，他会重复以下操作，直到每个格子上都恰好堆有 $H$ 个积木为止：

• 设当前所有格子中积木数的最大值为 $M$，最小值为 $m$。从所有积木数为 $m$ 的格子中任选一个（如果有多个可以任选），在该格子上堆若干个积木，使得该格子的积木数变为 $M$ 以上且不超过 $M+D$，即堆到 $M$、$M+1$、$\dots$、$M+D$ 中的某一个数。

请你帮高桥君计算，经过若干次上述操作后，使所有格子上都恰好有 $H$ 个积木的方法总数。由于答案可能非常大，请输出对 $10^9+7$ 取模后的结果。

输入为一行，包含三个整数：

$N$ $H$ $D$

输出使所有格子上都恰好有 $H$ 个积木的方法总数，对 $10^9+7$ 取模。

限制条件

• $2 \leq N \leq 10^6$
• $1 \leq D \leq H \leq 10^6$
• 输入均为整数

样例解释 1

（格子 $1$ 上的积木数，格子 $2$ 上的积木数）可以按如下方式变化：

• $(0, 0) \to (0, 1) \to (1, 1) \to (1, 2) \to (2, 2)$
• $(0, 0) \to (0, 1) \to (1, 1) \to (2, 1) \to (2, 2)$
• $(0, 0) \to (0, 1) \to (2, 1) \to (2, 2)$
• $(0, 0) \to (1, 0) \to (1, 1) \to (1, 2) \to (2, 2)$
• $(0, 0) \to (1, 0) \to (1, 1) \to (2, 1) \to (2, 2)$
• $(0, 0) \to (1, 0) \to (1, 2) \to (2, 2)$

因此，使所有格子上都恰好有 $2$ 个积木的方法总数为 $6$。

样例解释 3

注意要输出对 $10^9+7$ 取模后的结果。

由 ChatGPT 4.1 翻译