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: Wrong Answer

Solution code:
"""
基本の方針は「各マンハッタン距離が何回足されるか」という考え方で距離の値を積み上げて行けばよい

まず、XとYは独立に考えることにする。
X軸の距離の方から積み上げる。
X1とX2の距離が足される回数は、
A.X1の列とX2の列の座標の組み合わせの数　×　B.その組み合わせが含まれるような座標の組み合わせの数
である。
A　＝　行数**２
B　＝　CMB(N*M-2 , K-2)である

同様の計算をY軸に関しても行えばよい。
"""
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 10 ** 9 + 7
N = 10 ** 6  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用
 
for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

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

ans = 0

#X軸の距離を考える
A = N*N
B = cmb(N*M-2,K-2,p)
for i in range(1,N):
    ans += ((i*i)-(i-1+0)*i//2)*A*B%p
    ans %= p

#Y軸の距離を考える
A = M*M
B = cmb(N*M-2,K-2,p)
for i in range(1,M):
    ans += ((i*i)-(i-1+0)*i//2)*A*B%p
    ans %= p

print(ans)

Submission status: Wrong Answer

Solution code:
N,M,K=map(int,input().split())
P=1000000007
f=[0]*(N*M+1)
f[0]=1
for i in range(N*M):
    f[i+1]=(i+1)*f[i]%P
ans=0
for A in [N,M]:
    for i in range(1,A):
        ans = (ans+(N^M^A)**2*i*(i+1)//2)%P
print(ans*f[N*M-2]*pow(f[K-2],P-2,P)*pow(f[N-K],P-2,P)%P)

Submission status: Wrong Answer

Solution code:
class Combination:
    def __init__(self, n_max=10**6, mod=10**9+7):
        # self._n_max = n_max
        self._fac, self._finv, self._inv = [0]*n_max, [0]*n_max, [0]*n_max
        self._fac[0], self._fac[1] = 1, 1
        self._finv[0], self._finv[1] = 1, 1
        self._inv[1] = 1
        for i in range(2, n_max):
            self._fac[i] = self._fac[i - 1] * i % MOD
            self._inv[i] = MOD - self._inv[MOD%i] * (MOD // i) % MOD
            self._finv[i] = self._finv[i - 1] * self._inv[i] % MOD
    def com(self, n, r):
        if n < r: return 0
        if n < 0 or r < 0: return 0
        return self._fac[n] * (self._finv[r] * self._finv[n - r] % MOD) % MOD

MOD = 10**9+7
comb = Combination(10**6, MOD)
n,m,k = map(int, input().split())

ans = 0
for i in range(m):
    other_sum = i*(i+1)//2 + (m-1-i)*(m-i)//2
    # other_sum *= n
    pattern = n*n*comb.com(n*m-2,k-2)
    ans += pattern*other_sum
    ans%=MOD

for i in range(n):
    other_sum = i*(i+1)//2 + (n-1-i)*(n-i)//2
    # other_sum *= m
    pattern = m*m*comb.com(n*m-2,k-2)
    ans += pattern*other_sum
    ans%=MOD

print(ans//2)

Submission status: Wrong Answer

Solution code:
p = 10**9+7
N,M,K = map(int,input().split())
a = ((K*(K-1))//2)%p
b = (M**2)%p
b = (b*(((N*(N-1))//2)%p))%p
c = (N**2)%p
c = (c*((M*(M-1))//2)%p)%p
print((a*(b+c))%p)

Submission status: Wrong Answer

Solution code:
n, m, k = map(int, input().split())
mod = 10 ** 9 + 7
res_n, res_m = 0, 0

for i in range(n):
    for j in range(n):
        res_n += abs(i - j)
        res_n %= mod
res_n = (res_n * (m ** 2)) % mod

for i in range(m):
    for j in range(m):
        res_m += abs(i - j)
        res_m %= mod
res_m = (res_m * (n ** 2)) % mod

res = (res_n + res_m) // 2

f = [1 for _ in range(n*m)]
for i in range(1, n*m):
    f[i] = f[i-1] * i % mod

res = res * f[n*m-2] * pow(f[k-2], mod-2, mod) * pow(f[n*m-k], mod-2, mod) % mod

print(res)

Submission status: Wrong Answer

Solution code:
MOD = 10 ** 9 + 7
n, m, k = map(int, input().split())
def f(i, j):
    return i*(i-1)*(i+1)//6 * j ** 2
def c(a, b):
    r = 1
    for i in range(a, a - b, -1):
        r = r * i // (a + 1 - i)
        r %= MOD
    return r
print((f(n, m) + f(m, n)) * c(n*m - 2, k - 2) % MOD)

Submission status: Wrong Answer

Solution code:
N,M,K=map(int,input().split())
MOD=10**9+7
ans=0
x,y=1,1
k=min(K-2,N*M-K)
for i in range(k):
    x*=N*M-2-i
    y*=K-2-i
    x%=MOD
    y%=MOD
comb=x*pow(y,MOD-2,MOD)
comb%=MOD
for i in range(1,N):
    a=i*comb*(N-i)*M**2
    ans+=a
    ans%=MOD
for i in range(1,M):
    a=i*comb*(M-i)*N**2
    ans+=a
    ans%=MOD
print(ans%MOD)

Submission status: Wrong Answer

Solution code:
MOD=10**9+7
UPPERLIMIT=3*10**5
MODMUL=[1, 1]+[0]*(UPPERLIMIT-1)
for i in range(2, UPPERLIMIT+1):
  MODMUL[i]=MODMUL[i-1]*i%MOD
MODDIV=[1]*UPPERLIMIT+[pow(MODMUL[-1], MOD-2, MOD)]
for i in range(UPPERLIMIT, 0, -1):
  MODDIV[i-1]=MODDIV[i]*i%MOD
def MODCOMB(n, r):
  if n<r or n<1:
    return 0
  else:
    return (((MODMUL[n]*MODDIV[r])%MOD)*MODDIV[n-r])%MOD

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

ans=0
k=MODCOMB(N*M-2, K-2)
P=min(N, M)
Q=max(N, M)

for sa in range(1, P):
  ans=(ans+sa*(P-sa)*M*M*k)%MOD
  ans=(ans+sa*(P-sa)*N*N*k)%MOD
  
for sa in range(P, Q):
  ans=(ans+sa*(Q-sa)*P*P*k)%MOD

print(ans)

Submission status: Wrong Answer

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

fac = [1] * n*m
finv = [1] * n*m
inv = [1] * n*m

ans = 0
def COMinit():
    for i in range(2, n*m):
        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, k):
    if n < 0 or k < 0 or n < k:
        return 0
    return fac[n] * (finv[k] * finv[n - k] % mod) % mod
COMinit()
for i in range(1, n):
    ans += (COM(n*m - 2, k-2)) * ((n-i)*i * m**2)
for j in range(1, m):
    ans += (COM(n*m - 2, k-2)) * ((m-j)*j * n**2)
print(ans)

Submission status: Wrong Answer

Solution code:
n,m,k=map(int,input().split())
mod=10**9+7
f=[1]
for i in range(2*10**5+7):f+=[f[-1]*(i+1)%mod]
def comb(a,b):return f[a]*pow(f[b],mod-2,mod)*pow(f[a-b],mod-2,mod)%mod
ans=0
for i in range(1,n):
  ans+=(i*(n-i)*m**2)*(comb(n+m-2,k-2))
  ans%=mod
for i in range(1,m):
  ans+=(i*(m-i)*n**2)*(comb(n+m-2,k-2))
  ans%=mod
print(ans)

Submission status: Wrong Answer

Solution code:
import math
N,M,K = list(map(int, input().split()))
mod =1000000007

def comb(n, r):
    return (math.factorial(n) // (math.factorial(n - r) * math.factorial(r)))%mod

print(comb(N*M-2,K-2)*(M*N)%mod*((M*(N**2-1))%mod+(N*(M**2-1))%mod)//6%mod)

Submission status: Wrong Answer

Solution code:
import math
N,M,K = list(map(int, input().split()))

def comb(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))%1000000007

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

Submission status: Wrong Answer

Solution code:
from functools import reduce
p = 1000000007
def powmod(a, n):
    global p
    n_b = str(format(n, "b"))  # 2進表現に
    res = 1
    for bit in n_b:
        res = (res * res) % p
        if bit == "1":
            res = (res * a) % p
    return res
def cmod(n, r):
    if r > n // 2:
        return cmod(n, n - r)
    def mulmod(x, y):
        global p
        return x * y % p
    return powmod(reduce(mulmod, range(n - r + 1, n + 1), 1) * reduce(mulmod, range(1, r + 1), 1), (p - 2))
n, m, k = map(int, input().split())
print(((n**3-n)*m**2+(m**3-m)*n**2)//6*cmod(n+m-2,k-2)%p)

Submission status: Wrong Answer

Solution code:
a, b, c = map(int,input().split())
e = [23] * 300000
e[-1] += 1
for i in range(100000):
  w = e[1]
print(1)

Submission status: Wrong Answer

Solution code:
a, b, c = map(int,input().split())
e = [23] * 300000
e[-1] += 1
for i in range(100000):
  if i > 10:
    continue
  w = min(e)
print(1)

Submission status: Wrong Answer

Solution code:
a, b, c = map(int,input().split())
e = [23] * 300000
e[-1] += 1
for i in range(100):
  if i < 70:
    continue
  w = min(e)
print(1)

Submission status: Wrong Answer

Solution code:
a, b, c = map(int,input().split())
e = [23] * 300000
e[-1] += 1
for i in range(100):
  e[4] += 40
  e.sort()
print(1)

Submission status: Wrong Answer

Solution code:
a, b, c = map(int,input().split())
e = [23] * 300000
e[-1] += 1
for i in range(100):
  w = e.index(24)
print(1)

Submission status: Wrong Answer

Solution code:
a, b, c = map(int,input().split())
e = [23] * 300000
e[-1] += 1
for i in range(100):
  w = e.index(23)
print(1)

Submission status: Wrong Answer

Solution code:
a, b, c = map(int,input().split())
e = [23] * 300000
e[-1] += 1
for i in range(100):
  w = e.pop()
  e.append(w)
print(1)

Submission status: Wrong Answer

Solution code:
a, b, c = map(int,input().split())
e = [23] * 300000
e[-1] += 1
for i in range(100):
  w = e[-2]
  q = e[-1]
print(1)

Submission status: Wrong Answer

Solution code:
a, b, c = map(int,input().split())
e = [23] * 300000
e[-1] += 1
for i in range(100):
  w = min(e)
print(1)

Submission status: Wrong Answer

Solution code:
a, b, c = map(int,input().split())
e = [23] * 30000
e[-1] += 1
for i in range(100):
  w = e[i]
print(1)

Submission status: Wrong Answer

Solution code:
a, b, c = map(int,input().split())
e = [23] * 30000
e[-1] += 1
for i in range(100):
  w = e.index(24)
print(1)

Submission status: Wrong Answer

Solution code:
a, b, c = map(int,input().split())
e = [23] * 3000000
e[-1] += 1
for i in range(100):
  w = e[-i]
print(1)

Submission status: Wrong Answer

Solution code:
N, M, K = map(int,input().split())
MOD = 10 ** 9 + 7
ans = 0
C = 1

for i in range(1, K - 1):
    C *= N * M - i - 1
    C //= i
    
for i in range(N):
    for j in range(M):
        ad = (N - i) * (M - j) * (i + j)
        if i != 0 and j != 0:
            ad *= 2
            ans += ad    
print(ans * C % MOD)

Submission status: Wrong Answer

Solution code:
class cmbs(object):
    def __init__(self, mod):
        self.mod = mod
        self.g1 = [1, 1]
        self.g2 = [1, 1]
        inverse = [0, 1]
        for i in range(2, 10 ** 6 + 1):
            self.g1.append((self.g1[-1] * i) % mod)
            inverse.append((-inverse[mod % i] * (mod // i)) % mod)
            self.g2.append((self.g2[-1] * inverse[-1]) % mod)

    def cmb(self, n, r):
        if n > 10 ** 6:
            return self.cmbl(n, r)
        return self.cmbr(n, r)

    def cmbr(self, n, r):
        if r < 0 or r > n:
            return 0
        r = min(r, n - r)
        return self.g1[n] * self.g2[r] * self.g2[n-r] % self.mod

    def cmbl(self, n, r):
        t = 1
        r = min(r, n-r)
        for i in range(n - r + 1, n + 1):
            t = t * i % self.mod
        return t * self.g2[r] % self.mod

def main():
    N, M, K = map(int, input().split())
    mod = 10**9 + 7
    c = cmbs(mod)
    r = c.cmb((N*M)-2, K-2)
    r2 = 0
    for i in range(N):
        r2 += ((i + 1) * i + (N - i - 1) * (N-i))//2
    r2 *= pow(M, 2, mod)
    r2 %= mod
    r3 = 0
    for i in range(M):
        r3 += ((i + 1) * i + (M - i - 1) * (M-i))//2
    r3 *= pow(N, 2, mod)
    r3 %= mod
    r = r * (r2 + r3) // 2
    return r % mod
print(main())

Submission status: Wrong Answer

Solution code:
MOD = 10 ** 9 + 7


def prepare(n):
    global MOD
    modFacts = [0] * (n + 1)
    modFacts[0] = 1
    for i in range(n):
        modFacts[i + 1] = (modFacts[i] * (i + 1)) % MOD

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

    return modFacts, invs


def modCombi(n, r):
    global MOD
    return (modFacts[n] * invs[n - r] * invs[r]) % MOD


N, M, K = map(int, input().split())
modFacts, invs = prepare(N * M)
var = modCombi(N * M - 2, K - 2)

ans = 0
if N < M:
    N, M = M, N
L = [0] * (N + 1)
for i in range(1, N + 1):
    L[i] = L[i - 1] + i
for x in range(1, N + 1):
    Sx = (M * (L[N - x] + L[x - 1])) % MOD
    Sy = (N * (L[M - x] + L[x - 1])) % MOD
    ans += ((Sx + Sy) * M) % MOD

print((ans * invs[2] * var) % MOD)

Submission status: Wrong Answer

Solution code:
mod = 10**9+7
rng = 200100
fctr = [1]
finv = [1]
for i in range(1,rng):
  fctr.append(fctr[-1]*i%mod)
for i in range(1,rng):
  finv.append(pow(fctr[i],mod-2,mod))
def cmb(n,k):
  if n<0 or k<0:
    return 0
  else:
    return fctr[n]*finv[n-k]*finv[k]%mod

n,m,k = map(int,input().split())
cost = [[0 for i in range(m+1)] for j in range(n+1)]
cost[1][1] = ((n-1)+(m-1))*n*m//2
for i in range(1,n+1):
  for j in range(1,m+1):
    if j>1:
      cost[i][j] = cost[i][j-1]-(m-2*(j-1))*n
    elif i>1:
      cost[i][j] = cost[i-1][j]-(n-2*(i-1))*m
ans = 0
for i in cost:
  ans = (ans+sum(i))%mod
ans //= 2
ans = ans*cmb(n*m-2,k-2)%mod
print(ans)

Submission status: Wrong Answer

Solution code:
def comb(n, k, p):
    """power_funcを用いて(nCk) mod p を求める"""
    from math import factorial
    if n < 0 or k < 0 or n < k: return 0
    if n == 0 or k == 0: return 1
    a = factorial(n) % p
    b = factorial(k) % p
    c = factorial(n - k) % p
    return (a * power_func(b, p - 2, p) * power_func(c, p - 2, p)) % p


def power_func(a, b, p):
    """a^b mod p を求める"""
    if b == 0: return 1
    if b % 2 == 0:
        d = power_func(a, b // 2, p)
        return d * d % p
    if b % 2 == 1:
        return (a * power_func(a, b - 1, p)) % p


N, M, K = map(int, input().split())
mod = 10 ** 9 + 7
c = comb(N * M - 2, K - 2, mod)

sumx = 0
for d in range(1, M + 1):
    sumx *= d * (M - d)
    sumx %= mod
sumx *= N
sumx %= mod
sumx *= N
sumx %= mod

sumy = 0
for d in range(1, N + 1):
    sumy += d * (N - d)
    sumy %= mod
sumy *= M
sumy %= mod
sumy *= M
sumy %= mod

ans = (((sumx + sumy) % mod) * c) % mod
print(ans)

Submission status: Wrong Answer

Solution code:
from operator import mul
from functools import reduce
def comb2(n,r):
    r = min(n - r, r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1, r + 1))
    return over // under

import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
mod = 10**9 + 7
inf = float('inf')
ans = int(0)

N, M, K = LI()

cou = int(0)
maxL = N + M -2
L = int(0)
#距離i+1の組み合わせ

#for i in range(maxL):
for j in range(N):
    L += (N - j - 1) * (M ** 2) * (j + 1)
for j in range(M):
    L += (M - j - 1) * (N ** 2) * (j + 1)
#    for j in range(i+2):
#        if i>1 and i+1>j>0:
#            L[i] += max((N-j)*(M-(1+i)+j),0)*(i+1)*2
#        else:
#            L[i] += max(((N - j) * (M - (1 + i) + j)), 0) * (i + 1)

cou = comb2(N*M-2,K-2)%mod

ans = cou *L%mod

Submission status: Wrong Answer

Solution code:
N,M,K = map(int, input().split())

comb = 1
mod = 10**9+7
for i in range(min(K-2, N*M-K)):
    comb *= (N*M-2-i)
for i in range(min(K-2, N*M-K)):
    comb //= i+1
    
comb %= mod

x = (N*(N*(N+1))//2-N*(N+1)*(2*N+1)//3)*M**2
y = (M*(M*(M+1))//2-M*(M+1)*(2*M+1)//3)*N**2
    
ans = x+y
ans %= mod
    
print((ans*comb)%mod)

Submission status: Wrong Answer

Solution code:
MOD = 10 ** 9 + 7

def mod_combination(n, k):
    def extended_gcd(a, b):
        if b == 0:
            return (a, 1, 0)
        d, x, y = extended_gcd(b, a % b)
        return (d, y, x - (a // b) * y)
    p, q = 1, 1
    for i in range(n - k + 1, n + 1):
        p = (p * i) % MOD
    for i in range(2, k + 1):
        q = (q * i) % MOD
    return p * (extended_gcd(q, MOD)[1] % MOD) % MOD

def mod_pow(a, b):
    return pow(a, b, MOD)


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

X = mod_pow(M, 2) * (mod_pow(N, 3) - N) % MOD
Y = mod_pow(N, 2) * (mod_pow(M, 3) - M) % MOD

comb = mod_combination(N * M - 2, K - 2)

ans = (X + Y) // 6 * comb % MOD

print(ans)

Submission status: Wrong Answer

Solution code:
MOD = 10 ** 9 + 7

def mod_combination(n, k):
    def extended_gcd(a, b):
        if b == 0:
            return (a, 1, 0)
        d, x, y = extended_gcd(b, a % b)
        return (d, y, x - (a // b) * y)
    p, q = 1, 1
    for i in range(n - k + 1, n + 1):
        p = (p * i) % MOD
    for i in range(2, k + 1):
        q = (q * i) % MOD
    return p * (extended_gcd(q, MOD)[1] % MOD) % MOD

def mod_pow(a, b):
    return pow(a, b, MOD)


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

X = mod_pow(M, 2) * (mod_pow(N, 3) - N) % MOD
Y = mod_pow(N, 2) * (mod_pow(M, 3) - M) % MOD

comb = mod_combination(N * M - 2, K - 2)

ans = ((X + Y) % MOD) // 6 * comb % MOD

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
mod = pow(10, 9) + 7
def C(n, r):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod
NNN = (10**6)
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]
for i in range(2, NNN+1):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )
n,m,k=map(int,input().split())
#n=m=k=2
print(C(n*m,k)*k*(k-1)%mod*(n+m)//6%mod)

Submission status: Wrong Answer

Solution code:
mod = 1000000007
import sys
input = sys.stdin.readline
N, M, K = map(int, input().split())


def cmb(n, r):
    if n<0 or r<0 or r>n:
        return None
    r = min(r, n-r)
    if r == 0:
        return 0
    if r == 1:
        return n
    numerator = [0]*r
    denominator = [0]*r
    for k in range(r):
        numerator[k] = n-r+k+1
        denominator[k] = k+1
    for p in range(2, r+1):
        pivot = denominator[p-1]
        if pivot > 1:
            offset = (n-r) % p
            for k in range(p-1, r, p):
                numerator[k-offset] //= pivot
                denominator[k] //= pivot
    res = 1
    for n in numerator:
        if n > 1:
            res *= n
    return res

N2 = N**2
M2 = M**2
Xpattern = [(x * (N-x)) % mod for x in range(N)]
Ypattern = [(y * (M-y)) % mod for y in range(M)]
coef = cmb(N*M-2, K-2)

print(((sum(Xpattern)*M2+sum(Ypattern)*N2)*coef)%mod)

Submission status: Wrong Answer

Solution code:
mod = 1000000007
import sys
input = sys.stdin.readline
N, M, K = map(int, input().split())


def cmb(n, r):
    if n<0 or r<0 or r>n:
        return None
    r = min(r, n-r)
    if r == 0:
        return 0
    if r == 1:
        return n

    numerator = [0]*r
    denominator = [0]*r
    for k in range(r):
        numerator[k] = n-r+k+1
        denominator[k] = k+1
    for p in range(2, r+1):
        pivot = denominator[p-1]
        if pivot > 1:
            offset = (n-r) % p
            for k in range(p-1, r, p):
                numerator[k-offset] //= pivot
                denominator[k] //= pivot
    res = 1
    for n in numerator:
        if n > 1:
            res *= n
    return res

N2 = N**2
M2 = M**2
Xpattern = [(x * (N-x)) % mod for x in range(N)]
Ypattern = [(y * (M-y)) % mod for y in range(M)]
coef = cmb(N*M-2, K-2) % mod

print(((sum(Xpattern)*M2+sum(Ypattern)*N2)*coef)%mod)

Submission status: Wrong Answer

Solution code:
def mulmod(x, y, mod=10**9):
    return x * y % mod


def comb(n, k, mod=10**9 + 7):
    from functools import reduce
    k = min(k, n - k)
    x = reduce(mulmod, range(n - k + 1, n + 1), 1)
    y = reduce(mulmod, range(1, k + 1), 1)
    return x * pow(y, mod - 2, mod) % mod


def solve(string):
    n, m, k = map(int, string.split())
    mod = 10**9 + 7
    base = n * m * (n + m) * (n * m - 1) // 6 % mod
    return str(base * comb(n * m - 2, k - 2) % mod)


if __name__ == '__main__':
    print(solve(input()))

Submission status: Wrong Answer

Solution code:
import operator as op
from functools import reduce


def ncr(n, r):
    r = min(r, n - r)
    numer = reduce(op.mul, range(n, n - r, -1), 1) % (10**9+7)
    denom = reduce(op.mul, range(1, r + 1), 1)
    return numer // denom


def solve(string):
    n, m, k = map(int, string.split())
    base = n * m * ((n + 1) * (m + 1) * (n + m - 2) - n**2 - m**2 + 2) // 6 % (10**9 + 7)
    return str(base * ncr(m * n - 2, k - 2) % (10**9 + 7))


if __name__ == '__main__':
    print(solve(input()))

Submission status: Wrong Answer

Solution code:
def solve(string):
    n, m, k = map(int, string.split())
    base = n * m * ((n + 1) * (m + 1) * (n + m - 2) - n**2 - m**2 + 2) // 6 % (10**9 + 7)
    return str(base)


if __name__ == '__main__':
    print(solve(input()))

Submission status: Wrong Answer

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

def comb(n, k):
    m = 1
    if n < 2 * k:
        k = n - k
    for i in range(1, k + 1):
        m = (m * (n - i + 1) / i)%MOD    
    return m

ans_x=0
ans_y=0
for i in range(1,N):
  ans_x+=(i*(N-i))
for i in range(1,M):
  ans_y+=(i*(M-i))
ans_x*=(M**2)
ans_y*=(N**2)
ans=comb(N*M-2,K-2)%MOD
ans*=(ans_x+ans_y)
print(int(ans%MOD))

Submission status: Wrong Answer

Solution code:
def main():
    mod = 10**9+7
    n, m, k = list(map(int, input().split()))
    # 　ある配置を固定した時、その2つの配置でmanhattan距離が計算される回数は、他の組み合わせ数。
    combination = mod_combination(n*m-2, k-2)
    x=y=0
    for i in range(1, n):
        x += i * (n-i)
    for j in range(1, m):
        y += j * (m-j)
    return (((m ** 2) % mod * x % mod) + ((n ** 2) % mod * y % mod)) * combination % mod


def mod_combination(n, r, mod=10**9+7):
    fact = 1
    for i in range(n-r+1, n+1):
        fact = fact * i % mod
    divisor = 1
    for j in range(1, r+1):
        divisor = divisor * j % mod
    return int(fact/divisor)


print(main())

Submission status: Wrong Answer

Solution code:
def main():
    mod = 10**9+7
    n, m, k = list(map(int, input().split()))
    # 　ある配置を固定した時、その2つの配置でmanhattan距離が計算される回数は、他の組み合わせ数。
    combination = mod_combination(n*m-2, k-2)
    x=y=0
    for i in range(1, n):
        x += i * (n-i)
    for j in range(1, m):
        y += j * (m-j)
    return (((m ** 2) % mod * x % mod) + ((n ** 2) % mod * y % mod)) * combination % mod


def mod_combination(n, r, mod=10**9+7):
    fact = 1
    for i in range(n-r+1, n+1):
        fact = fact * i % mod
    divisor = 1
    for j in range(1, r+1):
        divisor = divisor * j % mod
    return int(fact/divisor)


main()

Submission status: Wrong Answer

Solution code:
def main():
    mod = 10**9+7
    n, m, k = list(map(int, input().split()))
    # 　ある配置を固定した時、その2つの配置でmanhattan距離が計算される回数は、他の組み合わせ数。
    combination = mod_combination(n*m-2, k-2)
    print(((each_coordinate(m, n, mod) + each_coordinate(n, m, mod))*combination)%mod)
    


def each_coordinate(arg_one, arg_two, mod):
    arg_squrared = ((arg_one%mod)**2)%mod
    return sum([((i%mod)*(arg_two-i)%mod)%mod*arg_squrared for i in range(1, arg_two)])


def mod_combination(n, r, mod=10**9+7):
    fact = 1
    for i in range(n-r+1, n+1):
        fact = fact * i % mod
    divisor = 1
    for j in range(1, r+1):
        divisor = divisor * j % mod
    return int(fact/divisor)


main()

Submission status: Wrong Answer

Solution code:
from math import factorial


n, m, k = list(map(int, input().split()))
# 　ある配置を固定した時、その2つの配置でmanhattan距離が計算される回数は、他の組み合わせ数。
combination = factorial(n*m-2)//factorial(k-2)//factorial((n*m-2)-(k-2))
# n=5なら1,2,3,4それぞれにm**2をかける。
print((sum([m**2*i*(n-i) for i in range(1, n)]) + sum([n**2*i*(m-i) for i in range(1, m)])) * combination)
# あるマンハッタン距離の時の配置の数

Submission status: Wrong Answer

Solution code:
import itertools
N,M,K = map(int, input().split())
ans = 0
x = list(range(1,N+1))
y = list(range(1,M+1))
xy =  list(itertools.product(x,y))
NM = N*M
for i in range(NM):
  for j in range(i+1,NM):
    ans += abs(xy[i][0]-xy[j][0]) +  abs(xy[i][1]-xy[j][1])

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

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    return

#B
def B():
    return

#C
def C():
    n,m = LI()
    t = [0 for i in range(n+1)]
    for i in range(m):
        l,r = LI()
        t[l-1] += 1
        t[r] -= 1
    for i in range(n):
        t[i+1] += t[i]
        if t[i] == m:
            t[i] = 1
        else:
            t[i] = 0
    print(sum(t[:n]))
    return

#D
def D():
    n,m = LI()
    a = LI()
    q = []
    for i in range(n):
        heappush(q,a[i])
    l = LIR(m)
    l.sort(key = lambda x:-x[1])
    for b,c in l:
        for i in range(b):
            x = heappop(q)
            if x < c:
                x = c
                heappush(q,x)
            else:
                heappush(q,x)
                break
    print(sum(q))
    return

#E
def E():
    n,m,k = LI()
    M = n*m
    fact = [1]*(M+1)
    for i in range(M):
        fact[i+1] = fact[i]*(i+1)%mod
    inv = [1]*(M+1)
    inv[M] = pow(fact[M],mod-2,mod)
    for i in range(M)[::-1]:
        inv[i] = inv[i+1]*(i+1)%mod
    ans = fact[M-2]*inv[k-2]*inv[M-k]%mod
    s = 0
    for i in range(1,k+1):
        s += i*(max(0,n-i)*m**2+max(0,m-i)*n**2)%mod
        s %= mod
    ans = ans*s%mod
    print(ans)
    return

#F
def F():
    q = I()
    m = 0
    l = [-float("inf"),float("inf")]
    x = 0
    num = 0
    for _ in range(q):
        Q = LI()
        if len(Q) == 1:
            print(x,m)
        else:
            z,a,b = Q
            m += b
            if num == 0:
                num += 1
                l = [a,float("inf")]
                x = a
            elif num == 1:
                if a != l[0]:
                    num += 1
                    l = [min(a,l[0]),max(a,l[0])]
                    x = l[0]
                    m += l[1]-l[0]
            else:
                num += 1
                if num % 2:
                    if l[0] <= a < l[1]:
                        m += min(a-l[0],l[1]-a)
                        x = a
                    elif a < l[0]:
                        m += l[0]-a
                        x = l[0]
                        l = [a,l[1]]
                    else:
                        m += a-l[1]
                        x = l[1]
                        l = [l[0],a]
                else:
                    if l[0] <= a < l[1]:
                        if a < x:
                            m += x-a
                            l = [a,x]
                            x = a
                        else:
                            m += a-x
                            l = [x,a]
                    elif a < l[0]:
                        m += x-a
                        x = l[0]
                        l = [l[0],x]
                    else:
                        m += a-x
                        l = [x,l[1]]
    return

#G
def G():
    return

#H
def H():
    return

#I
def I_():
    return

#J
def J():
    return

#Solve
if __name__ == "__main__":
    E()

Submission status: Wrong Answer

Solution code:

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

comb = [0] * (N * M + 1)
comb[K-2] = 1
for i in range(K-1, N*M+1):
    comb[i] = comb[i-1] * i // (i - (K - 2))
    comb[i] %= 1000000007

cost = 0
for d in range(1, N):
    cost += d * M**2 * (N - d) * comb[N*M-2]# comb[(N-d-1)*M]
    cost %= 1000000007
for d in range(1, M):
    cost += d * N**2 * (M - d) * comb[N*M-2]# comb[(M-d-1)*N]
    cost %= 1000000007
    
print(cost)

Submission status: Wrong Answer

Solution code:
MAX = 10**9 + 7

def mod_inv(i, mod):
    return pow(i, mod-2, mod)

def combination(_N, _K):
    if _K > (_N/2):
        _K = _N - _K
    up = 1
    low = 1
    for i in range (_K):
        up = up * (_N - i) % MAX
        low = low * (i + 1) % MAX
    ret = up * mod_inv(low, MAX) % MAX
    return ret

def solve2():
    N, M, K = [int(_) for _ in raw_input().split()]
    sumx = 0
    for xi in range(1, N+1):
        sumx = (sumx + (N*(N+1)//2) - (N + 1 - xi) * xi) % MAX
    sumx = (sumx * M * M) %MAX
    sumy = 0
    for yi in range(1, M+1):
        sumy = (sumy + (M*(M+1)//2) - (M + 1 - yi) * yi) % MAX
    sumy = (sumy * N * N) %MAX
    ret = (sumx + sumy) // 2 * combination(M*N-2, K-2) % MAX
    print ret

if __name__ == '__main__':
    solve2()

Submission status: Wrong Answer

Solution code:
MAX = 10**9 + 7

def mod_inv(i, mod):
    return pow(i, mod-2, mod)

def combination(_N, _K):
    if _K > (_N/2):
        _K = _N - _K
    up = 1
    low = 1
    for i in range (_K):
        up = up * (_N - i) % MAX
        low = low * (i + 1) % MAX
    ret = up * mod_inv(low, MAX) % MAX
    return ret

def solve():
    N, M, K = [int(_) for _ in raw_input().split()]
    disSum = M*N* (M*(N+1)*(N-1) + N*(M+1)*(M-1)) / 6
    ret = disSum * combination(M*N-2, K-2) % MAX
    print ret

Submission status: Wrong Answer

Solution code:
from functools import reduce
from operator import mul


def cmb2(n, r):
  r = min(n - r, r)
  if r == 0:
    return 1
  over = reduce(mul, range(n, n - r, -1))
  under = reduce(mul, range(1, r + 1))

  return over // under


def main():
  MOD = 1000000007

  N, M, K = [int(i) for i in input().strip().split(' ')]
  c = cmb2(N * M - 2, K - 2) % MOD
  print(c)

  X = 0
  Y = 0
  for i in range(M):
    X += (M - i) * i
  for i in range(N):
    Y += (N - i) * i

  total = (X * (N ** 2) + Y * (M ** 2)) % MOD * c % MOD
  print(total)


main()

Submission status: Wrong Answer

Solution code:
from scipy.misc import*;n,m,k=map(int,input().split());s=lambda x,y:sum(y*y*i*(n-i)for i in range(x));print((s(n,m)+s(m,n))*comb(n*m-2,k-2,1)%(10**9+7))

Submission status: Wrong Answer

Solution code:
from math import factorial

def comb(n, r):
    return factorial(n) // (factorial(n - r) * factorial(r))

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

C = comb(N*M-2, K-2)
#print(int(C))

A = int(0)
for d in range(N):
    a = (N-d)*(M**2)

    A += int(d*a)

B = int(0)
for d in range(M):
    b = (M-d)*(N**2)
    B += int(d*b)

ans = int((A+B)*C)
ans = ans%(1000000001)
print(ans)

Submission status: Wrong Answer

Solution code:
from math import factorial

def comb(n, r):
    return factorial(n) // (factorial(n - r) * factorial(r))

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

C = comb(N*M-2, K-2)
print(int(C))

A = int(0)
for d in range(N):
    a = (N-d)*(M**2)

    A += int(d*a)

B = int(0)
for d in range(M):
    b = (M-d)*(N**2)
    B += int(d*b)

ans = int((A+B)*C)
print(ans)