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: Time Limit Exceeded

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(3, M + N + 1):
    cnt = 0
    a = min(N, i - 1)
    b = i - a
    for _ in range(b, min(i - 1, M) + 1):
        if a == 1 or b == 1:
            cnt += (N - a + 1) * (M - b + 1)
        else:
            cnt += (N - a + 1) * (M - b + 1) * 2
        a -= 1
        b += 1
    ans += (i - 2) * cnt
    
print(ans * C % MOD)

Submission status: Time Limit Exceeded

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(3, M + N + 1):
    cnt = 0
    a = min(N, i - 1)
    b = i - a
    for _ in range(b, min(i - 1, M) + 1):
        if a == 1 or b == 1:
            cnt += (N - a + 1) * (M - b + 1)
        else:
            cnt += (N - a + 1) * (M - b + 1) * 2
        a -= 1
        b += 1
    ans += (i - 2) * cnt
    
print(ans * C % MOD)

Submission status: Time Limit Exceeded

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(3, M + N + 1):
    cnt = 0
    a = min(N, i - 1)
    b = i - a
    for _ in range(b, min(i - 1, M) + 1):
        if a == 1 or b == 1:
            cnt += (N - a + 1) * (M - b + 1)
        else:
            cnt += (N - a + 1) * (M - b + 1) * 2
        a -= 1
        b += 1
    ans += (i - 2) * cnt * C
    
print(ans % MOD)

Submission status: Time Limit Exceeded

Solution code:
N,M,K=map(int,input().split())
import math
def com(n, r):
  return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
A=com(M*N-2, K-2)
MOD=10**9+7
ans=0
for d in range(1,N):
  ans+=d*(N-d)*M*M*A%MOD
for d in range(1,M):
  ans+=d*(M-d)*N*N*A%MOD
print(ans%MOD)

Submission status: Time Limit Exceeded

