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.



Sample input:
2 2 1


Sample output:
6

Submission status: Time Limit Exceeded

Solution code:

"""
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):

    #print (i,nsum,mul)
    X.append(nsum*mul%mod)

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

#print (X)
print (nsum * math.factorial(N) % mod)

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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 = fact[1] + fact[2] + ... + fact[n]
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)

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:

"""
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):

    #print (i,nsum,mul)
    X.append(nsum*mul%mod)

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

#print (X)
print (nsum * fac % mod)

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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])

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

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

fact = [1]
fact_cum = [0] # 1! to N!
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)

Submission status: Accepted

Solution code:
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

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

print DP[-1]

Submission status: Runtime Error

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


if d != 1:
    print(re)

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

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

dp = [0] * (h + 1)
dp[0] = 1
for i in range(h):
    dp[i + 1] = dp[i] * fact_sum
    dp[i + 1] %= MOD

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

Submission status: Runtime Error

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


if n * h + h * d >= 10 ** 7:
    print(re)

# dp[i][j] := 高さiのブロックが最大高さでj個ある時の通り数
dp = [[0] * (n + 1) for i in range(h + 1)]
dp[0][n] = 1

# O(HN)
ru = [[0] * (n + 2) for i in range(h + 1)]
ru[0][n + 1] = 1
for i in range(h):
    # j = 0 -> j = 1 にする
    for diff in range(1, d + 1):
        if i + 1 - diff < 0:
            continue
        dp[i + 1][1] += ru[i + 1 - diff][n + 1]
        dp[i + 1][1] %= MOD

    # j - 1 -> j にする
    for j in range(2, n + 1):
        dp[i + 1][j] += dp[i + 1][j - 1] * j
        dp[i + 1][j] %= MOD

    for j in range(n + 1):
        ru[i + 1][j + 1] = ru[i + 1][j] + dp[i + 1][j]
        ru[i + 1][j + 1] %= MOD

print(dp[-1][-1] % MOD)

Submission status: Runtime Error

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


if n * h >= 10 ** 7:
    print(re)

# dp[i][j] := 高さiのブロックが最大高さでj個ある時の通り数
dp = [[0] * (n + 1) for i in range(h + 1)]
dp[0][n] = 1

# O(HN)
ru = [[0] * (n + 2) for i in range(h + 1)]
ru[0][n + 1] = 1
for i in range(h):
    # j = 0 -> j = 1 にする
    for diff in range(1, d + 1):
        if i + 1 - diff < 0:
            continue
        dp[i + 1][1] += ru[i + 1 - diff][n + 1]

    # j - 1 -> j にする
    for j in range(2, n + 1):
        dp[i + 1][j] += dp[i + 1][j - 1] * j
        dp[i + 1][j] %= MOD

    for j in range(n + 1):
        ru[i + 1][j + 1] = ru[i + 1][j] + dp[i + 1][j]
        ru[i + 1][j + 1] %= MOD

print(dp[-1][-1] % MOD)

Submission status: Runtime Error

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


if n * h * d >= 10 ** 7:
    print(re)

# dp[i][j] := 高さiのブロックが最大高さでj個ある時の通り数
dp = [[0] * (n + 1) for i in range(h + 1)]
dp[0][n] = 1

# O(HDN)
for i in range(h):
    # j = 0 -> j = 1 にする
    for diff in range(1, d + 1):
        if i + 1 - diff < 0:
            continue
        for cnt in range(1, n + 1):
            dp[i + 1][1] += dp[i + 1 - diff][cnt]
            dp[i + 1][1] %= MOD

    # j - 1 -> j にする
    for j in range(2, n + 1):
        dp[i + 1][j] += dp[i + 1][j - 1] * j
        dp[i + 1][j] %= MOD

print(dp[-1][-1] % MOD)

Submission status: Runtime Error

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


if n * h * d >= 10 ** 7:
    print(re)

# dp[i][j] := 高さiのブロックが最大高さでj個ある時の通り数
dp = [[0] * (n + 1) for i in range(h + 1)]
dp[0][n] = 1

# O(HDN)
for i in range(h):
    # j = 0 -> j = 1 にする
    for diff in range(1, d + 1):
        if i + 1 - diff < 0:
            continue
        for cnt in range(1, n + 1):
            dp[i + 1][1] += dp[i + 1 - diff][cnt] * cnt
            dp[i + 1][1] %= MOD

    # j -> j + 1 にする
    for j in range(2, n + 1):
        dp[i + 1][j] += dp[i + 1][j - 1] * (n - (j - 1))
        dp[i + 1][j] %= MOD

print(dp[-1][-1] % MOD)

Submission status: Runtime Error

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


