Problem:
 Score : 800 points    Problem Statement There are N squares arranged in a row, numbered 1 to N from left to right. Takahashi will stack building blocks on these squares, on which there are no blocks yet.  He wants to stack blocks on the squares evenly, so he will repeat the following operation until there are H blocks on every square:   Let M and m be the maximum and minimum numbers of blocks currently stacked on a square, respectively. Choose a square on which m blocks are stacked (if there are multiple such squares, choose any one of them), and add a positive number of blocks on that square so that there will be at least M and at most M + D blocks on that square.   Tell him how many ways there are to have H blocks on every square by repeating this operation. Since there can be extremely many ways, print the number modulo 10^9+7 .      Constraints  2 \leq N \leq 10^6  1 \leq D \leq H \leq 10^6  All values in input are integers.         Input Input is given from Standard Input in the following format:  N  H  D       Output Print the number of ways to have H blocks on every square, modulo 10^9+7 .        Sample Input 1 2 2 1      Sample Output 1 6  The possible transitions of (the number of blocks on Square 1 , the number of blocks on Square 2 ) are as follows:    (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)    Thus, there are six ways to have two blocks on every square.       Sample Input 2 2 30 15      Sample Output 2 94182806       Sample Input 3 31415 9265 3589      Sample Output 3 312069529  Be sure to print the number modulo 10^9+7 .

Solution (Python):
mod = 1000000007
eps = 10**-9


def main():
    import sys
    input = sys.stdin.readline

    N, H, D = map(int, input().split())
    imos = [0] * (H+2)
    ans = [0] * (H+1)
    M = 0
    f = 1
    for i in range(1, N+1):
        f = (f * i)%mod
        M = (M + f)%mod
    imos[1] += f
    imos[D+1] -= f
    for i in range(1, H):
        ans[i] = (ans[i-1] + imos[i])%mod
        imos[i+1] = (imos[i+1] + (ans[i] * M)%mod)%mod
        if i+D+1 <= H:
            imos[i+D+1] = (imos[i+D+1] - (ans[i] * M)%mod)%mod
    print((ans[H-1] + imos[H])%mod)


if __name__ == '__main__':
    main()

Solution (Python):
n, h, d = map(int, input().split())
MOD = 10 ** 9 + 7


fact = [1] * (n + 1)
for i in range(n):
    fact[i + 1] = fact[i] * (i + 1)
    fact[i + 1] %= MOD


fact_sum = 0
for i in range(1, n + 1):
    fact_sum += fact[i]
    fact_sum %= MOD

dp = [0] * (h + 1)
ru = [0] * (h + 2)
dp[0] = 1
ru[1] = 1
for i in range(h):
    l = max(i + 1 - d, 0)
    dp[i + 1] += (ru[i + 1] - ru[l]) * fact_sum
    dp[i + 1] %= MOD
    ru[i + 2] = ru[i + 1] + dp[i + 1]
    ru[i + 2] %= MOD

print((dp[-1] * fact[n] * pow(fact_sum, MOD - 2, MOD)) % MOD)

Solution (Python):
N,H,D=map(int,input().split())
mod=10**9+7

const=0
frac=[1]
for i in range(1,N+1):
    frac.append((frac[-1]*i)%mod)
    const=(const+frac[-1])%mod

dp=[0]*(H+1)
dp[0]=1
dp[1]=frac[-1]

S=dp[1]
for i in range(2,D+1):
    dp[i]=const*S+frac[-1]
    dp[i]%=mod
    S=(S+dp[i])%mod

S=sum(dp[i] for i in range(1,D+1))
S%=mod

for i in range(D+1,H+1):
    dp[i]=const*S
    dp[i]%=mod
    S=(S+dp[i]-dp[i-D])%mod

print(dp[H])

Solution (Python):

"""
Writer: SPD_9X2
https://atcoder.jp/contests/diverta2019-2/tasks/diverta2019_2_e
Mの時、 a1<=a2<=a3…aN
を満たす通り数 X[M] が分かれば解ける(全ての順N!は等しいため)

当然、次のMにはa1から順に更新していくことになる(M+?にね)
Dの時
X[M] = (X[M-1] + X[M-2] +　… + X[M-D]) * N
が成立かな
X[0] = 1

N=2
X[0]=1
X[1]=2
X[2]=6

N=3
X[0]=1
X[1]=9

X[M]の更新式
→これが間違ってそう
X[M] = (X[M-1] + X[M-2] +　… + X[M-D]) * (1!+2!+3!+…N!)
→エスパーだけどなんか正しそう

X[H-1]を求めてN!を掛ければそれが答え
→サンプル合った！！
"""
import math
N,H,D = map(int,input().split())
mod = 10**9+7

