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().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[N*M-2] %= 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: Time Limit Exceeded

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

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

Solution code:

mod = int(1e+9 + 7)

def power_mod(a, power):
    value = 1
    
    while power != 0:
        if power % 2 == 1:
            value = (value * a) % mod
            power -= 1
        a = (a * a) % mod
        power /= 2

    return value % mod

def combination(n, r):
    numerator = 1
    denomenator = 1

    for i in range(r):
        numerator *= n - i
        numerator %= mod
        denomenator *= power_mod(i + 1, mod - 2)
        denomenator %= mod
    
    return (numerator * denomenator) % mod

def main():
    inp = input().split(" ")
    N, M, K = int(inp[0]), int(inp[1]), int(inp[2])

    cost_x = 0
    cost_y = 0
    comb = combination(N * M - 2, K - 2)

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

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

    cost_x *= M * M
    cost_x %= mod
    cost_y *= N * N
    cost_y %= mod
    cost = (cost_x + cost_y) % mod

    print((cost * comb) % mod)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
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())
mod = 10**9 + 7

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

Submission status: Time Limit Exceeded

Solution code:
import sys
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def II(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def SI(): return input()
YN = lambda b: print('YES') if b else print('NO')
yn = lambda b: print('Yes') if b else print('No')

from scipy.misc import comb

def main():
    N, M, K = LI()

    rows = M*M*sum([d * (N-d) for d in range(1, N)])
    cols = N*N*sum([d * (M-d) for d in range(1, M)])
    ans = (rows + cols) * comb(M*N-2, K-2, exact=True) % MOD

    print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
import math

MOD = int(10**9 + 7)

def egcd(a, b):
    if a ==  0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b%a, a)
        return (g, x - (b//a) * y, y)

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception("No inverse exists")
    else:
        return x % m

def combination(n, r):
    return math.factorial(n) * modinv(math.factorial(r), MOD) * modinv(math.factorial(n-r), MOD)
    # return math.factorial(n) // math.factorial(r) // math.factorial(n-r)

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

ans = 0

k = combination(N*M-2, K-2)

for d in range(1, N):
    ans += d * k * M * M * (N - d)

for d in range(1, M):
    ans += d * k * N * N * (M - d)

print(ans % MOD)

Submission status: Time Limit Exceeded

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 *= (_N - i) % MAX
        low *= (i + 1) % MAX
    ret = up * mod_inv(low, MAX)
    if ret >= MAX:
        ret %= MAX
    return ret

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

if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

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 *= (_N - i) % MAX
        low *= (i + 1) % MAX
    ret = up * mod_inv(low, MAX)
    if ret >= MAX:
        ret %= 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)) * mod_inv(6, MAX)
    if disSum >= MAX:
        disSum %= MAX
    ret = disSum * combination(M*N-2, K-2)
    if ret >= MAX:
        ret %= MAX
    print ret

if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

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 *= (_N - i) % MAX
        low *= (i + 1) % MAX
    ret = up * mod_inv(low, MAX)
    if ret >= MAX:
        ret %= 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
    if disSum >= MAX:
        disSum %= MAX
    ret = disSum * combination(M*N-2, K-2)
    if ret >= MAX:
        ret %= MAX
    print ret

if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
MAX = 10**9 + 7

def combination(_N, _K):
    if _K > (_N/2):
        _K = _N - _K
    up = 1
    low = 1
    for i in range (_K):
        up *= (_N - i)
        low *= (i + 1)
    ret = up /low
    if ret >= MAX:
        ret %= 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
    if disSum >= MAX:
        disSum %= MAX
    ret = disSum * combination(M*N-2, K-2)
    if ret >= MAX:
        ret %= MAX
    print ret

if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
from operator import mul

MOD = 1000000007


