DPっぽい雰囲気を感じるが、状態数がとんでもないことになりそうで、実は少ない状態数で解ける問題。
問題文の通りに実装しようとすると、「何個の箱が積まれたマスが何マスあるか」、全 $O(H^N)$ の状態を持っておかねばならないように見える。 「最大値」「最小値のマス」に加え、「その最小値のマスが最小値で無くなったら次に最小値となるマス」の特定が必要だからだ。
当然、その方法では無理。
以下のような数列を考えると、取っかかりが見つかる。
$N=3$ 個のマスに高さ $H=4$ 個まで、$D=2$ で箱を積むと、例えばこんな数列ができる。
0 0 0 1 3 3 4 4 4
すると、この問題において「マスに積まれた箱の個数の組合せ」の遷移は、この数列を幅 $N$ の窓で順にスライドさせた状態と一致する。
1 0 0 0 2 0 0 1 0のマスに箱を積んで1にする 3 0 1 3 0のマスに箱を積んで3にする 4 1 3 3 0のマスに箱を積んで3にする 5 3 3 4 1のマスに箱を積んで4にする 6 3 4 4 3のマスに箱を積んで4にする 7 4 4 4 3のマスに箱を積んで4にする
よって、このような数列の個数を数え上げることが、解答への一歩となる。
ただしこのままだと、途中で最小値の箱が複数ある場合にどれを選んでもよいことが考慮されていない。
例えば上記では3が2つ出てくるが、数列の解釈では「3番目の操作で先に0から3にしたマスを、6番目の操作で先に3から4にする」パターンしか考えられていない。 しかし実際は、4番目の操作で後から3になったマスを、3から4にするときには先に操作してもよい。
この操作順序の入れ替わりパターンは、ある数字について同じ数字が $K$ 個あると、$K!$ 通り発生する。
0 0 0 1 1 1 2 2 2 3 3 3 4 4 4 だと、数列としては1個でも操作パターンとしては $3! \times 3! \times 3! \times 3! = 1296$ 通り存在する。
なお、$H=4$ については次の操作が無いので、$K$ 個あっても $K!$ 倍する必要は無い。
これを踏まえて、DPを考える。
まず、入れ替わりを考えず、数列の個数を単純に数えるなら、以下のようになるだろう。
$DP[i]=$ 数列の右端が $i$ であるような、条件を満たす数列の個数
途中の数字は $D$ 個までなら飛ばしてもいいので、遷移元は $DP[i-D]～DP[i-1]$ の和となる。
これに $N$ をかけているのは、$i$ が1個、2個、…、$N$ 個並ぶパターン（全 $N$ 通り）を考慮している。
答えは、$DP[H-D]～DP[H-1]$ の和となる。 $DP[H]$ まで計算しなくていいのは、$H$ については目標の状態である $N$ 個並ぶパターンのみ数えればよいから。 （他と同様に計算すると、1個だけ並ぶパターンなどが含まれてしまう）
次に、入れ替わりを考慮して数えると、こう変化する。
まず初期状態で、これからどの順で操作するかのパターン数が $N!$ になる。
また、先ほどの $N$ をかけていた箇所が階乗の和に変化しているが、これは $i$ が $k$ 個並ぶパターンでそれぞれ $k!$ 通りに派生するのを合計している。
階乗の和は $i$ に依らないので事前計算してしまえ、このアルゴリズムは $O(N+H)$ で動作する。
n, h, d = map(int, input().split())
MOD = 10 ** 9 + 7
fact, fact_acc = 1, 1
for i in range(2, n + 1):
fact = fact * i % MOD
fact_acc = (fact_acc + fact) % MOD
dp = [0] * h
dp[0] = base = fact
for i in range(1, h):
dp[i] = base * fact_acc % MOD
base = (base + dp[i]) % MOD
if i >= d:
base = (base - dp[i - d]) % MOD
print(base)