mul = 0
fac = 1
for i in range(1,N+1):
    fac *= i
    fac %= mod
    mul += fac
    mul %= mod

X = [1]
nsum = 1
for i in range(H-1):

    
    X.append(nsum*mul%mod)

    nsum += X[-1]
    nsum %= mod
    if i >= D-1:
        nsum -= X[i-D+1]
        


print (nsum * fac % mod)

Solution (Python):
import sys
readline = sys.stdin.readline

MOD = 10**9+7
def frac(limit):
    frac = [1]*limit
    for i in range(2,limit):
        frac[i] = i * frac[i-1]%MOD
    fraci = [None]*limit
    fraci[-1] = pow(frac[-1], MOD -2, MOD)
    for i in range(-2, -limit-1, -1):
        fraci[i] = fraci[i+1] * (limit + i + 1) % MOD
    return frac, fraci
frac, fraci = frac(1341398)
def comb(a, b):
    if not a >= b >= 0:
        return 0
    return frac[a]*fraci[b]*fraci[a-b]%MOD

N, H, D = map(int, readline().split())

M = 0
for i in range(1, N+1):
    M = (M+frac[i]) % MOD

dp = [0]*(H+2)
dp[1] = frac[N]
Dp = dp[:]

for i in range(2, H+1):
    dp[i] = M*(Dp[i-1] - Dp[max(0, i-D-1)]) % MOD
    Dp[i] = (Dp[i-1] + dp[i]) % MOD
dp[H+1] = (Dp[H] - Dp[max(0, H-D)]) % MOD
print(dp[H+1])

Solution (Python):
N,H,D=map(int,input().split())
mod=10**9+7
table=[1]
num=0
for i in range(1,N+1):
    table.append(table[-1]*i%mod)
    num=(num+table[-1])%mod
dp=[0]*(H+1)
d_sum=[0]*(H+1)
for i in range(1,D+1):
    dp[i]=table[N]
for i in range(1,H+1):
    dp[i]=(dp[i]+(d_sum[i-1]-d_sum[max(0,i-D-1)])*num)%mod
    d_sum[i]=(dp[i]+d_sum[i-1])%mod
print(dp[H])

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    md = 10 ** 9 + 7
    n, h, d = MI()
    sum_fact = 0
    n_fact = 1
    for x in range(1, n + 1):
        n_fact *= x
        sum_fact += n_fact
        n_fact %= md
        sum_fact %= md
    if h==1:
        print(n_fact)
        exit()
    dp = [0] * (h + 1)
    dp[0] = dp[1] = n_fact
    s = 0
    for i in range(2, h + 1):
        if i <= d:
            s += dp[i - 1]
            dp[i] = s * sum_fact + dp[0]
        elif i == d + 1:
            s += dp[i - 1]
            dp[i] = s * sum_fact
        else:
            s += dp[i - 1] - dp[i - 1 - d]
            dp[i] = s * sum_fact
        s %= md
        dp[i] %= md
    print(dp[-1])

main()

Solution (Python):
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 + 1)
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)

Solution (Python):
N, H, D = map(int, input().split())
MOD = 10 ** 9 + 7

fact = 1
s = 0
for i in range(1, N+1) :
    fact = fact * i % MOD
    s = (s + fact) % MOD

dp = [0] * H
dp[0] = 1
ret = 1

for i in range(1, H) :
    dp[i] = ret * s % MOD
    ret = (ret + ret * s) % MOD
    if i >= D : 
        ret = (ret - dp[i - D]) % MOD
        
print(ret * fact % MOD)

Solution (Python):
N, H, D = map(int, input().split())

MOD = 10**9 + 7

v = 1
w = 0
for i in range(1, N+1):
    v = v * i % MOD
    w += v
v %= MOD
w %= MOD

