Problem:


Score : 500 points

Problem Statement

We have a grid of squares with N rows and M columns. Let (i, j) denote the square at the i-th row from the top and j-th column from the left. We will choose K of the squares and put a piece on each of them.

If we place the K pieces on squares (x_1, y_1), (x_2, y_2), ..., and (x_K, y_K), the cost of this arrangement is computed as:

\sum_{i=1}^{K-1} \sum_{j=i+1}^K (|x_i - x_j| + |y_i - y_j|)

Find the sum of the costs of all possible arrangements of the pieces. Since this value can be tremendous, print it modulo 10^9+7.

We consider two arrangements of the pieces different if and only if there is a square that contains a piece in one of the arrangements but not in the other.

Constraints

2 \leq N \times M \leq 2 \times 10^5

2 \leq K \leq N \times M

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M K

Output

Print the sum of the costs of all possible arrangements of the pieces, modulo 10^9+7.

Sample Input 1

2 2 2

Sample Output 1

8

There are six possible arrangements of the pieces, as follows:

((1,1),(1,2)), with the cost |1-1|+|1-2| = 1

((1,1),(2,1)), with the cost |1-2|+|1-1| = 1

((1,1),(2,2)), with the cost |1-2|+|1-2| = 2

((1,2),(2,1)), with the cost |1-2|+|2-1| = 2

((1,2),(2,2)), with the cost |1-2|+|2-2| = 1

((2,1),(2,2)), with the cost |2-2|+|1-2| = 1

The sum of these costs is 8.

Sample Input 2

4 5 4

Sample Output 2

87210

Sample Input 3

100 100 5000

Sample Output 3

817260251

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



Sample input:
2 2 2


Sample output:
8

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())


H,W,K = inpl()

MAX = H*W+5
fac = [1]*(MAX+1)
for i in range(1,MAX+1):
	fac[i] = (fac[i-1]*i)%mod

gyakugen = [1]*(MAX+1)
gyakugen[MAX] = pow(fac[MAX],mod-2,mod)
for i in range(MAX,0,-1):
	gyakugen[i-1] = (gyakugen[i]*i)%mod

def Comb(n,k):#nCk
	return (fac[n]*gyakugen[k]*gyakugen[n-k])%mod

ans = 0
ruiseki = [0]
tmp = 0
for i in range(1,max(H,W)+5):
    tmp += i
    ruiseki.append(tmp)

for y in range(H):
    ans += (ruiseki[y] + ruiseki[H-y-1])*W*W

for x in range(W):
    ans += (ruiseki[x] + ruiseki[W-x-1])*H*H

ans //= 2
ans *= Comb(H*W-2,K-2)

print(ans%mod)

Submission status: Accepted

Solution code:
N, M, K = map(int, input().split())
P = 10**9+7
fact = [1]
for i in range(N*M):
    fact.append(fact[-1]*(i+1)%P)
def inv(n):
    return pow(n, P-2, P)
def C(a, b):
    return fact[a]*inv(fact[a-b]*fact[b])%P
