Problem:


Score : 900 points

Problem Statement

There is a rectangular sheet of paper with height H+1 and width W+1. We introduce an xy-coordinate system so that the four corners of the sheet are (0, 0), (W + 1, 0), (0, H + 1) and (W + 1, H + 1).

This sheet can be cut along the lines x = 1,2,...,W and the lines y = 1,2,...,H. Consider a sequence of operations of length K where we choose K of these H + W lines and cut the sheet along those lines one by one in some order.

Let the score of a cut be the number of pieces of paper that exist just after the cut. The score of a sequence of operations is the sum of the scores of all of the K cuts.

Find the sum of the scores of all possible sequences of operations of length K. Since this value can be extremely large, print the number modulo 10^9 + 7.

Constraints

1 \leq H,W \leq 10^7

1 \leq K \leq H + W

H, W and K are integers.

Input

Input is given from Standard Input in the following format:

H W K

Output

Print the sum of the scores, modulo 10^9 + 7.

Sample Input 1

2 1 2

Sample Output 1

34

Let x_1, y_1 and y_2 denote the cuts along the lines x = 1, y = 1 and y = 2, respectively. The six possible sequences of operations and the score of each of them are as follows:

y_1, y_2: 2 + 3 = 5

y_2, y_1: 2 + 3 = 5

y_1, x_1: 2 + 4 = 6

y_2, x_1: 2 + 4 = 6

x_1, y_1: 2 + 4 = 6

x_1, y_2: 2 + 4 = 6

The sum of these is 34.

Sample Input 2

30 40 50

Sample Output 2

616365902

Be sure to print the sum modulo 10^9 + 7.



Sample input:
2 1 2


Sample output:
34

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import numpy as np
def PaperCutting(H,W,K):
#     nodes = defaultdict(int)
#     cal_nodes = {}
#     next_layer = {}
    nodes = np.zeros([H+1,W+1],dtype=int)
    pathes = np.zeros([H+1,W+1],dtype=int)
    pathes[0][0]=1
    scores = [[(h+1)*(w+1) for w in range(W+1)] for h in range(H+1) ]
    depth = 1
    while depth <= K:
        for h in range(min(depth,H)+1):
            w = depth-h
            if w <= W:
                ph = (pathes[h-1][w] if h-1 >= 0 else 0) % (10**9+7)
                pw = (pathes[h][w-1] if w-1 >= 0 else 0 ) % (10**9+7)
                pathes[h][w] = ph* (H-h+1) + pw* (W-w+1) 
                nodes[h][w] = (nodes[h-1][w] + scores[h][w] * ph) * (H-h+1)  + (nodes[h][w-1] + scores[h][w] * pw) * (W-w+1)
                nodes[h][w] = nodes[h][w] % (10**9+7)
        depth += 1 
    print( int(sum([nodes[h][K-h]  for h in range(K+1) if h<=H and K-h<=W])  % (10**9+7)) )

Submission status: Wrong Answer

Solution code:
MOD = 10**9 + 7
list_size = 20000001

f_list = [1] * list_size
f_r_list = [1] * list_size

for i in range(list_size - 1):
	f_list[i + 1] = int((f_list[i] * (i + 2)) % MOD)

f_r_list[-1] = pow(f_list[-1], MOD - 2, MOD)

for i in range(2, list_size + 1):
	f_r_list[-i] = int((f_r_list[-i + 1] * (list_size + 2 - i)) % MOD)

h, w, k = map(int, input().split())
ans = k * f_list[h+w-1] * f_r_list[h+w-k-1]
ans += (h+w) * k * (k+1) * f_list[h+w-2] * f_r_list[1] * f_r_list[h+w-k-1]
ans %= MOD
ans += h * w * f_list[h+w-3] * (k-1) * k * (k+1) * pow(3, MOD-2, MOD) * f_r_list[h+w-k-1]
ans %= MOD
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict

def calc5(all_nodes,H,W,K):
    while K != 0:
        next_nodes = dict()
        for k,v in all_nodes.items():
            if k[0]+1 <= H+1:
                k0 = k[0]+1
                s = ((k[0]+1)*k[1]+k[2] )
                if (k0,k[1],s) in next_nodes:
                    next_nodes[(k0,k[1],s) ] += v * (H+1-k[0])
                else:
                    next_nodes[(k0,k[1],s) ] = v * (H+1-k[0])
            if k[1]+1 <= W+1:
                k1 = k[1]+1
                s = ((k[1]+1)*k[0]+k[2] )
                if (k[0],k1,s) in next_nodes:
                    next_nodes[(k[0],k1,s) ] += v* (W+1-k[1])
                else:
                    next_nodes[(k[0],k1,s) ] = v* (W+1-k[1])
                    
        all_nodes = next_nodes
        K -= 1
    print( sum([ k[2]*v for k,v in all_nodes.items()]) )
    #a = ( sum([ k[2]*v for k,v in all_nodes.items()]) )

def main5(H,W,K):
    all_nodes = {}
    all_nodes[(1,1,0)] = 1
    calc5(all_nodes,H,W,K)
    
if __name__ == '__main__':
    # H,W,K = sys.argv[1:]
    tmp = input()
    H,W,K = tmp.split()
    main5(int(H),int(W),int(K))