def combination(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():
  N, M, K = [int(i) for i in input().strip().split(' ')]
  c = combination(N * M - 2, K - 2) % MOD

  X = sum([(M - i) * i for i in range(M)])
  Y = sum([(N - i) * i for i in range(N)])
  total = X * (N ** 2) + Y * (M ** 2) % MOD
  total = total * c % MOD
  print(total)


main()

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
from operator import mul

MOD = 1000000007


def combination(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():
  N, M, K = [int(i) for i in input().strip().split(' ')]
  c = combination(N * M - 2, K - 2) % MOD
  NNC = N * N % MOD
  MMC = M * M % MOD

  total = 0

  for i in range(M):
    total = (total + (M - i) * i * NNC) % MOD
  for i in range(N):
    total = (total + (N - i) * i * MMC) % MOD

  print(total * c % MOD)


main()

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
from operator import mul

MOD = 1000000007


def combination(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():
  N, M, K = [int(i) for i in input().strip().split(' ')]
  c = combination(N * M - 2, K - 2) % MOD
  NNC = N * N * c % MOD
  MMC = M * M * c % MOD

  total = 0
  MAX = max(M, N)
  for xy1 in range(MAX - 1):
    for xy2 in range(xy1 + 1, MAX):
      if xy2 < M:
        # diff * n_x1 * n_x2 * combination
        total = (total + (xy2 - xy1) * NNC) % MOD

      if xy2 < N:
        total = (total + (xy2 - xy1) * MMC) % MOD

  print(total)


main()

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
from operator import mul

MOD = 1000000007


def combination(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():
  N, M, K = [int(i) for i in input().strip().split(' ')]
  c = combination(N * M - 2, K - 2) % MOD

  total = 0
  MAX = max(M, N)
  for xy1 in range(MAX - 1):
    for x2 in range(xy1 + 1, M):
      # diff * n_x1 * n_x2 * combination
      total = (total + (x2 - xy1) * N * N * c) % MOD

    for y2 in range(xy1 + 1, N):
      total = (total + (y2 - xy1) * M * M * c) % MOD

  print(total)


main()

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
from operator import mul

MOD = 1000000007


def combination(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():
  N, M, K = [int(i) for i in input().strip().split(' ')]
  c = combination(N * M - 2, K - 2) % MOD

  total = 0
  for x1 in range(M - 1):
    for x2 in range(x1 + 1, M):
      dx = x2 - x1
      # diff * n_x1 * n_x2 * combination
      total += (x2 - x1) * N * N * c
      total %= MOD

  for y1 in range(N - 1):
    for y2 in range(y1 + 1, N):
      total += (y2 - y1) * M * M * c
      total %= MOD

  print(total)


main()

Submission status: Time Limit Exceeded

Solution code:
from itertools import product, combinations
N,M,K=map(int, raw_input().split())

mod=10**9+7
fact, inv_fact = [1], [1]
fact_tmp = 1
for i in range(1, N*M+1):
    fact_tmp *= i
    fact_tmp %= mod
    fact.append(fact_tmp)
    inv_fact.append(pow(fact_tmp, mod-2, mod))
 
 
def ncr(n,r):
	if n < 0 or r < 0 or n < r:	return 0
	else:	return (fact[n] * inv_fact[r] * inv_fact[n-r]) %mod


torisuu=ncr(N*M-2,K-2)
Zahyou=list( product(range(N), range(M)) )
Combi=list( combinations( range(N*M), 2) )


ans=0
for first, second in Combi:
	unit_cost=abs( Zahyou[second][0]-Zahyou[first][0] ) + abs(Zahyou[second][1]-Zahyou[first][1])
	unit_cost%=mod
	ans+=unit_cost*torisuu
	ans%=mod

print ans

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
from scipy.misc import*;n,m,k=map(int,input().split());s=lambda x,y:sum(y*y*i*(x-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: Time Limit Exceeded

Solution code:
from operator import mul
from functools import reduce

def comb(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 = 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%(1000000007)
print(ans)

Submission status: Time Limit Exceeded

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%(1000000007)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
LARGE = 10**9 + 7


def p_inv(k, p):
    return pow(k, p-2, p)


def nck_mod(n, k, m):
    res = 1
    for i in range(n, n-k, -1):
        res = res * i % m
    for i in range(1, k+1):
        res = res * p_inv(i, m) % m
    return res


def solve(n, m, k):
    res_1 = 0
    for i in range(n):
        for j in range(n):
            res_1 += abs(i - j)
    res_2 = 0
    for i in range(m):
        for j in range(m):
            res_2 += abs(i - j)
    res = (res_1 * m * m + res_2 * n * n) % LARGE

    weight = nck_mod(n * m - 1, k - 1, LARGE) * p_inv(n * m - 1, LARGE) * (k - 1) * p_inv(2, LARGE) % LARGE

    return res * weight % LARGE


if __name__ == "__main__":
    N, M, K = map(int, input().split())
    print(solve(N, M, K))
    # print(solve(2, 2, 2))
    # print(solve(4, 5, 4))
    # print(solve(100, 100, 5000))

Submission status: Time Limit Exceeded

Solution code:
from math import factorial

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

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

div_num = 10**9 + 7

cost = 0
def func(n,m,k):
    result = 0
    for d in range(1,n):
        select_2cell_cnt = (n-d)*(m**2)
        result += d * select_2cell_cnt * combinations_count(n*m-2,k-2)
        result = result % div_num
    
    return result % div_num

cost += func(N,M,K)
cost += func(M,N,K)

print(cost % div_num)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding utf-8 -*-
import math


def calc_C(n, r):
    return (math.factorial(n) // (math.factorial(n - r) * math.factorial(r))) % (10**9 + 7)


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

ans = 0

# row
for i in range(N):
    ans += i * (N - i) * M * M % (10**9 + 7)

# col
for i in range(M):
    ans += i * (M - i) * N * N % (10**9 + 7)

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding utf-8 -*-
import math


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


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

ans = 0

# row
for i in range(N):
    ans += i * (N - i) * M * M

# col
for i in range(M):
    ans += i * (M - i) * N * N

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

Submission status: Time Limit Exceeded

Solution code:
from math import factorial

def cmb(n,r):
    return int( factorial(n) // factorial(r) // factorial(n - r) )

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

ans = 0

for dx in range(1, n):
    ans += dx * (n-dx) * m**2

for dy in range(1, m):
    ans += dy * (m-dy) * n**2

mod = 10**9 + 7
pat = cmb(n*m-2 % mod, k-2)
ans = ans * pat
ans = ans % mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from math import factorial

def cmb(n,r):
    return int( factorial(n) // factorial(r) // factorial(n - r) )

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

ans = 0

for dx in range(1, n):
    ans += dx * (n-dx) * m**2

for dy in range(1, m):
    ans += dy * (m-dy) * n**2


pat = cmb(n*m-2, k-2)
ans = ans * pat
ans = ans % (10**9 + 7)
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())

ans = 0

for dx in range(1, n):
    ans += dx * (n-dx) * m**2

for dy in range(1, m):
    ans += dy * (m-dy) * n**2


pat = cmb(n*m-2, k-2)
ans = ans * pat
ans = ans % (10**9 + 7)
print(ans)

Submission status: Time Limit Exceeded

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

MOD = 10 ** 9 + 7

def combination(n, m):
    c = 1
    m = min(n-m, m)
    for i in range(m):
        c *= (n-i) * pow(m-i, MOD-2, MOD) % MOD
    return c

pattern = combination(N*M-2, K-2)

def diff_x_pattern(val):
    ret = 0
    for d in range(1, val):
        ret += ((val - d) * d) % MOD
    return ret

ans = (M * M * diff_x_pattern(N)) % MOD
ans += (N * N * diff_x_pattern(M)) % MOD
print((ans*pattern)%MOD)

Submission status: Time Limit Exceeded

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

MOD = 10 ** 9 + 7

fact = [1 for _ in range(N*M+1)]
for i in range(1, N*M+1):
    fact[i] = fact[i-1] * i

def inv(val):
    return pow(val, MOD-2, MOD)

def combination(n, m):
    return fact[n] * inv(fact[n-m]*fact[m]) % MOD

pattern = combination(N*M-2, K-2)

def diff_x_pattern(val):
    ret = 0
    for d in range(1, val):
        ret += ((val - d) * d) % MOD
    return ret

ans = (M * M * diff_x_pattern(N)) % MOD
ans += (N * N * diff_x_pattern(M)) % MOD
print((ans*pattern)%MOD)

Submission status: Time Limit Exceeded

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

MOD = 10 ** 9 + 7

fact = [1 for _ in range(N*M+1)]
for i in range(1, N*M+1):
    fact[i] = fact[i-1] * i

def inv(val):
    return pow(val, MOD-2, MOD)

def combination(n, m):
    return fact[n] * inv(fact[n-m]*fact[m]) % MOD

pattern = combination(N*M-2, K-2) % MOD

def diff_x_pattern(val):
    ret = 0
    for d in range(1, val):
        ret += ((val - d) * d) % MOD
    return ret

ans = (M * M * diff_x_pattern(N)) % MOD
ans += (N * N * diff_x_pattern(M)) % MOD
print((ans*pattern)%MOD)

Submission status: Time Limit Exceeded

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

MOD = 10 ** 9 + 7

fact = [1 for _ in range(N*M+1)]
for i in range(1, N*M+1):
    fact[i] = fact[i-1] * i

def inv(val):
    return pow(val, MOD-2, MOD)

def combination(n, m):
    return fact[n] * inv(fact[n-m]*fact[m]) % MOD

pattern = combination(N*M-2, K-2) % MOD

def diff_x_pattern(val):
    # for d in range(1, val):
    #     ret += (val - d) * d
    return (val * (val - 1) * val // 2 - (val - 1) * (2 * val - 1) * val // 6) % MOD

ans = (M * M * diff_x_pattern(N)) % MOD
ans += (N * N * diff_x_pattern(M)) % MOD
print((ans*pattern)%MOD)

Submission status: Time Limit Exceeded

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

MOD = 10 ** 9 + 7

def combination(n, m):
    m = min(m, n-m)
    c = 1
    for i in range(m):
        c *= (n-i) * pow(m-i, MOD-2, MOD) % MOD
    return c % MOD

pattern = combination(N*M-2, K-2) % MOD

def diff_x_pattern(val):
    # for d in range(1, val):
    #     ret += (val - d) * d
    return (val * (val - 1) * val // 2 - (val - 1) * (2 * val - 1) * val // 6) % MOD

ans = (M * M * diff_x_pattern(N)) % MOD
ans += (N * N * diff_x_pattern(M)) % MOD
print((ans*pattern)%MOD)

Submission status: Time Limit Exceeded

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

MOD = 10 ** 9 + 7

def combination(n, m):
    m = min(m, n-m)
    c = 1
    for i in range(m):
        c *= n - i
    for i in range(2, m+1):
        c //= i
    return c % MOD

pattern = combination(N*M-2, K-2) % MOD

def diff_x_pattern(val):
    # for d in range(1, val):
    #     ret += (val - d) * d
    return (val * (val - 1) * val // 2 - (val - 1) * (2 * val - 1) * val // 6) % MOD

ans = (M * M * diff_x_pattern(N)) % MOD
ans += (N * N * diff_x_pattern(M)) % MOD
print((ans*pattern)%MOD)

Submission status: Time Limit Exceeded

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

MOD = 10 ** 9 + 7

NM = N * M

fact = [1 for _ in range(NM+1)]
for i in range(1, NM+1):
    fact[i] = fact[i-1] * i

def combination(n, m):
    return fact[n] // fact[n-m] //fact[m]

pattern = combination(NM-2, K-2) % MOD

def diff_x_pattern(val):
    # for d in range(1, val):
    #     ret += (val - d) * d
    return val * (val - 1) * val // 2 - (val - 1) * (2 * val - 1) * val // 6

ans = M * M * diff_x_pattern(N)
ans += N * N * diff_x_pattern(M)
print((ans*pattern)%MOD)

Submission status: Time Limit Exceeded

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

MOD = 10 ** 9 + 7

def combination(n, m):
    c = 1
    for i in range(m):
        c *= n-i
    for i in range(1, m+1):
        c //= i
    return c

pattern = combination(M*N-2, K-2) % MOD

ans = 0
for d in range(1, N):
    ans += M * M * (N - d) * d
for d in range(1, M):
    ans += N * N * (M - d) * d
print((ans*pattern)%MOD)

Submission status: Time Limit Exceeded

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

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

def Combi2(a,b):#aは大きいが、bは小さいとき
    if b>a:
        return 0
    ANS=1
    for i in range(min(b,a-b)):
        ANS=ANS*(a-i)*pow(min(b,a-b)-i,mod-2,mod)

    return ANS%mod

SUM_N=SUM_M=0
for i in range(N):
    SUM_N+=i*(N-i)

for i in range(M):
    SUM_M+=i*(M-i)

#print((SUM_N*(M**2)+SUM_M*(N**2))/Combi2(N*M,2)*Combi2(N*M,K)*K*(K-1)//2%mod)
print((SUM_N*(M**2)+SUM_M*(N**2))*pow(Combi2(N*M,2),mod-2,mod)*Combi2(N*M,K)*K*(K-1)*pow(2,mod-2,mod)%mod)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
mod = 10 ** 9 + 7
n, m, k = map(int, input().split())
nm = n * m
fact = [1] * (nm + 1)

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


def C(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(x):
    s1 = x * x * (x + 1) // 2
    s2 = x * (x + 1) * (2 * x + 1) // 6
    return (s1 - s2) % mod


res = (m ** 2 % mod * F(n) % mod + n ** 2 * F(m) % mod) % mod
res *= C(n * m - 2, k - 2)
res %= mod
print(res)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
mod = 10 ** 9 + 7
n, m, k = map(int, input().split())
nm = n * m
fact = [1] * (nm + 1)

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


def C(n, k):
    x = fact[n]
    x *= pow(fact[n-k], mod - 2, mod)
    x *= pow(fact[k], mod - 2, mod)
    return x


def F(x):
    s1 = x * x * (x + 1) // 2
    s2 = x * (x + 1) * (2 * x + 1) // 6
    return (s1 - s2)


res = (m ** 2 * F(n) + n ** 2 * F(m))
res *= C(n * m - 2, k - 2)
print(res % mod)

Submission status: Time Limit Exceeded

Solution code:
mod = 10**9 + 7

def comb(n, k):
    x, y = 1, 1
    k = min(k, n-k)
    for i in range(k):
        x *= n - i
        y *= i + 1
    return x*pow(y, mod-2, mod) % mod

N, M, K = map(int, input().split())
print((sum(i*(N-i)*M**2 for i in range(N))+sum(i*(M-i)*N**2 for i in range(M)))*comb(N*M-2, K-2) % mod)

Submission status: Time Limit Exceeded

Solution code:
import math

inf = 7 + (10 ** 9)

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

n, m, k = map(int, input().split())
ans = 0
comb = ((combinations_count((n * m) - 2, k - 2)))
n_2 = (n * n * comb) % inf
m_2 = (m * m * comb) % inf
k_m = ((m * (m - 1) * (m + 1)) // 6) % inf
k_n = ((n * (n - 1) * (n + 1)) // 6) % inf
ans = (k_m * n_2) + (k_n * m_2)
ans = ans % inf
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from scipy.misc import comb

MAX = 10**9 + 7

def man_comb(_N, _K):
    if _K > (_N/2):
        return comb(_N, _N - _K, exact=True)
    else:
        return comb(_N, _K, exact=True)

def combination(_N, _K):
    if _K > (_N/2):
        _K = _N - _K
    up = 1
    low = 1
    for i in range (_K):
        up *= (_N - i)
        low *= (i + 1)
    ret = up /low
    if ret >= MAX:
        ret %= 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
    if disSum >= MAX:
        disSum %= MAX
    ret = disSum * combination(M*N-2, K-2)
    if ret >= MAX:
        ret %= MAX
    print ret

if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
from math import factorial

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

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

div_num = 10**9 + 7

cost = 0
def func(n,m,k):
    result = 0
    for d in range(1,n):
        select_2cell_cnt = (n-d)*(m**2)
        result += d * select_2cell_cnt * combinations_count(n*m-2,k-2)
    
    return result % div_num

cost += func(N,M,K)
cost += func(M,N,K)

print(cost % div_num)

Submission status: Time Limit Exceeded

Solution code:
import math

inf = 7 + (10 ** 9)

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

n, m, k = map(int, input().split())
ans = 0
comb = ((combinations_count((n*m)-2, k-2)))
n_2 = (n * n * comb) % inf
m_2 = (m * m * comb) % inf
k_m = (((m * m * (m - 1)) // 2) - (((m - 1) * m * ((2 * m) - 1)) // 6)) % inf
k_n = (((n * n * (n - 1)) // 2) - (((n - 1) * n * ((2 * n) - 1)) // 6)) % inf
ans = (k_m * n_2) + (k_n * m_2)
ans = ans % inf
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math

inf = 7 + (10 ** 9)

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

n, m, k = map(int, input().split())
ans = 0
comb = ((combinations_count((n*m)-2, k-2)))
n_2 = (n * n * comb) % inf
m_2 = (m * m * comb) % inf
k_m = 0
k_n = 0
for i in range(1, m):
    k_m += (i) * (m - i)
for i in range(1, n):
    k_n += (i) * (n - i)
ans = (k_m * n_2) + (k_n * m_2)
ans = ans % inf
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
N,M,K=map(int,input().split())
xs=0
ys=0
inf=10**9+7
xs=(M*(M+1)*(2*M+1) - 3*M*(M+1))//12
ys=(N*(N+1)*(2*N+1) - 3*N*(N+1))//12
#for i in range(1,M):
	#xs+=i*(M-i)
	#xs = xs % inf
#for i in range(1,N):
	#ys+=i*(N-i)
	#ys = ys % inf
xs*=(N**2)
xs = xs % inf
ys*=(M**2)
ys = ys % inf

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

def comb_new(n,r):
	inf = 10**9+7
	loop = n//inf
	amari = n % inf
	if loop:
		y = 1
		for i in range(r):
			y *= n-i
		return y//math.factorial(r)
	else:
		y = 1
		for i in range(r):
			y *= n-i
		return y//math.factorial(r)


#c = comb(N*M-2,K-2) % inf
c = comb_new(N*M-2,K-2) % inf
print(((xs+ys)*c)%inf)

Submission status: Time Limit Exceeded

Solution code:
import math

inf = 7 + (10 ** 9)

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

n, m, k = map(int, input().split())
ans = 0
comb = ((combinations_count((n*m)-2, k-2)))
n_2 = (n * n * comb) % inf
m_2 = (m * m * comb) % inf
for i in range(1, m):
    ans += (( n_2 * (i)) * (m - i)) % inf
    ans = ans % inf
for i in range(1, n):
    ans += (m_2 * (i) * (n - i)) % inf
    ans = ans % inf
ans = ans % inf
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from scipy.misc import comb

MAX = 10**9 + 7

def man_comb(_N, _K):
    if _K > (_N/2):
        return comb(_N, _N - _K, exact=True)
    else:
        return comb(_N, _K, exact=True)

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
    if disSum >= MAX:
        disSum %= MAX
    ret = disSum * man_comb(M*N-2, K-2)
    if ret >= MAX:
        ret %= MAX
    print ret

if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

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


mod = 10 ** 9 + 7
MAX = N*M
fac = [0] * MAX
finv = [0] * MAX
inv = [0] * MAX

def cominit():
    fac[0] = 1
    fac[1] = 1
    finv[0] = 1
    finv[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 cmb(n,r):
    if n < 0 or r < 0 or r > n:return 0
    if r > n/2: r = n-r        
    return fac[n] * (finv[r] * finv[n-r] % mod) % mod
    
cominit()
ans= 0
NCK = cmb(N*M-2,K-2) 
M2 = M**2 * NCK
N2 = N**2 * NCK
for i in range(N-1):
    for j in range(i,N):
        ans += M2 * (j-i) 
        ans %= mod
        
for i in range(M-1):
    for j in range(i,M):
        ans += N2 * (j-i) 
        ans %= mod
        
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math

inf = 7 + (10 ** 9)

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

n, m, k = map(int, input().split())
ans = 0
comb = ((combinations_count((n*m)-2, k-2)))
n_2 = (n * n) % inf
m_2 = (m * m) % inf
for i in range(1, m):
    ans += ((comb * n_2 * (i)) * (m - i)) % inf
    ans = ans % inf
for i in range(1, n):
    ans += (comb * m_2 * (i) * (n - i)) % inf
    ans = ans % inf
ans = ans % inf
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math

inf = 7 + (10 ** 9)

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

n, m, k = map(int, input().split())
ans = 0
comb = ((combinations_count((n*m)-2, k-2)))
for i in range(1, m):
    ans += ((comb * n * n * (i)) * (m - i)) % inf
    ans = ans % inf
for i in range(1, n):
    ans += (comb * m * m * (i) * (n - i)) % inf
    ans = ans % inf
ans = ans % inf
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math

inf = 7 + (10 ** 9)

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


def permutations_count(n, r):
    return math.factorial(n) // math.factorial(n - r)


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

Submission status: Time Limit Exceeded

Solution code:
import math

inf = 7 + (10 ** 9)

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


def permutations_count(n, r):
    return math.factorial(n) // math.factorial(n - r)


n, m, k = map(int, input().split())
ans = 0
for i in range(m-1):
    for j in range(i+1, m):
        ans += (combinations_count((n*m)-2, k-2) * n * n * (j - i))
        ans = ans % inf
for i in range(n-1):
    for j in range(i+1, n):
        ans += combinations_count((n*m)-2, k-2) * m * m * (j - i)
        ans = ans % inf
ans = ans % inf
print(ans)