配点 : $800$ 点

問題文

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

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

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

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

制約

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

入力

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

$N$ $H$ $D$

出力

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

2 2 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)$

よって、全てのマスに積み木がちょうど $2$ 個積まれている状態にする方法の個数は $6$ 通りです。

2 30 15

94182806

31415 9265 3589

312069529

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