Submission status: Wrong Answer

Solution code:
def solve(h, w, k):
    n = h + w
    MOD = 10 ** 9 + 7

    if k == 1:
        return 2 * n

    ans = 0
    # (0, 0) ... k * nPk * 1
    ans += k * n * (n - 1) % MOD
    # (i, 0) (0, j) ... sum(t for t=1..k) * (n-1)P(k-1) * (h+w)
    tmp = k * (k + 1) // 2 * (n - 1) % MOD
    ans += tmp * n % MOD
    # (i, j) ... sum((t-1)(k-t+1) for t=1..k) * (n-2)P(k-2) * 2 * h*w
    #            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~ = (k-1)k(k+1)/6
    if k >= 2:
        tmp = k * (pow(k, 2, MOD) - 1) // 3 % MOD
        ans += tmp * h * w % MOD

    for m in range(n - 2, n - k, -1):
        ans = ans * m % MOD
    return ans % MOD


h, w, k = map(int, input().split())
print(solve(h, w, k))

Submission status: Wrong Answer

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

# (0, 0) ... k * nPk * 1
ans += k * n * (n - 1) % MOD
# (i, 0) (0, j) ... sum(t for t=1..k) * (n-1)P(k-1) * (h+w)
tmp = k * (k + 1) // 2 * (n - 1) % MOD
ans += tmp * n % MOD
# (i, j) ... sum((t-1)(k-t+1) for t=1..k) * (n-2)P(k-2) * 2 * h*w
#            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~ = (k-1)k(k+1)/6
if k >= 2:
    tmp = k * (pow(k, 2, MOD) - 1) // 3 % MOD
    ans += tmp * h * w % MOD

for m in range(n - 2, n - k, -1):
    ans = ans * m % MOD

print(ans)

Submission status: Wrong Answer

Solution code:
mod = 10 ** 9 + 7
h, w, k = map(int, input().split())
s = h+w
p = 1
pp = 1
for x in range(s-k+1,s+1):
  p = (p*x)%mod
  if x == s-2:
    pp = p
a = (k**2%mod+k%mod)/2
b = (k**3%mod-k%mod)/3
e = k*p%mod + a*p%mod + (b*h*w*pp)%mod
print(int(e%mod))

Submission status: Wrong Answer

Solution code:
from itertools import permutations

mod = 10 ** 9 + 7
h, w, k = map(int, input().split())
s = range(h+w) 
p = list(permutations(s, k))
ans = 0

for i in p:
  a = 2
  b = 0
  hh = 0
  ww = 0
  for j in i:
    if j < h:
      b += ww+1
      hh += 1
    else:
      b += hh+1
      ww += 1
    a += b
  ans += a

print(ans % mod)

Submission status: Wrong Answer

Solution code:
from itertools import permutations

h, w, k = map(int, input().split())

li = range(h+w)

pli = list(permutations(li, k))

sum = 0


for p in pli:
    s = 1
    x = 1
    y = 1
    
    for a in p:
        if a < h:
            x += 1
            s += (y+1)
        else:
            y += 1
            s += (x+1)
    
    sum += s

ans = sum % (1000000007)
print(ans)

Submission status: Wrong Answer

Solution code:
from itertools import permutations

h, w, k = map(int, input().split())

li = range(h+w)

pli = list(permutations(li, k))

sum = 0


for p in pli:
    s = 1
    x = 1
    y = 1
    
    for a in p:
        if a < h:
            x += 1
            s += (y+1)
        else:
            y += 1
            s += (x+1)
    sum += s

ans = sum % (10^9+7)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
mod=10**9+7
def mul(a,b):
    x,y=a,b
    return (x*y)%mod

H,W,K=map(int,input().split())
mod=10**9+7
ans=0
const=1
for i in range(H+W-1,H+W-K,-1):
    const=(const*i)%mod

inv=pow(H+W-1,mod-2,mod)
for i in range(K):
    #ans+=(K-i)*(((H+W)*const)%mod)+(((K-i)*i*const)%mod)*((inv*2*H*W)%mod)
    #ans%=mod
    temp1=mul(mul(H+W,const),K-i)
    ans=(ans+temp1)%mod
    temp2=mul(inv,mul(2*H*W,mul(K-i,mul(i,const))))
    ans=(ans+temp2)%mod
ans+=mul(K,mul(H+W,const))
ans%=mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
mod=10**9+7
def mul(a,b):
    x,y=a,b
    return (x*y)%mod

H,W,K=map(int,input().split())
mod=10**9+7
ans=0
const=1
for i in range(H+W-1,H+W-K,-1):
    const=(const*i)%mod

inv=pow(H+W-1,mod-2,mod)
for i in range(K):
    #ans+=(K-i)*(((H+W)*const)%mod)+(((K-i)*i*const)%mod)*((inv*2*H*W)%mod)
    #ans%=mod
    temp1=mul(mul(H+W,const),K-i)
    ans=(ans+temp1)%mod
    temp2=mul(inv,mul(2*H*W,mul((K-i)*i,const)))
    ans=(ans+temp2)%mod