if n * h * d >= 10 ** 7:
    print(re)

# dp[i][j] := 高さiのブロックが最大高さでj個ある時の通り数
dp = [[0] * (n + 1) for i in range(h + 1)]
dp[0][n] = 1

# O(HDN)
for i in range(h):
    # j = 0 -> j = 1 にする
    for diff in range(1, d + 1):
        if i + 1 - diff < 0:
            continue
        for cnt in range(1, n + 1):
            dp[i + 1][1] += dp[i + 1 - diff][cnt] * cnt
            dp[i + 1][1] %= MOD

    # j -> j + 1 にする
    for j in range(2, n + 1):
        dp[i + 1][j] += dp[i + 1][j - 1] * (n - (j - 1))
        dp[i + 1][j] %= MOD

print(dp[-1][-1])

Submission status: Runtime Error

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

# dp[i][j] := 高さiのブロックが最大高さでj個ある時の通り数
dp = [[0] * (n + 1) for i in range(h + 1)]
dp[0][n] = 1

# O(HDN)
for i in range(h):
    # j = 0 -> j = 1 にする
    for diff in range(1, d + 1):
        if i + 1 - diff < 0:
            continue
        for cnt in range(1, n + 1):
            dp[i + 1][1] += dp[i + 1 - diff][cnt] * cnt
            dp[i + 1][1] %= MOD

    # j -> j + 1 にする
    for j in range(2, n + 1):
        dp[i + 1][j] += dp[i + 1][j - 1] * (n - (j - 1))
        dp[i + 1][j] %= MOD

print(dp[-1][-1])

Submission status: Runtime Error

Solution code:
// includes
#include <bits/stdc++.h>

// macros
#define ll long long int
#define pb emplace_back
#define mk make_pair
#define pq priority_queue
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define rep(i, n) FOR(i, 0, n)
#define rrep(i, n) for(int i=((int)(n)-1);i>=0;i--)
#define irep(itr, st) for(auto itr = (st).begin(); itr != (st).end(); ++itr)
#define irrep(itr, st) for(auto itr = (st).rbegin(); itr != (st).rend(); ++itr)
#define vrep(v, i) for(int i = 0; i < (v).size(); i++)
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end())
#define FI first
#define SE second
#define dump(a, n) for(int i = 0; i < n; i++)cout << a[i] << "\n "[i + 1 != n];
#define dump2(a, n, m) for(int i = 0; i < n; i++)for(int j = 0; j < m; j++)cout << a[i][j] << "\n "[j + 1 != m];
#define bit(n) (1LL<<(n))
#define INT(n) int n; cin >> n;
#define LL(n) ll n; cin >> n;
#define DOUBLE(n) double n; cin >> n;
using namespace std;

//  types
typedef pair<int, int> P;
typedef pair<ll, int> Pl;
typedef pair<ll, ll> Pll;
typedef pair<double, double> Pd;
typedef complex<double> cd;
 
// constants
const int inf = 1e9;
const ll linf = 1LL << 50;
const double EPS = 1e-10;
const int mod = 1e9 + 7;
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, -1, 0, 1};

// solve
template <class T>bool chmax(T &a, const T &b){if(a < b){a = b; return 1;} return 0;}
template <class T>bool chmin(T &a, const T &b){if(a > b){a = b; return 1;} return 0;}
template <typename T> istream &operator>>(istream &is, vector<T> &vec){for(auto &v: vec)is >> v; return is;}
template <typename T> ostream &operator<<(ostream &os, const vector<T>& vec){for(int i = 0; i < vec.size(); i++){ os << vec[i]; if(i + 1 != vec.size())os << " ";} return os;}
template <typename T> ostream &operator<<(ostream &os, const set<T>& st){for(auto itr = st.begin(); itr != st.end(); ++itr){ os << *itr; auto titr = itr; if(++titr != st.end())os << " ";} return os;}
template <typename T> ostream &operator<<(ostream &os, const unordered_set<T>& st){for(auto itr = st.begin(); itr != st.end(); ++itr){ os << *itr; auto titr = itr; if(++titr != st.end())os << " ";} return os;}
template <typename T> ostream &operator<<(ostream &os, const multiset<T>& st){for(auto itr = st.begin(); itr != st.end(); ++itr){ os << *itr; auto titr = itr; if(++titr != st.end())os << " ";} return os;}
template <typename T> ostream &operator<<(ostream &os, const unordered_multiset<T>& st){for(auto itr = st.begin(); itr != st.end(); ++itr){ os << *itr; auto titr = itr; if(++titr != st.end())os << " ";} return os;}
template <typename T1, typename T2> ostream &operator<<(ostream &os, const pair<T1, T2> &p){os << p.first << " " << p.second; return os;}
template <typename T1, typename T2> ostream &operator<<(ostream &os, const map<T1, T2> &mp){for(auto itr = mp.begin(); itr != mp.end(); ++itr){ os << itr->first << ":" << itr->second; auto titr = itr; if(++titr != mp.end())os << " "; } return os;}
template <typename T1, typename T2> ostream &operator<<(ostream &os, const unordered_map<T1, T2> &mp){for(auto itr = mp.begin(); itr != mp.end(); ++itr){ os << itr->first << ":" << itr->second; auto titr = itr; if(++titr != mp.end())os << " "; } return os;}