print((M**2*(N**3-N)+N**2*(M**3-M))//6*C(M*N-2, K-2)%P)

Submission status: Accepted

Solution code:
n, m, k = list(map(int, input().split()))
MOD = 10 ** 9 + 7

t = 0
pre = [0]
for i in range(1, max(n, m) + 1):
    t += i
    pre.append(t)


def calc_base(n, m, pre):
    base = 0
    for i in range(n // 2):
        base = base + (pre[i] + pre[n - i - 1]) * 2 % MOD
    if n % 2 == 1:
        i = n // 2
        base = (base + pre[i] * 2) % MOD
    return base * m * m % MOD


bi = calc_base(n, m, pre)
bj = calc_base(m, n, pre)


def prepare(n, MOD):
    f = 1
    for m in range(1, n + 1):
        f *= m
        f %= MOD
    fn = f

    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv

    return fn, invs


nm = n * m - 2
f, inv = prepare(nm, MOD)
print((bi + bj) * f * inv[k - 2] % MOD * inv[nm - k + 2] * inv[2] % MOD)

Submission status: Accepted

Solution code:
Mod = 10**9 + 7

n,m,k = map(int,input().split())

inv = [0]*(k+3)
inv[1] = 1
for i in range(2,k+2):
  # print(i)
  inv[i] = ((Mod-Mod//i) * inv[Mod%i]) % Mod


s = (n*n*(m+1)*m*(m-1) + m*m*(n+1)*n*(n-1))//6
for i in range(k-2):
   s = (s*(n*m-2-i)*inv[i+1])%Mod
print(s)

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin

mod = 1000000007

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n, m, k = na()

def invl(a, mod):
    b = mod
    p = 1; q = 0
    while b > 0:
        c = a // b
        a, b = b, a%b
        p, q = q, p-c*q
    return p + mod if p < 0 else p

num = 1
den = 1
for u in range(k-2):
    num = num * (n*m-2-u) % mod
for u in range(k-2):
    den = den * (1+u) % mod
C = num * invl(den, mod) % mod

# 10 7 6 7 10
# i i-1 .. 0 .. n-1-i
# sum_i (i*(i+1)//2 + (n-1-i)*(n-i)//2)*m
# n*(n+1)*(n+2)//6*2*m

v = n*(n+1)*(n-1)//3*m*m + m*(m+1)*(m-1)//3*n*n
v *= C
print(v*invl(2,mod)%mod)

Submission status: Accepted

Solution code:
from collections import defaultdict as ddic, deque, Counter
from itertools import permutations, combinations, product
import bisect, heapq

rr = raw_input
rri = lambda: int(raw_input())
rrm = lambda: map(int, raw_input().split())
MOD = 10**9 + 7

def binom(n, k):
    numer = 1
    for i in xrange(1, n+1):
        numer *= i
        numer %= MOD
    denom = 1
    for i in xrange(1, k+1):
        denom *= i
        denom %= MOD
    denom2 = 1
    for i in xrange(1, n-k+1):
        denom2 *= i
        denom2 %= MOD
    ans = numer * pow(denom, MOD-2, MOD) % MOD
    ans *= pow(denom2, MOD-2, MOD)
    ans %= MOD
    return ans

def sumToN(N):
    return N*(N+1)/2

def flat(R, C):
    if C > R: R,C = C,R
    # R >= C
    # 0 1 2 3 4 5 6 7 8 [C=9]
    # 3 2 1 0 1 2 3 4 5
    ans = 0
    for c in xrange(C):
        left = c
        right = C - 1 - c
        base = sumToN(left) + sumToN(right)
        for r in xrange(R):
            up, down = r, R-1-r
            base2 = sumToN(up) + sumToN(down)
            ans += base * R + base2 * C
    ans /= 2
    return ans % MOD


def solve(R, C, K):
    N = R * C
    return flat(R, C) * binom(N - 2, K - 2) % MOD

print solve(*rrm())

Submission status: Accepted

Solution code:
MOD = 10**9 + 7

N,M,K = map(int,input().split())
NM = N*M

U = 2*10**5
fact = [1] * (U+1)
fact_inv = [1] * (U+1)

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

def comb(n,k):
  x = fact[n]
  x *= pow(fact[n-k],MOD-2,MOD)
  x %= MOD
  x *= pow(fact[k],MOD-2,MOD)
  x %= MOD
  return x

def F(N):
  # sum_x,y abs(x-y)
  x = N*(N+1)//2*N
  y = N*(N+1)*(2*N+1)//6
  return (x-y)%MOD

MM = M*M%MOD
NN = N*N%MOD
answer = MM*F(N)%MOD + NN*F(M)%MOD
answer %= MOD
answer *= comb(N*M-2,K-2)
answer %= MOD
print(answer)

Submission status: Runtime Error

Solution code:
mod = 10 ** 9 + 7
class nCr():
    def __init__(self, n):
        self.n = n
        self.fa = [1] * (self.n + 1)
        self.fi = [1] * (self.n + 1)
        for i in range(1, self.n + 1):
            self.fa[i] = self.fa[i - 1] * i % mod
            self.fi[i] = pow(self.fa[i], mod - 2, mod)
    def comb(self, n, r):
        if n < r:return 0
        if n < 0 or r < 0:return 0
        return self.fa[n] * self.fi[r] % mod * self.fi[n - r] % mod
n, m, k = map(int, input().split())
ans = 0
c = nCr(n + m)
for i in range(n):
    ans += i * (n - i) * m * m
    ans %= mod
for i in range(m):
    ans += i * (m - i) * n * n
    ans %= mod
print(ans * c.comb(n * m - 2, k - 2) % mod)

Submission status: Runtime Error

Solution code:
n, m, k = map(int, input().split())

mod = 10**9+7
N = 10**5+50
fac = [1]*(N+1)
finv = [1]*(N+1)
for i in range(N):
    fac[i+1] = fac[i] * (i+1) % mod
finv[-1] = pow(fac[-1], mod-2, mod)
for i in reversed(range(N)):
    finv[i] = finv[i+1] * (i+1) % mod

def cmb1(n, r, mod):
    if r <0 or r > n:
        return 0
    r = min(r, n-r)
    return fac[n] * finv[r] * finv[n-r] % mod

ans = 0
for i in range(n*m):
    x, y = divmod(i, m)
    # x
    ans += x*m*cmb1(n*m-2, k-2, mod)*x
    ans -= (n-1-x)*m*cmb1(n*m-2, k-2, mod)*x
    # y
    ans += y*n*cmb1(n*m-2, k-2, mod)*y
    ans -= (m-1-y)*n*cmb1(n*m-2, k-2, mod)*y

ans %= mod
print(ans)

Submission status: Runtime Error

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
from collections import Counter
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())

N, M, K = map(int, input().split())
MAX = 10 ** 5
MOD = 10 ** 9 + 7

fac = [0 for i in range(MAX)]
finv = [0 for i in range(MAX)]
inv = [0 for i in range(MAX)]

def comInit(mod):
    fac[0], fac[1] = 1, 1
    finv[0], finv[1] = 1, 1
    inv[1] = 1
    for i in range(2, MAX):
        fac[i] = fac[i - 1] * i % mod
        inv[i] = mod - inv[mod % i] * (mod // i) % mod
        finv[i] = finv[i - 1] * inv[i] % mod


def com(n, r, mod):
    if n < r:
        return 0
    if n < 0 or r < 0:
        return 0
    return fac[n] * (finv[r] * finv[n - r] % mod) % mod

def p(n, r, mod):
    return fac[n] * finv[n - r] % mod
comInit(MOD)

xs = 0
for i in range(M):
    xs += i * (M - i)
    xs %= MOD
xs *= N ** 2
ys = 0
for i in range(N):
    ys += i * (N - i)
    ys %= MOD
ys *= M ** 2
ys %= MOD
print(((xs + ys) % MOD) * com(N * M - 2, K - 2, MOD) % MOD)

Submission status: Runtime Error

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def comb_mod(n, r):
    res = 1
    r = min(n - r, r)

    for i in range(r):
        res *= (n - i)
        res %= MOD
        res *= pow((r - i), -1, MOD)

    return res


def main():
    n, m, k = list(map(int, readline().split()))

    com = comb_mod(n * m - 2, k - 2)
    x = 0
    y = 0

    for i in range(n):
        right = n - 1 - i
        x += (right + 1) * right // 2
        x %= MOD

    for i in range(m):
        down = m - 1 - i
        y += (down + 1) * down // 2
        y %= MOD

    ans = 0
    ans += m ** 2 * x * com
    ans += n ** 2 * y * com
    ans %= MOD

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from itertools import accumulate, combinations, permutations, product
from math import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

n,m,k=map(int,input().split())

# MOD combination
def cmb(n, r, mod=10**9+7):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

N = 2*10**5+10
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 )

ans=0
for i in range(n):
    ans+=i*(n-i)*m*m*cmb(n*m-2,k-2)
    ans%=mod

n,m=m,n
for i in range(n):
    ans+=i*(n-i)*m*m*cmb(n*m-2,k-2)
    ans%=mod

print(ans)

Submission status: Runtime Error

Solution code:
MOD = 10**9 + 7
N = 10**5 + 10

fact = [1]*(N+1)
rfact = [1]*(N+1)
r = 1
for i in range(1, N+1):
  fact[i] = r = r * i % MOD
rfact[N] = r = pow(fact[N], MOD-2, MOD)
for i in range(N, 0, -1):
  rfact[i-1] = r = r * i % MOD

# nPk (mod MOD) を求める
def perm(n, k):
  return fact[n] * rfact[n-k] % MOD

# nCk (mod MOD) を求める
def comb(n, k):
  return fact[n] * rfact[k] * rfact[n-k] % MOD

n,m,k = map(int,input().split())

p = comb(n*m-2, k-2)

ans = 0
for i in range(1,n):
    ans += i * (n-i) * m * m * p
    ans %= MOD

for i in range(1,m):
    ans += i * (m-i) * n * n * p
    ans %= MOD

print(ans)

Submission status: Runtime Error

Solution code:
MOD = 10**9 + 7
N = 10**5 + 1

fact = [1]*(N+1)
rfact = [1]*(N+1)
r = 1
for i in range(1, N+1):
  fact[i] = r = r * i % MOD
rfact[N] = r = pow(fact[N], MOD-2, MOD)
for i in range(N, 0, -1):
  rfact[i-1] = r = r * i % MOD

# nPk (mod MOD) を求める
def perm(n, k):
  return fact[n] * rfact[n-k] % MOD

# nCk (mod MOD) を求める
def comb(n, k):
  return fact[n] * rfact[k] * rfact[n-k] % MOD

n,m,k = map(int,input().split())

p = comb(n*m-2, k-2)

ans = 0
for i in range(1,n):
    ans += i * (n-i) * m * m * p
    ans %= MOD

for i in range(1,m):
    ans += i * (m-i) * n * n * p
    ans %= MOD

print(ans)

Submission status: Runtime Error

Solution code:
nCr = {}
def cmb(n, r):
    if r == 0 or r == n: return 1
    if r == 1: return n
    if (n,r) in nCr: return nCr[(n,r)]
    nCr[(n,r)] = cmb(n-1,r) + cmb(n-1,r-1)
    return nCr[(n,r)]

N,M,K = list(map(int, input().split()))

print(cmb(N*M-2,K-2)*M*N*(M*(N**2-1)+N*(M**2-1))//6%1000000007)

Submission status: Runtime Error

Solution code:
from scipy.special import comb
N,M,K = list(map(int, input().split()))

print(comb(N*M-2,K-2,exact=True)*M*N*(M*(N**2-1)+N*(M**2-1))//6%1000000007)

Submission status: Runtime Error

Solution code:
import math
n,m,k = map(int,input().split())
mod = 10**9+7
memo = {}
def factorial(num):
    if num == 0:
        return 1
    if not num in memo:
        memo[num] = num*factorial(num-1)
    return memo[num]

temp = math.factorial(n*m-2)//(math.factorial(k-2)*math.factorial(n*m-4-k))
ans = 0
for d in range(1,n):
    ans += d*((n-d)*(m**2))*temp
for d in range(1,m):
    ans += d*((m-d)*(n**2))*temp
print(ans%mod)

Submission status: Runtime Error

Solution code:
n,m,k = map(int,input().split())
mod = 10**9+7
memo = {}
def factorial(num):
    if num == 0:
        return 1
    if not num in memo:
        memo[num] = num*factorial(num-1)
    return memo[num]

temp = factorial(n*m-2)//(factorial(k-2)*factorial(n*m-k))
ans = 0
for d in range(1,n):
    ans += d*((n-d)*(m**2))*temp
for d in range(1,m):
    ans += d*((m-d)*(n**2))*temp
print(ans%mod)

Submission status: Runtime Error

Solution code:

##mod,nについての制約は自分でいかに記入する

def find_power(n,mod):
    # 0!からn!までのびっくりを出してくれる関数(ただし、modで割った値に対してである）
    powlist=[0]*(n+1)
    powlist[0]=1
    powlist[1]=1
    for i in range(2,n+1):
        powlist[i]=powlist[i-1]*i%(mod)
    return powlist
 #あるかずxのn乗をmodで割ったあまりを返す関数pow_cal(x,n,mod)
def pow_cal(x,n,mod):
    if n==0:
         return 1
    elif n==1:
         return x%mod
    elif n>=2:
        if n%2==0:
             return (pow_cal(x,n//2,mod)**2)%mod
        else:
             return (x*pow_cal(x,n//2,mod)**2)%mod

def find_inv_power(n,mod):
    #0!からn!までの逆元を素数modで割ったあまりリストを作る関数
    c=1
    uselist=[0 for i in range(n+1)]
    for i in range(1,n+1):
        c*=i
        c%=mod
    first=pow_cal(c,mod-2,mod)
    uselist[n]=first
    for i in range(n,0,-1):
        uselist[i-1]=(uselist[i]*i)%(mod)
    return uselist
    
A=find_power(4*10**5,mod)
B=find_inv_power(4*10**5,mod)

def combi(n,r,mod):
    if n<r:
        return 0
    elif n>=r:
        return (A[n]*B[r]*B[n-r])%(mod)

    
M,N,K=map(int,input().split())
ans=M*N*(M+N)*(M*N-1)//6
mod=10**9+7
print(ans*combi(M*N-2,K-2,mod)%mod)

Submission status: Runtime Error

Solution code:
from scipy.special import comb
N, M, K = map(int, input().split())

ans = 0

for i in range(1, M):
    ans += i * (M-i) * N**2 
for i in range(1, N):
    ans += i * (N-i) * M**2

ans *= comb(N*M-2, K-2, exact=True)

print(int(ans % (10**9+7)))