ans+=mul(K,mul(H+W,const))
ans%=mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
H,W,K=map(int,input().split())
mod=10**9+7
ans=0
const=1
for i in range(H+W-1,H+W-K,-1):
    const=(const*i)%mod

inv=pow(H+W-1,mod-2,mod)
for i in range(K):
    ans+=(K-i)*(((H+W)*const)%mod)+(((K-i)*i*const)%mod)*((inv*2*H*W)%mod)
    ans%=mod
ans+=K*(H+W)*const
ans%=mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
H,W,K=map(int,input().split())
mod=10**9+7
ans=0
const=1
for i in range(H+W-1,H+W-K,-1):
    const=(const*i)%mod

inv=pow(H+W-1,mod-2,mod)
for i in range(K):
    ans+=(K-i)*(H+W)*const+(K-i)*i*const*inv*2*H*W
    ans%=mod
ans+=K*(H+W)*const
ans%=mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def cmb(n, r, mod):#コンビネーションの高速計算　
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 2*10**7
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

H,W,K=map(int,input().split())
ans=K*((g1[H+W]*g2[H+W-K])%mod)
ans%=mod
for i in range(K):
    p=((K-i)*(g1[H+W-(i+1)]*g2[(H+W-K)]%mod))%mod
    q=(H+W)*cmb(H+W-1,i,mod)+(((2*H*W)%mod)*cmb(H+W-2,i-1,mod))%mod
    ans+=p*((q*g1[i])%mod)
    ans%=mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

def calc5(all_nodes,H,W,K):
    for _ in range(K):
        next_nodes = dict()
        for k,v in all_nodes.items():
            if k[0]+1 <= H+1:
                k0 = k[0]+1
                s = ((k0)*k[1]+k[2] )
                if (k0,k[1],s) in next_nodes:
                    next_nodes[(k0,k[1],s) ] += v * (H+1-k[0])
                else:
                    next_nodes[(k0,k[1],s) ] = v * (H+1-k[0])
            if k[1]+1 <= W+1:
                k1 = k[1]+1
                s = ((k1)*k[0]+k[2] )
                if (k[0],k1,s) in next_nodes:
                    next_nodes[(k[0],k1,s) ] += v* (W+1-k[1])
                else:
                    next_nodes[(k[0],k1,s) ] = v* (W+1-k[1])
                    
        all_nodes = next_nodes
    print( sum([ k[2]*v for k,v in all_nodes.items()])%(10**9+7) )

def main5(H,W,K):
    all_nodes = {}
    all_nodes[(1,1,0)] = 1
    calc5(all_nodes,H,W,K)
    
if __name__ == '__main__':
    # H,W,K = sys.argv[1:]
    tmp = input()
    H,W,K = tmp.split()
    main5(int(H),int(W),int(K))

Submission status: Time Limit Exceeded

Solution code:
import sys

def calc5(all_nodes,H,W,K):
    while K != 0:
        next_nodes = dict()
        for k,v in all_nodes.items():
            if k[0]+1 <= H+1:
                k0 = k[0]+1
                s = ((k[0]+1)*k[1]+k[2] )
                if (k0,k[1],s) in next_nodes:
                    next_nodes[(k0,k[1],s) ] += v * (H+1-k[0])
                else:
                    next_nodes[(k0,k[1],s) ] = v * (H+1-k[0])
            if k[1]+1 <= W+1:
                k1 = k[1]+1
                s = ((k[1]+1)*k[0]+k[2] )
                if (k[0],k1,s) in next_nodes:
                    next_nodes[(k[0],k1,s) ] += v* (W+1-k[1])
                else:
                    next_nodes[(k[0],k1,s) ] = v* (W+1-k[1])
                    
        all_nodes = next_nodes
        K -= 1
    print( sum([ k[2]*v for k,v in all_nodes.items()])%(10**9+7) )
    #a = ( sum([ k[2]*v for k,v in all_nodes.items()]) )

def main5(H,W,K):
    all_nodes = {}
    all_nodes[(1,1,0)] = 1
    calc5(all_nodes,H,W,K)
    
if __name__ == '__main__':
    # H,W,K = sys.argv[1:]
    tmp = input()
    H,W,K = tmp.split()
    main5(int(H),int(W),int(K))

Submission status: Time Limit Exceeded

Solution code:
import sys
from itertools import permutations 
# import numpy as np

def calc(H,W,K):
    s = 0
    all_ele = [0] * H + [1] * W
    for perm in permutations(all_ele,K):
        s += each_calc(perm)
    print(s)
    return s

def each_calc(perm):
    s = 0
    nx = 1
    ny = 1
    for e in perm:
        if e==0:
            nx += 1
            s += nx*ny
            
        else:
            ny += 1
            s += ny*nx    
    return s

if __name__ == '__main__':
    # H,W,K = sys.argv[1:]
    tmp = input()
    H,W,K = tmp.split()
    calc(int(H),int(W),int(K))

Submission status: Time Limit Exceeded

Solution code:
h,w,k=map(int,input().split())
p,n=10**9+7,h+w
x=k+k*(k+1)//2+k*(k-1)*(k+1)//3*h*w*pow(n*(n-1),p-2,p)
for i in range(n,n-k,-1):x=x*i%p
print(x)