dp = [0]*(H+1)
dp[0] = v
s = 0
for i in range(H):
    s += dp[i] % MOD
    if i+1 < H:
        dp[i+1] = s * w % MOD
    else:
        dp[i+1] = s % MOD
    if i-D+1 >= 0:
        s -= dp[i-D+1] % MOD
print(dp[H])

Solution (Python):
N, H, D = map(int,input().split())
MOD = 10**9 + 7
 
fact = [1]
fact_cum = [0]
for i in range(1,N+1):
  fact.append((fact[-1]*i)%MOD)
  fact_cum.append((fact_cum[-1] + fact[-1])%MOD)
 
ap = [0] * (H+1)
ap_cum = [0] * (H+1)
ap[0] = 1
ap_cum[0] = 1
 
for n in range(1,H+1):
  x = ap_cum[n-1]
  if n > D:
    x -=ap_cum[n-D-1]
  x *= fact_cum[N]
  x %= MOD
  ap[n] = x
  ap_cum[n] = (ap_cum[n-1] + x)%MOD
 
 
ans = ap[H]
ans *= fact[N]
ans %= MOD
ans *= pow(fact_cum[N],MOD-2,MOD)
ans %= MOD
 
print(ans)

Solution (Python):
N, H, D = map(int, input().split())
P, a, s = 10**9+7, 1, 0
for i in range(1, N+1):
    a = a*i%P
    s = (s+a)%P

X = [a]
for i in range(1, H):
    X.append(a*s%P)
    a += X[-1]
    if i >= D: a -= X[-D-1]
    a %= P

print(a)

Solution (Python):
N, H, D = map(int, input().split())
P, a, s = 10**9+7, 1, 0
for i in range(1, N+1):
    a = a*i%P
    s = (s+a)%P

X = [a]
for i in range(1, H):
    X.append(a*s%P)
    a += X[-1]
    if i >= D: a -= X[-D-1]
    a %= P

print(a)

Solution (Python):
N, H, D = map(int,input().split())
MOD = 10**9 + 7

fact = [1]
fact_cum = [0] 
for i in range(1,N+1):
  fact.append((fact[-1]*i)%MOD)
  fact_cum.append((fact_cum[-1] + fact[-1])%MOD)

dp = [0] * (H+1)
dp_cum = [0] * (H+1)
dp[0] = 1
dp_cum[0] = 1

for n in range(1,H+1):
  x = dp_cum[n-1]
  if n > D:
    x -= dp_cum[n-D-1]
  x *= fact_cum[N]
  x %= MOD
  dp[n] = x
  dp_cum[n] = (dp_cum[n-1] + x)%MOD


answer = dp[H]
answer *= fact[N]
answer %= MOD
answer *= pow(fact_cum[N],MOD-2,MOD)
answer %= MOD

print(answer)

Solution (Python):
N, H, D = map(int,input().split())
MOD = 10**9 + 7

fact = [1]
fact_cum = [0] 
for i in range(1,N+1):
  fact.append((fact[-1]*i)%MOD)
  fact_cum.append((fact_cum[-1] + fact[-1])%MOD)

dp = [0] * (H+1)
dp_cum = [0] * (H+1)
dp[0] = 1
dp_cum[0] = 1

for n in range(1,H+1):
  x = dp_cum[n-1]
  if n > D:
    x -= dp_cum[n-D-1]
  x *= fact_cum[N]
  x %= MOD
  dp[n] = x
  dp_cum[n] = (dp_cum[n-1] + x)%MOD


answer = dp[H]
answer *= fact[N]
answer %= MOD
answer *= pow(fact_cum[N],MOD-2,MOD)
answer %= MOD

print(answer)

Solution (Python):
import sys
range = xrange
input = raw_input

mod = 10**9 + 7

n,h,d = [int(x) for x in input().split()]

big = 10**6+10
fac = [1]
while len(fac)<big:
    fac.append(fac[-1] * len(fac) % mod)

cumfac = [0]
for f in fac:
    cumfac.append((cumfac[-1] + f)%mod)

DP = [0]*(h+1)
DP[0] = fac[n]

multi = cumfac[n+1] - cumfac[1]
s = 0
for i in range(1,h):
    s += DP[i-1]
    if i-d-1>=0:
        s -= DP[i-d-1]
    s %= mod
    DP[i] = s*multi % mod


DP[h] = sum(DP[max(0,h-d):h]) % mod

print DP[-1]