题目描述

$N$ 個のマスが横一列に並んでおり、左から順に $1$ から $N$ までの番号がつけられています。高橋君はこれらのマスに積み木を積もうとしています。 まだそれぞれのマスには積み木が $1$ つも積まれていません。

積み木をバランス良く積みたい高橋君は、以下の操作を繰り返して全てのマスに積み木がちょうど $H$ 個ずつ積まれている状態にしようとしています。

• $1$ マスに積まれている積み木の最大値を $M$ 個、最小値を $m$ 個とする。$m$ 個の積み木が置かれているマスを $1$ つ選び (複数ある場合はどれを選んでもよい)、そのマスに積まれた積み木が $M$ 個以上 $M\ +\ D$ 個以下になるように積み木を正の個数積む。

高橋君のために、この操作を繰り返して全てのマスに積み木がちょうど $H$ 個積まれている状態にする方法が何通りあるか数えてあげてください。答えは非常に大きくなる場合があるので、$10^9+7$ で割った余りを出力してください。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $H$ $D$

输出格式

全てのマスに積み木がちょうど $H$ 個積まれている状態にする方法の個数を $10^9+7$ で割った余りを出力せよ。

题目大意

有一个长度为 $N(2\le N \le 10^6)$ 的数组，一开始所有元素均为 $0$。

设 $M$ 为当前数组中的最大元素，$m$ 是当前数组中的最小元素，你可以执行若干次以下操作：

• 选择一个大小为 $m$ 的元素，把他变为 $x$，其中 $M\le x \le M+D$ 且 $m<x$。

求有多少种操作方法使得数组中的所有元素均为 $H$，对 $10^9+7$ 取模。

$1\le D\le H\le10^6$

2 2 1

6

2 30 15

94182806

31415 9265 3589

312069529

提示

制約

• $2\ \leq\ N\ \leq\ 10^6$
• $1\ \leq\ D\ \leq\ H\ \leq\ 10^6$
• 入力は全て整数である

Sample Explanation 1

(マス $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)$ よって、全てのマスに積み木がちょうど $2$ 個積まれている状態にする方法の個数は $6$ 通りです。

Sample Explanation 3

個数を $10^9+7$ で割った余りを出力することに注意してください。