Solution code:
mod = 10**9 + 7
n, m, k = map(int, input().split())
nm = n * m
fact = [1] * (nm-1)
inv = [1] * (nm-1)
inv_fact = [1] * (nm-1)
for i in range(2, nm-1):
  fact[i] = fact[i-1] * i % mod
  inv[i] = -(mod // i) * inv[mod % i] % mod
  inv_fact[i] = inv_fact[i-1] * inv[i]
comb = fact[nm-2] * inv_fact[k-2] * inv_fact[nm-k] % mod
cost_x = (n-1) * n * (n+1) // 6 * m * m % mod
cost_y = (m-1) * m * (m+1) // 6 * n * n % mod
print(comb * (cost_x + cost_y) % mod)

Submission status: Time Limit Exceeded

Solution code:
mod = 10**9 + 7
n, m, k = map(int, input().split())
nm = n * m
fact = [1] * (nm+1)
inv = [1] * (nm+1)
inv_fact = [1] * (nm+1)
for i in range(2, nm+1):
  fact[i] = fact[i-1] * i % mod
  inv[i] = -(mod // i) * inv[mod % i] % mod
  inv_fact[i] = inv_fact[i-1] * inv[i]
cost = 0
comb = fact[nm-2] * inv_fact[k-2] * inv_fact[nm-k] % mod
cost_x = 0
cost_y = 0
for dx in range(1, n):
  cost_x += dx * (n - dx) * m * m % mod
for dy in range(1, m):
  cost_y += dy * (m - dy) * n * n % mod
print(comb * (cost_x + cost_y) % mod)

Submission status: Time Limit Exceeded

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

MOD = 1000000007
def pow_mod(x, y):
    if y == 0: return 1
    ans = 1
    while y > 1:
        if y % 2 != 0: 
            ans *= x
            ans %= MOD
        x *= x
        x %= MOD
        y //= 2
    return ans * x % MOD
mod_inv = lambda x: pow_mod(x, MOD - 2)

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

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

w = (m * n - 2) % MOD
wCx = {0: 1}
for i in range(1, k+1):
  wCx[i] = wCx[i - 1] 
  wCx[i] *= (w - i + 1) % MOD
  wCx[i] %= MOD
  wCx[i] *= mod_inv(i)
  wCx[i] %= MOD

ans = ((a + b) % MOD) 
ans *= wCx[k-2]
ans %= MOD

print(ans)

Submission status: Time Limit Exceeded

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

mod = 1000000007
def pow(x, n):
    ret = 1
    while n > 0:
        if (n & 1) == 1:
            ret = (ret * x) % mod
        x = (x * x) % mod
        n //= 2
    return ret

fac = [1]
inv = [1]
for i in range(1, n * m + 1):
    fac.append((fac[-1] * i) % mod)
    inv.append(pow(fac[i], mod - 2))

def cmb(n, k):
    return ((fac[n] * inv[k]) % mod * inv[n - k]) % mod

def doit(n, m, k):
    ret = 0
    for d in range(m):
        ret = (ret + d * (m - d)) % mod
    return (ret * n * n * cmb(n * m - 2, k - 2)) % mod

print((doit(n, m, k) + doit(m, n, k)) % mod)

Submission status: Time Limit Exceeded

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

mod = 1000000007
def pow(x, n):
    ret = 1
    while n > 0:
        if (n & 1) == 1:
            ret = (ret * x) % mod
        x = (x * x) % mod
        n //= 2
    return ret

fac = [1]
inv = [1]
for i in range(1, n * m + 1):
    fac.append((fac[-1] * i) % mod)
    inv.append(pow(fac[i], mod - 2))

def cmb(n, k):
    return ((fac[n] * inv[k]) % mod * inv[n - k]) % mod

def doit(n, m, k):
    ret = 0
    for d in range(m):
        ret = (ret + d * (m - d) * n * n * cmb(n * m - 2, k - 2)) % mod
    return ret

print((doit(n, m, k) + doit(m, n, k)) % mod)

Submission status: Time Limit Exceeded

Solution code:
import math
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


n, m, k = map(int, input().split())
cmb = combinations_count(n * m - 2, k - 2)
ans = 0
for i in range(1, n):
    ans += i * cmb * m * m * (n - i)
    ans %= 10 ** 9 + 7

for i in range(m):
    ans += i * cmb * n * n * (m - i)
    ans %= 10 ** 9 + 7

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

Submission status: Time Limit Exceeded

Solution code:
import math
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


n, m, k = map(int, input().split())
cmb = combinations_count(n * m - 2, k - 2)
ans = 0
for i in range(n):
    for j in range(i, n):
        if i < j:
            ans += abs(i - j) * cmb * m * m
            ans %= 10 ** 9 + 7

for i in range(m):
    for j in range(i, m):
        if i < j:
            ans += abs(i - j) * cmb * n * n
            ans %= 10 ** 9 + 7

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

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import re
import math
import fractions
import random
import time
#import numpy as np
mod=int(10**9+7)
inf=int(10**20)
fac=[1]*250000
for a in range(2,250000):
    fac[a]=fac[a-1]*a%mod
class union_find():
    def __init__(self,n):
        self.n=n
        self.P=[a for a in range(N)]
        self.rank=[0]*n

    def find(self,x):
        if(x!=self.P[x]):self.P[x]=self.find(self.P[x])
        return self.P[x]

    def same(self,x,y):
        return self.find(x)==self.find(y)

    def link(self,x,y):
        if self.rank[x]<self.rank[y]:
            self.P[x]=y
        elif self.rank[y]<self.rank[x]:
            self.P[y]=x
        else:
            self.P[x]=y
            self.rank[y]+=1

    def unite(self,x,y):
        self.link(self.find(x),self.find(y))

    def size(self):
        S=set()
        for a in range(self.n):
            S.add(self.find(a))
        return len(S)
def bin_(num,size):
    A=[0]*size
    for a in range(size):
        if (num>>(size-a-1))&1==1:
            A[a]=1
        else:
            A[a]=0
    return A
def comb(n,r):return math.factorial(n)//math.factorial(n-r)//math.factorial(r)
def next_comb(num,size):
    x=num&(-num)
    y=num+x
    z=num&(~y)
    z//=x
    z=z>>1
    num=(y|z)
    if(num>=(1<<size)):return False
    else:
        return num



def comb_(n,r):return fac[n]*pow(fac[n-r],mod-2,mod)*pow(fac[r],mod-2,mod)
#main
def solve():
    return

#入力
N,M,K=map(int,input().split())
sum_=0
for a in range(N-1):
    for b in range(a+1,N):
        sum_+=M*M*abs(a-b)*comb_(N*M-2,K-2)%mod
for a in range(M-1):
    for b in range(a+1,M):
        sum_+=N*N*abs(a-b)*comb_(N*M-2,K-2)%mod

print(sum_%mod)

Submission status: Time Limit Exceeded

Solution code:
n,m,k=map(int,input().split())
mod=10**9+7
from operator import mul
from functools import reduce

def cmb(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%mod
A=n*m
v=cmb(A-2,k-2)
t=0
y=0
for i in range(1,n):
  t+=i*(n-i)*m*m%mod
for i in range(1,m):
  y+=i*(m-i)*n*n%mod

ans=v*(t+y)
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
n,m,k=map(int,input().split())
mod=10**9+7
from operator import mul
from functools import reduce

def cmb(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%mod
A=n*m
v=cmb(A-2,k-2)
t=0
y=0
for i in range(1,n):
  t+=i*(n-i)*m*m%mod
for i in range(1,m):
  y+=i*(m-i)*n*n%mod

ans=v*(t+y)
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
n,m,k=map(int,input().split())
mod=10**9+7
from operator import mul
from functools import reduce

def cmb(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
A=n*m
v=cmb(A-2,k-2)
t=0
y=0
for i in range(1,n):
  t+=i*(n-i)*m*m
for i in range(1,m):
  y+=i*(m-i)*n*n

ans=v*(t+y)
print(ans%mod)

Submission status: Time Limit Exceeded

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

print(ans)

Submission status: Time Limit Exceeded

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

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

comb = a//b
ans = ((N*N*(N+1)//2-N*(N+1)*(2*N+1)//6)*M**2 + (M*M*(M+1)//2-M*(M+1)*(2*M+1)//6)*N**2)%mod
ans *= comb
print(ans%mod)

Submission status: Time Limit Exceeded

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)
    comb //= i+1

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

Submission status: Time Limit Exceeded

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)//6)*M**2
y = (M*M*(M+1)//2-M*(M+1)*(2*M+1)//6)*N**2
ans = (x+y)*comb
print(ans%mod)

Submission status: Time Limit Exceeded

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

x = 0
y = 0
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
for d in range(1, N):
    x += d*(N-d)*M**2
for d in range(1, M):
    y += d*(M-d)*N**2
    
ans = x+y
ans %= mod
    
print((ans*comb)%mod)

Submission status: Time Limit Exceeded

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

mod = 10**9 + 7

def chs(a,b, md):
    res = 1
    for i in range(a-b+1,a+1):
        res *=  i
        res %= md
    rev = 1
    for i in range(1,b+1):
        rev *= i
        rev %= md
    rev2 = pow(rev,md-2,md)
    
    res *= rev2
    res %= md
    
    return res

ans = 0

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

        

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

Submission status: Time Limit Exceeded

Solution code:
from math import factorial as f
n,m,k=map(int,input().strip().split())
print((f(n*m-2)//(f(k-2)*f(n*m-k))*(m*m*(n**3-n)+n*n*(m**3-m))//6)%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
from operator import mul
from functools import reduce

def cmb(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

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

c = cmb(N*M-2,K-2)

ans = c * (M**2 * (N**2 * (N+1)//2 - N*(N+1)*(2*N+1)//6) + N**2 * (M**2 * (M+1)//2 - M*(M+1)*(2*M+1)//6)) % 1000000007

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from operator import mul
from functools import reduce

def cmb(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

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

sum = 0
c = cmb(N*M-2,K-2)
for m in range(M):
    sum += c * (M-m) * (N**2) * m
    sum %= 1000000007
for n in range(N):
    sum += c * (N-n) * (M**2) * n
    sum %= 1000000007

print(sum)

Submission status: Time Limit Exceeded

Solution code:
def conb(m, n):
    a = 1
    for i in range(n-m):
        a *= n - i
        a //= i+1
    return a

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

sum = 0
c = conb(K-2, N*M-2)
for m in range(M):
    sum += c * (M-m) * (N**2) * m
    sum %= 1000000007
for n in range(N):
    sum += c * (N-n) * (M**2) * n
    sum %= 1000000007

print(sum)

Submission status: Time Limit Exceeded

Solution code:
def fact(n):
    a = 1
    for i in range(n):
        a *= i+1
    return a

def conb(m, n):
    return fact(n) // fact(m) // fact(n-m)

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

sum = 0
c = conb(K-2, N*M-2)
for m in range(M):
    sum += c * (M-m) * (N**2) * m
    sum %= 1000000007
for n in range(N):
    sum += c * (N-n) * (M**2) * n
    sum %= 1000000007

print(sum)

Submission status: Time Limit Exceeded

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

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 = 1
num = min(K-2, N*M-K)
for i in range(N*M-2, N*M-2-num, -1):
    coef *= i
for j in range(1, num+1):
    coef //= j
coef %= mod

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

Submission status: Time Limit Exceeded

Solution code:
modout = lambda x: x%1000000007
import sys
input = sys.stdin.readline
N, M, K = map(int, input().split())
N2 = N**2
M2 = M**2
Xpattern = [x * (N-x) for x in range(N)]
Ypattern = [y * (M-y) for y in range(M)]
coef = 1
num = min(K-2, N*M-K)
for i in range(N*M-2, N*M-2-num, -1):
    coef *= i
for j in range(1, num+1):
    coef //= j


print(modout((sum(Xpattern)*M2+sum(Ypattern)*N2)*coef))

Submission status: Time Limit Exceeded

Solution code:
modout = lambda x: x%1000000007

N, M, K = map(int, input().split())
N2 = N**2
M2 = M**2
Xpattern = [x * (N-x)*M2 for x in range(N)]
Ypattern = [y * (M-y)*N2 for y in range(M)]
coef = 1
num = min(K-2, N*M-K)
for i in range(N*M-2, N*M-2-num, -1):
    coef *= i
for j in range(1, num+1):
    coef //= j


print(modout((sum(Xpattern)+sum(Ypattern))*coef))

Submission status: Time Limit Exceeded

Solution code:
def comb(n, k, mod=10**9 + 7):
    from functools import reduce
    from operator import mul
    k = min(k, n - k)
    x = reduce(mul, range(n - k + 1, n + 1), 1) % mod
    y = reduce(mul, range(1, k + 1), 1) % mod
    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: Time Limit Exceeded

Solution code:
from scipy.misc import comb


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


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

Submission status: Time Limit Exceeded

Solution code:
from scipy.misc import comb


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 * comb(n * m - 2, min(k - 2, n * m - k), exact=True) % (10**9 + 7))


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

Submission status: Time Limit Exceeded

Solution code:
from scipy.misc import comb


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 * comb(n * m - 2, k - 2, exact=True) % (10**9 + 7))


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

Submission status: Time Limit Exceeded

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)
    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: Time Limit Exceeded

Solution code:
from scipy.misc import comb


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 * (comb(n * m - 2, k - 2, exact=True) % (10**9 + 7)) % (10**9 + 7))


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

Submission status: Time Limit Exceeded

Solution code:
from operator import mul
from functools import reduce


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 * reduce(mul, range(n * m - k + 1, n * m - 1)) //
               reduce(mul, range(1, k - 1)) % (10**9 + 7) if k > 2 else base)


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

Submission status: Time Limit Exceeded

Solution code:
from scipy.misc import comb


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


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

Submission status: Time Limit Exceeded

Solution code:
from math import factorial as f
N, M, K = map(int, input().split())
mod = 10 ** 9 + 7

def combi(n, r):
  return f(n) // f(n - r) // f(r) % mod

res = 0
c = combi(N * M - 2, K - 2)
cn = c * M ** 2 % mod
cm = c * N ** 2 % mod
temp = ((N - 1 + 1) * (N - 1) // 2) * cn % mod
for i in range(1, N):
  res += temp % mod
  res %= mod
  temp -= (N - i) * cn % mod
#print(res)
temp = ((M - 1 + 1) * (M - 1) // 2) * cm % mod
for i in range(1, M):
  res += temp % mod
  res %= mod
  temp -= (M - i) * cm % mod

print(res % mod)

Submission status: Time Limit Exceeded

Solution code:
from math import factorial as f
N, M, K = map(int, input().split())
mod = 10 ** 9 + 7

def combi(n, r):
  return f(n) // f(n - r) // f(r) % mod

res = 0
c = combi(N * M - 2, K - 2)
for i in range(1, N):
  res += ((N - i + 1) * (N - i) // 2) * c * M * M % mod
  res %= mod

for i in range(1, M):
  res += ((M - i + 1) * (M - i) // 2) * c * N * N % mod
  res %= mod

print(res % mod)

Submission status: Time Limit Exceeded

Solution code:
from math import factorial as f
N, M, K = map(int, input().split())
mod = 10 ** 9 + 7

def combi(n, r):
  return f(n) // f(n - r) // f(r) % mod

res = 0
for i in range(1, N):
  res += ((N - i + 1) * (N - i) // 2) * combi(N * M - 2, K - 2) * M * M % mod
  res %= mod

for i in range(1, M):
  res += ((M - i + 1) * (M - i) // 2) * combi(N * M - 2, K - 2) * N * N % mod
  res %= mod

print(res % mod)

Submission status: Time Limit Exceeded

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

from fractions import Fraction

# 組合せの総数
def comb(n, k):
    
    if n < 0 or k < 0:
        pdt = 0
    
    else:
        pdt = 1
        for s in range(1, k + 1):
            pdt *= Fraction(n - s + 1, s)
    
    # 戻り値をint型にするために分子を取り出す
    return pdt.numerator


ans_x=0
ans_y=0

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

Submission status: Time Limit Exceeded

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

import math

from operator import mul
from functools import reduce
def combinations_count(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

ans_x = 0
c = combinations_count(N*M-2, K-2)
#for i in range(1, N+1):
#    ans_x += N*(N+1)//2-i*(i+1)//2-i*(N-i)
    #for j in range(i+1, N+1):
    #    ans_x += j-i
ans_x = (N*N*(N+1) + N*(N+1)*(2*N+1)//6 - (2*N+1)*N*(N+1)//2)//2
ans_x = M*M*ans_x*c

ans_y = 0
c = combinations_count(N*M-2, K-2)
#for i in range(1, M+1):
#    ans_y += M*(M+1)//2-i*(i+1)//2-i*(M-i)
    #for j in range(i+1, M+1):
    #    ans_y += j-i
ans_y = (M*M*(M+1) + M*(M+1)*(2*M+1)//6 - (2*M+1)*M*(M+1)//2)//2
ans_y = N*N*ans_y*c
ans = (ans_x+ans_y)%(10**9+7)
print(ans)

Submission status: Time Limit Exceeded

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

import math
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

ans_x = 0
c = combinations_count(N*M-2, K-2)
#for i in range(1, N+1):
#    ans_x += N*(N+1)//2-i*(i+1)//2-i*(N-i)
    #for j in range(i+1, N+1):
    #    ans_x += j-i
ans_x = (N*N*(N+1) + N*(N+1)*(2*N+1)//6 - (2*N+1)*N*(N+1)//2)//2
ans_x = M*M*ans_x*c

ans_y = 0
c = combinations_count(N*M-2, K-2)
#for i in range(1, M+1):
#    ans_y += M*(M+1)//2-i*(i+1)//2-i*(M-i)
    #for j in range(i+1, M+1):
    #    ans_y += j-i
ans_y = (M*M*(M+1) + M*(M+1)*(2*M+1)//6 - (2*M+1)*M*(M+1)//2)//2
ans_y = N*N*ans_y*c
ans = (ans_x+ans_y)%(10**9+7)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M, K = map(int, input().split())
import math
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

ans_x = 0
c = combinations_count(N*M-2, K-2)
for i in range(1, N+1):
    ans_x += N*(N+1)//2-i*(i+1)//2-i*(N-i)
    #for j in range(i+1, N+1):
    #    ans_x += j-i
ans_x = M*M*ans_x*c

ans_y = 0
c = combinations_count(N*M-2, K-2)
for i in range(1, M+1):
    ans_y += M*(M+1)//2-i*(i+1)//2-i*(M-i)
    #for j in range(i+1, M+1):
    #    ans_y += j-i
ans_y = N*N*ans_y*c
ans = (ans_x+ans_y)%(10**9+7)
print(ans)

Submission status: Time Limit Exceeded

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

import math
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

ans_x = 0
c = combinations_count(N*M-2, K-2)
for i in range(1, N+1):
    for j in range(i+1, N+1):
        ans_x += j-i
ans_x = M*M*ans_x*c

ans_y = 0
c = combinations_count(N*M-2, K-2)
for i in range(1, M+1):
    for j in range(i+1, M+1):
        ans_y += j-i
ans_y = N*N*ans_y*c
ans = (ans_x+ans_y)%(10**9+7)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#E問題
N,M,K = map(int,input().split())
mod = 1000000007

zen = 1
for i in range(N*M-2):
    zen*=(i+1)
kk = 1
for i in range(K-2):
    kk*=(i+1)
zk = 1
for i in range(N*M-K):
    zk*=(i+1)
    
C = zen//(kk*zk)


X = 0
for i in range(N-1):
    d = i+1
    X+=(N-d)*M*M*d
    X%=mod
Y = 0
for i in range(M-1):
    d = i+1
    Y+=(M-d)*N*N*d
    Y%=mod
print(C*(X+Y)%mod)

Submission status: Time Limit Exceeded

Solution code:
#E問題
N,M,K = map(int,input().split())
mod = 1000000007

#factorial(階乗)
def factorial(n):
    factorial_list=[]
    for i in range(n+1):
        if i == 0:
            factorial_list.append(1)
        elif i == 1:
            factorial_list.append(1)
        else:
            factorial_list.append(factorial_list[-1]*i)
    return factorial_list[-1]
#combination(組み合わせC)
def comb(comb1,comb2):
    x=min(comb1,comb2)
    y=max(comb1,comb2)
    bunshi=factorial(y)
    bunbo=factorial(x)*factorial(y-x)
    return bunshi//bunbo

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


X = 0
for i in range(N-1):
    d = i+1
    X+=(N-d)*M*M*d
    X%=mod
Y = 0
for i in range(M-1):
    d = i+1
    Y+=(M-d)*N*N*d
    Y%=mod
print(C*(X+Y)%mod)

Submission status: Time Limit Exceeded

Solution code:
from math import factorial

MOD = 10**9+7

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)%MOD)
# あるマンハッタン距離の時の配置の数

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
import math

N, M, K = [int(item) for item in input().split()]
mod = 10**9 + 7

total = 0
for d in range(1, N):
    score = (N - d) * M**2 * d
    score %= mod
    for i in range(2, K):
        score *= ((N * M - i) % mod * pow(K - i, mod - 2, mod))
        score %= mod
    total += score
    total %= mod

for d in range(1, M):
    score = (M - d) * N**2 * d
    score %= mod
    for i in range(2, K):
        score *= ((N * M - i) % mod * pow(K - i, mod - 2, mod))
        score %= mod
    total += score
    total %= mod


print(total)

Submission status: Time Limit Exceeded

Solution code:
import math
N,M,K = map(int,input().split())
pat = 1
for i in range(max(K-1,N*M-K+1),N*M-1):
    pat *= i
pat = pat // math.factorial(min(K-2,N*M-K))
pat = pat%(10**9+7)
ans_x,ans_y = 0,0
for i in range(M):
    ans_x =(ans_x + i*(M-i))%(10**9+7)
for i in range(N):
    ans_y =(ans_y + i*(N-i))%(10**9+7)
ans_x = (ans_x*(N**2))%(10**9+7)
ans_y = (ans_y*(M**2))%(10**9+7)
ans = (ans_x+ans_y)%(10**9+7)
ans = (ans*pat)%(10**9+7)
print(ans)

Submission status: Time Limit Exceeded

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

def comb(n, k):
    ret = 1
    for i in range(1, k + 1):
        ret = ret * (n - i + 1) % MOD        
        ret = ret * pow(i, MOD - 2, MOD) % MOD
        
    return ret

ans = 0
for d in range(N):
    ans += d * comb(N * M - 2, K - 2) * (N - d) * M ** 2
    ans %= MOD
    
for d in range(M):
    ans += d * comb(N * M - 2, K - 2) * (M - d) * N ** 2
    ans %= MOD
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,m,k=map(int,input().split())
mod=10**9+7
import math
def f(x):
  return math.factorial(x)
def c(x,y):
  return f(x)//(f(x-y)*f(y))

ans=(n**2*(m-1)*m*(m+1)//6)%mod
ans=(ans+m**2*(n-1)*n*(n+1)//6)%mod
ans=(ans*c(m*n-2,k-2))%mod
print(ans)

Submission status: Time Limit Exceeded

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

# 二項係数を 10^9+7 で割った余りを求める
# https://qiita.com/drken/items/3b4fdf0a78e7a138cd9a#5-%E4%BA%8C%E9%A0%85%E4%BF%82%E6%95%B0-ncr
# https://qiita.com/Yaruki00/items/fd1fc269ff7fe40d09a6
# https://www.hamayanhamayan.com/entry/2018/06/06/210256

mod = 10**9 + 7

# x ** a をmodで割った余りを、O(log(a))時間で求める。
def power(x, a):
	if a == 0:
		return 1
	elif a == 1:
		return x
	elif a % 2 == 0:
		return power(x, a//2) **2 % mod
	else:
		return power(x, a//2) **2 * x % mod

# xの逆元を求める。フェルマーの小定理より、 x の逆元は x ^ (mod - 2) に等しい。計算時間はO(log(mod))程度。
# https://qiita.com/Yaruki00/items/fd1fc269ff7fe40d09a6
def modinv(x):
	return power(x, mod-2)

# 二項係数の左側の数字の最大値を max_len　とする。nとかだと他の変数と被りそうなので。
# factori_table = [1, 1, 2, 6, 24, 120, ...] 要は factori_table[n] = n!
# 計算時間はO(max_len * log(mod))

max_len = n * m #適宜変更する

factori_table = [1] * (max_len + 1)
factori_inv_table = [1] * (max_len + 1)
for i in range(1, max_len + 1):
	factori_table[i] = factori_table[i-1] * (i) % mod
	factori_inv_table[i] = modinv(factori_table[i])

def binomial_coefficients(n, k):
	# n! / (k! * (n-k)! )
	return factori_table[n] * factori_inv_table[k] * factori_inv_table[n-k]

ans_1 = 0
for i in range(n):
	ans_1 += i * m**2 * (n-i)
for i in range(m):
	ans_1 += i * n**2 * (m-i)

print(binomial_coefficients(n*m-2, k-2) * ans_1 % mod)

Submission status: Time Limit Exceeded

Solution code:
import math
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

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

ans = 0
for i in range(0,N):
    for j in range(0,M):
        mul = 2
        if i == 0 or j == 0:
            mul = 1

        ans += mul * (N -i) * (M -j) * (i+j)

ans *= combinations_count(N*M-2,K-2)
ans %= 10**9 + 7
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math

N, M, K = (int(x) for x in input().split())

def nCm(n,m):
    if m < 0 or m > n:
        return 0
    nf = math.factorial(n)
    nm = math.factorial(m)
    nm2 = math.factorial(n-m)
    return (nf//nm//nm2) % 1000000007

c_sum = (M*(N-1)*N*(N+1)*M+N*(M-1)*M*(M+1)*N)//3
c_sum = c_sum//2
c_sum *= nCm(N*M-2, K-2)
c_sum = c_sum % 1000000007

print(c_sum)

Submission status: Time Limit Exceeded

Solution code:

import math

def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    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

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

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

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

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