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 翻译