template <typename T>
T power(T a, T n, T mod) {
  T res = 1;
  T tmp = n;
  T curr = a;
  while(tmp){
    if(tmp % 2 == 1){
      res = (T)((ll)res * curr % mod);
    }
    curr = (T)((ll)curr * curr % mod);
    tmp >>= 1;
  }

  return res;
}

ll fac[1000001], fsum[1000001];
ll dp[1000001], dpsum[1000001];

int main(int argc, char const* argv[])
{
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout << fixed << setprecision(20);
  LL(n); LL(h); LL(d);
  fac[0] = 1; FOR(i, 1, 1000001)fac[i] = i * fac[i-1] % mod;
  FOR(i, 1, 1000001)fsum[i] = (fac[i] + (i > 1 ? fsum[i-1]: 0)) % mod;
  dp[1] = 1;
  dpsum[1] = 1;
  FOR(i, 2, h + 1){
    dp[i] = dpsum[i-1];
    if(i-d-1>=0)dp[i] = (dp[i] - dpsum[i-d-1]) % mod;
    if(dp[i]<0)dp[i] += mod;
    dp[i] = dp[i] * fsum[n] % mod;
    if(i <= d)dp[i]++;

    dpsum[i] = (dpsum[i-1] + dp[i]) % mod;
  }

  cout << dp[h] * fac[n] % mod << endl;
  return 0;
}

Submission status: Runtime Error

Solution code:
n = int(input())
fib = 1
if n < 10:
    fib = [1, 2, 4, 7, 12, 20, 33, 54, 88]
else:
    fib = [1, 2, 4, 7, 12, 20, 33, 54, 55]
    
prod = [1] * 10
for i in range(1,9):
    prod[i] = prod[i-1] * fib[i]
    

ans = [[0] * n for i in range(n)]
for i in range(n):
    for j in range(i+1, n):
        ans[i][j] = ans[j][i] = fib[j-i-1] * prod[n-2-i]

for i in range(n):
    print(" ".join(list(map(str, ans[i]))))

Submission status: Runtime Error

Solution code:
a = "2 2 1"
print "6"

Submission status: Runtime Error

Solution code:
n = int(input())
ga, sa, ba = list(map(int, input().split()))
gb, sb, bb = list(map(int, input().split()))

w_ab = []
v_ab = []

if ga < gb:
    w_ab.append(ga)
    v_ab.append(gb)
if sa < sb:
    w_ab.append(sa)
    v_ab.append(sb)
if ba < bb:
    w_ab.append(ba)
    v_ab.append(bb)

num = (n+1)*(len(w_ab)+1)
dp = [0]*num
for i in range(len(w_ab)):
    for j in range(n+1):
        if j < w_ab[i]:
            dp[(i+1)*(n+1) + j] = dp[i*(n+1) + j]
        else:
            dp[(i+1)*(n+1) + j] = max(dp[i*(n+1) + j], dp[(i+1)*(n+1) + j - w_ab[i]] + v_ab[i])
ans = 0
length = len(w_ab)
for j in range(n+1):
    ans = max(ans, dp[length*(n+1) + j] + n-j)
n = ans

w_ab = []
v_ab = []

if ga > gb:
    w_ab.append(gb)
    v_ab.append(ga)
if sa > sb:
    w_ab.append(sb)
    v_ab.append(sa)
if ba > bb:
    w_ab.append(bb)
    v_ab.append(ba)

num = (n+1)*(len(w_ab)+1)
dp = [0]*num
for i in range(len(w_ab)):
    for j in range(n+1):
        if j < w_ab[i]:
            dp[(i+1)*(n+1) + j] = dp[i*(n+1) + j]
        else:
            dp[(i+1)*(n+1) + j] = max(dp[i*(n+1) + j], dp[(i+1)*(n+1) + j - w_ab[i]] + v_ab[i])

length = len(w_ab)
ans = 0
for j in range(n+1):
    ans = max(ans, dp[length*(n+1) + j] + n-j)
print(ans)