Submission status: Accepted

Solution code:
H,W,K=map(int,input().split());m,c=10**9+7,1;H+=W
for i in range(1,K):c=c*(H-i)%m;
v=pow(H-1,m-2,m);d=K*(K+1)//2;a=c*H*(d+K);a+=c*v*2*(H-W)*W*(K-1)*d//3;print(a%m)

Submission status: Accepted

Solution code:
H,W,K=map(int,input().split());m=10**9+7;c=1;H+=W
for i in range(H-1,H-K,-1):c=c*i %m;
v=pow(H-1,m-2,m);d=K*(K+1)//2;a=c*H*(d+K);d=(K-1)*d//3;a=(a+d*c*v*2*(H-W)*W)%m;print(a)

Submission status: Accepted

Solution code:
H,W,K=map(int,input().split());m=10**9+7;a,c=0,1;H+=W;mul=lambda x,y:(x*y)%m
for i in range(H-1,H-K,-1): c=c*i %m;
v=pow(H-1,m-2,m);temp1=mul(H,mul((K*(K+1)//2)%m,c));c=mul(c,v);u=((K*(K**2-1))//6)%m;temp2=mul(2*(H-W)*W,mul(u,c));c=mul(c,H-1);ans=mul(K,mul(H,c));ans=(ans+temp1+temp2)%m;print(ans)

Submission status: Accepted

Solution code:
mod=10**9+7
def mul(a,b):
    x,y=a,b
    return (x*y)%mod

H,W,K=map(int,input().split())
mod=10**9+7
ans=0
const=1
for i in range(H+W-1,H+W-K,-1):
    const=(const*i)%mod

inv=pow(H+W-1,mod-2,mod)
temp1=mul(H+W,mul((K*(K+1)//2)%mod,const))
const=mul(const,inv)
u=(K*(K**2-1))//6
u%=mod
temp2=mul(2*H*W,mul(u,const))
ans=(temp1+temp2)%mod
const=mul(const,H+W-1)
ans+=mul(K,mul(H+W,const))
ans%=mod
print(ans)

Submission status: Accepted

Solution code:
MOD = 10**9 + 7
list_size = 20000001

f_list = [1] * list_size
f_r_list = [1] * list_size

for i in range(list_size-1):
	f_list[i+1] = (f_list[i] * (i+1)) % MOD

f_r_list[-1] = pow(f_list[-1], MOD - 2, MOD)

for i in range(list_size-2, -1, -1):
	f_r_list[i] = (f_r_list[i+1] * (i+1)) % MOD

h, w, k = map(int, input().split())
ans = k * f_list[h+w] * f_r_list[h+w-k]
ans += (h+w) * k * (k+1) * f_list[h+w-1] * f_r_list[2] * f_r_list[h+w-k]
ans %= MOD
ans += h * w * f_list[h+w-2] * (k-1) * k * (k+1) * pow(3, MOD-2, MOD) * f_r_list[h+w-k]
ans %= MOD
print(ans)

Submission status: Accepted

Solution code:
k = 72
kk = k // 4
KK = 1<<k
nu = lambda L: int("".join([hex(KK+a)[3:] for a in L[::-1]]), 16)
st = lambda n: hex(n)[2:]
li = lambda s, l, r: [int(a, 16) % P if len(a) else 0 for a in [s[-(i+1)*kk:-i*kk] for i in range(l, r)]]

def grow(d, v, h):
    h += [0] * d
    f = [(-1 if (i+d) % 2 else 1) * fainv[i] * fainv[d-i] % P * h[i] % P for i in range(d+1)]
    nuf = nu(f)
    a = d * inv[v] % P
    t = [1] * (3*d+3)
    for i in range(1, 3*d+3): t[i] = t[i-1] * (a - d + i - 1) % P
    ti = [1] * (3*d+3)
    ti[-1] = pow(t[-1], P-2, P)
    for i in range(1, 3*d+3)[::-1]: ti[i-1] = ti[i] * (a - d + i - 1) % P
    iv = [1] * (3*d+3)
    for i in range(1, 3*d+3):
        iv[i] = ti[i] * t[i-1] % P

    ###
    g = [inv[i] for i in range(1, 2*d+2)]
    fg = li(st(nuf * nu(g)), d, d * 2 + 1)
    for i in range(d):
        h[i+d+1] = fg[i] * fa[d+i+1] % P * fainv[i] % P

    ###
    g = [iv[i] for i in range(1, 2*d+2)]
    fg = li(st(nuf * nu(g)), d, d * 2 + 1)
    for i in range(d+1):
        h[i] = h[i] * (fg[i] * t[d+i+1] % P * ti[i] % P) % P

    ###
    g = [iv[i] for i in range(d+2, 3*d+3)]
    fg = li(st(nuf * nu(g)), d, d * 2 + 1)
    for i in range(d):
        h[i+d+1] = h[i+d+1] * (fg[i] * t[2*d+i+2] % P * ti[d+i+1] % P) % P

    return h

# Create a table of the factorial of the first v+2 multiples of v, i.e., [0!, v!, 2v!, ..., (v(v+1))!]
def create_table(v):
    s = 1
    X = [1, v+1]
    while s < v:
        X = grow(s, v, X)
        s *= 2

    table = [1]
    for x in X:
        table.append(table[-1] * x % P)
    return table

def fact(i, table):
    a = table[i//v]
    for j in range(i//v*v+1, i+1):
        a = a * j % P
    return a

H, W, K = map(int, input().split())
N = H + W
P = 10**9+7

v = 1 << (N.bit_length() + 1) // 2
fa = [1] * (2*v+2)
fainv = [1] * (2*v+2)
for i in range(2*v+1):
    fa[i+1] = fa[i] * (i+1) % P
fainv[-1] = pow(fa[-1], P-2, P)
for i in range(2*v+1)[::-1]:
    fainv[i] = fainv[i+1] * (i+1) % P
inv = [0] * (2*v+2)
for i in range(1, 2*v+2):
    inv[i] = fainv[i] * fa[i-1] % P

T = create_table(v)

print((K*(K+3)//2 + K*(K+1)*(K-1)//3*H*W*pow(N * (N-1), P-2, P)) * fact(N, T) * pow(fact(N-K, T), P-2, P) % P)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

import numpy as np

MOD = 10**9 + 7

H,W,K = map(int,readline().split())

"""
・長方形ピースに対して右上のセルがどれであるかに注目
・各xに対してx回目の操作がそのセルについて加点対象になる確率を求めればよい
"""

def cumprod(arr,MOD):
    L = len(arr); Lsq = int(L**.5+1)
    arr = np.resize(arr,Lsq**2).reshape(Lsq,Lsq)
    for n in range(1,Lsq):
        arr[:,n] *= arr[:,n-1]; arr[:,n] %= MOD
    for n in range(1,Lsq):
        arr[n] *= arr[n-1,-1]; arr[n] %= MOD
    return arr.ravel()[:L]

p1 = K
p2 = (K*(K+1)//2)
p3 = ((K-1)*K*(K+1)//3) * H*W * pow((H+W)*(H+W-1),MOD-2,MOD)
p = (p1 + p2 + p3) % MOD

x = np.arange(H+W,H+W-K,-1,dtype=np.int64)
answer = p * cumprod(x,MOD)[-1] % MOD
print(answer)

Submission status: Accepted

Solution code:
H,W,K=map(int,input().split())
P,N=10**9+7,H+W
x=K*(K+3)//2+(K**3-K)//3*H*W*pow(N*N-N,P-2,P)
for i in range(K):x=x*(N-i)%P
print(x)

Submission status: Accepted

Solution code:
def solve(h, w, k):
    n = h + w
    MOD = 10 ** 9 + 7

    if k == 1:
        return 2 * n

    ans = 0
    # (0, 0) ... k * nPk * 1
    ans += k * n * (n - 1) % MOD
    # (i, 0) (0, j) ... sum(t for t=1..k) * (n-1)P(k-1) * (h+w)
    tmp = k * (k + 1) // 2 * (n - 1) % MOD
    ans += tmp * n % MOD
    # (i, j) ... sum((t-1)(k-t+1) for t=1..k) * (n-2)P(k-2) * 2 * h*w
    #            ~~~~~~~~~~~~~~~~~~~~~~~~~~~~ = (k-1)k(k+1)/6
    tmp = (k - 1) * k * (k + 1) // 3 % MOD
    ans += tmp * h * w % MOD

    for m in range(n - 2, n - k, -1):
        ans = ans * m % MOD
    return ans % MOD


h, w, k = map(int, input().split())
print(solve(h, w, k))

Submission status: Accepted

Solution code:
H, W, K = map(int, input().split())
P = 10**9 + 7
x = K + K*(K+1)//2 + K*(K+1)*(K-1)//3*H*W*pow((H+W)*(H+W-1),P-2,P)
for i in range(H+W, H+W-K, -1):
    x *= i
    x %= P
print(x)

Submission status: Runtime Error

Solution code:
mod = int(1e9) + 7 # <-- input modulo
maxf = 10000100           # <-- input factional limitation

def make_fact(n, k):
    tmp = n
    perm = [i for i in range(k)]
    L = [0 for _ in range(k)]
    for i in range(k):
        L[i] = tmp % (i + 1)
        tmp //= i + 1
    LL = [0 for _ in range(k)]
    for i in range(k):
        LL[i] = perm[L[-i-1]]
        for j in range(L[-i-1]+1, k):
            perm[j-1] = perm[j]
    return LL

def doubling(n, m, modulo=mod):
    y = 1
    base = n
    tmp = m
    while tmp != 0:
        if tmp % 2 == 1:
            y *= base
            if modulo > 0:
                y %= modulo
        base *= base
        if modulo > 0:
            base %= modulo
        tmp //= 2
    return y

def inved(a, modulo=mod):
    x, y, u, v, k, l = 1, 0, 0, 1, a, modulo
    while l != 0:
        x, y, u, v = u, v, x - u * (k // l), y - v * (k // l)
        k, l = l, k % l
    return x % modulo

fact = [1 for _ in range(maxf+1)]
invf = [1 for _ in range(maxf+1)]

for i in range(maxf):
    fact[i+1] = (fact[i] * (i+1)) % mod
invf[-1] = inved(fact[-1])
for i in range(maxf, 0, -1):
    invf[i-1] = (invf[i] * i) % mod

def comb(n, k):
  return fact[n] * invf[n-k] * invf[k] % mod
H, W, K = map(int, input().split())
S = (((K+1)*(K+2)*(2*K+3))//6 - H*(K+1)*(K+2)//2 + H - 1 + K*(W+1))*comb(H+W-2, H-1)%mod
if H >= 2:
  S += (W+1)*((K+1)*(K+2)//2-1)*comb(H+W-2, H-2)
if W >= 2:
  S += (K*(K+1)//2-K*(H-1))*comb(H+W-2, H)
print(S*invf[H+W-K]*fact[H]*fact[W]%mod)

Submission status: Runtime Error

Solution code:
N = list(map(int,input().split()))
list0_9 = [0 for i in range(10)]
for i in N:
  list0_9[i]+=1
if list0_9[1] == list0_9[2] == list0_9[7] == list0_9[9] == 1:
  print("YES")
else:
  print("NO")

Submission status: Runtime Error

Solution code:
def PaperCutting(H,W,K):
    nodes = [[0 for w in range(W+1)] for h in range(H+1) ]#np.zeros([H+1,W+1],dtype=int)
    pathes = [[0 for w in range(W+1)] for h in range(H+1) ]#np.zeros([H+1,W+1],dtype=int)
    pathes[0][0]=1
    scores = [[(h+1)*(w+1) for w in range(W+1)] for h in range(H+1) ]
    depth = 1
    while depth <= K:
        for h in range(min(depth,H)+1):
            w = depth-h
            if w <= W:
                ph = (pathes[h-1][w] if h-1 >= 0 else 0) % (10**9+7)
                pw = (pathes[h][w-1] if w-1 >= 0 else 0 ) % (10**9+7)
                pathes[h][w] = ph* (H-h+1) + pw* (W-w+1) 
                nodes[h][w] = (nodes[h-1][w] + scores[h][w] * ph) * (H-h+1)  + (nodes[h][w-1] + scores[h][w] * pw) * (W-w+1)
                nodes[h][w] = nodes[h][w] % (10**9+7)
        depth += 1 
    print( int(sum([nodes[h][K-h]  for h in range(K+1) if h<=H and K-h<=W])  % (10**9+7)) )
    
if __name__ == '__main__':
    tmp = input()
    H,W,K = tmp.split()
    PaperCutting(int(H),int(W),int(K))

Submission status: Runtime Error

Solution code:
import numpy as np
def PaperCutting(H,W,K):
    nodes = [[0 for w in range(W+1)] for h in range(H+1) ]#np.zeros([H+1,W+1],dtype=int)
    pathes = [[0 for w in range(W+1)] for h in range(H+1) ]#np.zeros([H+1,W+1],dtype=int)
    pathes[0][0]=1
    scores = [[(h+1)*(w+1) for w in range(W+1)] for h in range(H+1) ]
    depth = 1
    while depth <= K:
        for h in range(min(depth,H)+1):
            w = depth-h
            if w <= W:
                ph = (pathes[h-1][w] if h-1 >= 0 else 0) % (10**9+7)
                pw = (pathes[h][w-1] if w-1 >= 0 else 0 ) % (10**9+7)
                pathes[h][w] = ph* (H-h+1) + pw* (W-w+1) 
                nodes[h][w] = (nodes[h-1][w] + scores[h][w] * ph) * (H-h+1)  + (nodes[h][w-1] + scores[h][w] * pw) * (W-w+1)
                nodes[h][w] = nodes[h][w] % (10**9+7)
        depth += 1 
    print( int(sum([nodes[h][K-h]  for h in range(K+1) if h<=H and K-h<=W])  % (10**9+7)) )
    
if __name__ == '__main__':
    tmp = input()
    H,W,K = tmp.split()
    PaperCutting(int(H),int(W),int(K))

Submission status: Runtime Error

Solution code:
import numpy as np
def PaperCutting(H,W,K):
    nodes = np.zeros([H+1,W+1],dtype=int)
    pathes = np.zeros([H+1,W+1],dtype=int)
    pathes[0][0]=1
    scores = [[(h+1)*(w+1) for w in range(W+1)] for h in range(H+1) ]
    depth = 1
    while depth <= K:
        for h in range(min(depth,H)+1):
            w = depth-h
            if w <= W:
                ph = (pathes[h-1][w] if h-1 >= 0 else 0) % (10**9+7)
                pw = (pathes[h][w-1] if w-1 >= 0 else 0 ) % (10**9+7)
                pathes[h][w] = ph* (H-h+1) + pw* (W-w+1) 
                nodes[h][w] = (nodes[h-1][w] + scores[h][w] * ph) * (H-h+1)  + (nodes[h][w-1] + scores[h][w] * pw) * (W-w+1)
                nodes[h][w] = nodes[h][w] % (10**9+7)
        depth += 1 
    print( int(sum([nodes[h][K-h]  for h in range(K+1) if h<=H and K-h<=W])  % (10**9+7)) )
    
if __name__ == '__main__':
    tmp = input()
    H,W,K = tmp.split()
    PaperCutting(int(H),int(W),int(K))

Submission status: Runtime Error

Solution code:
from collections import defaultdict
import numpy as np
def PaperCutting(H,W,K):
    nodes = np.zeros([H+1,W+1],dtype=int)
    pathes = np.zeros([H+1,W+1],dtype=int)
    pathes[0][0]=1
    scores = [[(h+1)*(w+1) for w in range(W+1)] for h in range(H+1) ]
    depth = 1
    while depth <= K:
        for h in range(min(depth,H)+1):
            w = depth-h
            if w <= W:
                ph = (pathes[h-1][w] if h-1 >= 0 else 0) % (10**9+7)
                pw = (pathes[h][w-1] if w-1 >= 0 else 0 ) % (10**9+7)
                pathes[h][w] = ph* (H-h+1) + pw* (W-w+1) 
                nodes[h][w] = (nodes[h-1][w] + scores[h][w] * ph) * (H-h+1)  + (nodes[h][w-1] + scores[h][w] * pw) * (W-w+1)
                nodes[h][w] = nodes[h][w] % (10**9+7)
        depth += 1 
    print( int(sum([nodes[h][K-h]  for h in range(K+1) if h<=H and K-h<=W])  % (10**9+7)) )
    
if __name__ == '__main__':
    tmp = input()
    H,W,K = tmp.split()
    PaperCutting(int(H),int(W),int(K))

Submission status: Runtime Error

Solution code:
from collections import defaultdict
import numpy as np
def PaperCutting(H,W,K):
    nodes = np.zeros([H+1,W+1],dtype=int)
    pathes = np.zeros([H+1,W+1],dtype=int)
    pathes[0][0]=1
    scores = [[(h+1)*(w+1) for w in range(W+1)] for h in range(H+1) ]
    depth = 1
    while depth <= K:
        for h in range(min(depth,H)+1):
            w = depth-h
            if w <= W:
                ph = (pathes[h-1][w] if h-1 >= 0 else 0) % (10**9+7)
                pw = (pathes[h][w-1] if w-1 >= 0 else 0 ) % (10**9+7)
                pathes[h][w] = ph* (H-h+1) + pw* (W-w+1) 
                nodes[h][w] = (nodes[h-1][w] + scores[h][w] * ph) * (H-h+1)  + (nodes[h][w-1] + scores[h][w] * pw) * (W-w+1)
                nodes[h][w] = nodes[h][w] % (10**9+7)
        depth += 1 
    print( int(sum([nodes[h][K-h]  for h in range(K+1) if h<=H and K-h<=W])  % (10**9+7)) )
    
if __name__ == '__main__':
    tmp = input()
    H,W,K = tmp.split()
    main5(int(H),int(W),int(K))
    PaperCutting(int(H),int(W),int(K))

Submission status: Runtime Error

Solution code:
import sys
from collections import defaultdict
def calc5(all_nodes,H,W,K):
    for _ in range(K):
        next_nodes = defaultdict(int)
        for k,v in all_nodes.items():
            if k[0]+1 <= H+1:
                k0 = k[0]+1
                s = ((k0)*k[1]+k[2] )
                next_nodes[(k0,k[1],s) ] += v * (H+1-k[0])
            if k[1]+1 <= W+1:
                k1 = k[1]+1
                s = ((k1)*k[0]+k[2] )
                next_nodes[(k[0],k1,s) ] += v* (W+1-k[1])
                    
        all_nodes = next_nodes
    print( sum([ k[2]*v for k,v in all_nodes.items()])%(10**9+7) )
    
def main5(H,W,K):
    all_nodes = {}
    all_nodes[(1,1,0)] = 1
    calc5(all_nodes,H,W,K)
    
if __name__ == '__main__':
    # H,W,K = sys.argv[1:]
    tmp = input()
    #tmp = "30 40 50"
    H,W,K = tmp.split()
    main5(int(H),int(W),int(K))

Submission status: Runtime Error

Solution code:
import sys
from collections import defaultdict
def calc5(all_nodes,H,W,K):
    for _ in range(K):
        next_nodes = defaultdict(int)
        for k,v in all_nodes.items():
            if k[0]+1 <= H+1:
                k0 = k[0]+1
                s = ((k0)*k[1]+k[2] )
                next_nodes[(k0,k[1],s) ] += v * (H+1-k[0])
            if k[1]+1 <= W+1:
                k1 = k[1]+1
                s = ((k1)*k[0]+k[2] )
                next_nodes[(k[0],k1,s) ] += v* (W+1-k[1])
                    
        all_nodes = next_nodes
    print( sum([ k[2]*v for k,v in all_nodes.items()])%(10**9+7) )
    
def main5(H,W,K):
    all_nodes = {}
    all_nodes[(1,1,0)] = 1
    calc5(all_nodes,H,W,K)
    
if __name__ == '__main__':
    # H,W,K = sys.argv[1:]
	tmp = input()
    H,W,K = tmp.split()
    main5(int(H),int(W),int(K))

Submission status: Runtime Error

Solution code:
import sys
from collections import defaultdict
def calc5(all_nodes,H,W,K):
    for _ in range(K):
        next_nodes = defaultdict(int)
        for k,v in all_nodes.items():
            if k[0]+1 <= H+1:
                k0 = k[0]+1
                s = ((k0)*k[1]+k[2] )
                next_nodes[(k0,k[1],s) ] += v * (H+1-k[0])
            if k[1]+1 <= W+1:
                k1 = k[1]+1
                s = ((k1)*k[0]+k[2] )
                next_nodes[(k[0],k1,s) ] += v* (W+1-k[1])
                    
        all_nodes = next_nodes
    print( sum([ k[2]*v for k,v in all_nodes.items()])%(10**9+7) )
    
def main5(H,W,K):
    all_nodes = {}
    all_nodes[(1,1,0)] = 1
    calc5(all_nodes,H,W,K)
    
if __name__ == '__main__':
    # H,W,K = sys.argv[1:]
	tmp = input()
    #tmp = "30 40 50"
    H,W,K = tmp.split()
    main5(int(H),int(W),int(K))

Submission status: Runtime Error

Solution code:
import sys
 
def calc5(all_nodes,H,W,K):
    for _ in range(K):
        next_nodes = dict()
        for k,v in all_nodes.items():
            if k[0]+1 <= H+1:
                k0 = k[0]+1
                s = ((k0)*k[1]+k[2] )
                if (k0,k[1],s) in next_nodes:
                    next_nodes[(k0,k[1],s) ] += v * (H+1-k[0])
                else:
                    next_nodes[(k0,k[1],s) ] = v * (H+1-k[0])
            if k[1]+1 <= W+1:
                k1 = k[1]+1
                s = ((k1)*k[0]+k[2] )
                if (k[0],k1,s) in next_nodes:
                    next_nodes[(k[0],k1,s) ] += v* (W+1-k[1])
                else:
                    next_nodes[(k[0],k1,s) ] = v* (W+1-k[1])
                    
        all_nodes = next_nodes
    print( sum([ k[2]*v for k,v in all_nodes.items()])%(10**9+7) )
 
def main5(H,W,K):
    all_nodes = {}
    all_nodes[(1,1,0)] = 1
    calc5(all_nodes,H,W,K)
    
if __name__ == '__main__':
    # H,W,K = sys.argv[1:]
    tmp = input()
    H,W,K = tmp.split()
    main5(int(H),int(W),int(K))
import sys

Submission status: Runtime Error

Solution code:
MOD = 10**9 + 7
list_size = 200001

f_list = [1] * list_size
f_r_list = [1] * list_size

for i in range(list_size-1):
	f_list[i+1] = (f_list[i] * (i+1)) % MOD

f_r_list[-1] = pow(f_list[-1], MOD - 2, MOD)

for i in range(list_size-2, -1, -1):
	f_r_list[i] = (f_r_list[i+1] * (i+1)) % MOD

h, w, k = map(int, input().split())
ans = k * f_list[h+w] * f_r_list[h+w-k]
ans += (h+w) * k * (k+1) * f_list[h+w-1] * f_r_list[2] * f_r_list[h+w-k]
ans %= MOD
ans += h * w * f_list[h+w-2] * (k-1) * k * (k+1) * pow(3, MOD-2, MOD) * f_r_list[h+w-k]
ans %= MOD
print(ans)

Submission status: Runtime Error

Solution code:
import sys
from itertools import permutations 
# import numpy as np

def calc(H,W,K):
    s = 0
    all_ele = [0] * H + [1] * W
    for perm in permutations(all_ele,K):
        s += each_calc(perm)
    print(s)
    return s

def each_calc(perm):
    s = 0
    nx = 1
    ny = 1
    for e in perm:
        if e==0:
            nx += 1
            s += nx*ny
            
        else:
            ny += 1
            s += ny*nx    
    return s

if __name__ == '__main__':
    # H,W,K = sys.argv[1:]
    H,W,K = sys.stdin
    calc(int(H),int(W),int(K))

Submission status: Runtime Error

Solution code:
import sys
from itertools import permutations 
# import numpy as np

def calc(H,W,K):
    s = 0
    all_ele = [0] * H + [1] * W
    for perm in permutations(all_ele,K):
        s += each_calc(perm)
    print(s)
    return s

def each_calc(perm):
    s = 0
    nx = 1
    ny = 1
    for e in perm:
        if e==0:
            nx += 1
            s += nx*ny
            
        else:
            ny += 1
            s += ny*nx    
    return s

if __name__ == '__main__':
    H,W,K = sys.argv[1:]
    calc(int(H),int(W),int(K))

Submission status: Runtime Error

Solution code:
import sys
from itertools import permutations 
# import numpy as np

def calc(H,W,K):
	s = 0
	all_ele = [0] * H + [1] * W
	for perm in permutations(all_ele,K):
		s += each_calc(perm)
	print(s)
    return s

def each_calc(perm):
	s = 0
	nx = 1
	ny = 1
	for e in perm:
		if e==0:
			s += ny
			nx += 1
		else:
			s += nx
			ny += 1
	return s


if __name__ == '__main__':
    H,W,K = sys.args[1:]