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:
#!/usr/bin/python3
# -*- coding: utf-8 -*-


MOD = 10**9+7
Facts = [1]*(2*10**5+1)
for i in range(2,2*10**5+1):
  Facts[i] = (Facts[i-1]*i) % MOD

def mul(a,b):
  return (a*b) % MOD

def power(a,b):
  if   b==0   : return 1
  elif b==1   : return a % MOD
  elif b%2==0 : return power(a,b//2)**2 % MOD
  else        : return power(a,b//2)**2 * a % MOD

def div(a,b):
  return mul(a,power(b,MOD-2))


def combi(n,m,k):
  if k <= 2 or k >= n*m:
    return 1
  else:
    return div(Facts[n*m-2],(Facts[k-2]*Facts[n*m-k]))


def main():
  N,M,K = map(int, input().split())
  ans = 0
  for d in range(1,N):
    ans = (ans + d * (N-d)*M**2 * combi(N,M,K)) % MOD
  for d in range(1,M):
    ans = (ans + d * (M-d)*N**2 * combi(N,M,K)) % MOD
  return ans

if __name__ == "__main__":
  print(main())

Submission status: Time Limit Exceeded

Solution code:
import sys
from math import factorial

input = sys.stdin.readline

Mod = 10**9 + 7


def Cmb(n, k):
    return factorial(n) // (factorial(n - k) * factorial(k)) % Mod


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

ans = 0

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

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

ans *= Cmb(n * m - 2, k - 2)
ans %= Mod

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from math import factorial

Mod = 10**9 + 7


def Cmb(n, k):
    return factorial(n) // (factorial(n - k) * factorial(k)) % Mod


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

ans = 0

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

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

ans *= Cmb(n * m - 2, k - 2)
ans %= Mod

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def combination(n, r):
    r = min(n - r, r)
    result = 1
    for i in range(n, n - r, -1):
        result *= i
    for i in range(1, r + 1):
        result //= i
    return result


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

NM = N * M
fa = [1] * (NM + 1)

for i in range(1, NM + 1):
    fa[i] = (fa[i - 1] * i) % mod

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

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

ans *= combination(NM-2, K-2)
ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def combination(n, r):
    r = min(n - r, r)
    result = 1
    for i in range(n, n - r, -1):
        result *= i
    for i in range(1, r + 1):
        result //= i
    return result


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

NM = N * M
fa = [1] * (NM + 1)

for i in range(1, NM + 1):
    fa[i] = (fa[i - 1] * i) % mod

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

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

ans *= combination(NM-2, K-2)
ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def combination(n, r):
    r = min(n - r, r)
    result = 1
    for i in range(n, n - r, -1):
        result *= i
    for i in range(1, r + 1):
        result //= i
    return result


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

NM = N * M
fa = [1] * (NM + 1)

for i in range(1, NM + 1):
    fa[i] = fa[i - 1] * i
    fa[i] %= mod

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

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

ans *= combination(NM-2, K-2)
ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from math import factorial
mod=10**9+7
def cmb(n, r):
    return factorial(n) // factorial(r) // factorial(n - r)%mod

n,m,k=map(int,input().split())
print(((pow(m,2,mod)*cmb(n*m-2,k-2)*sum((n-i)*i%mod for i in range(1,n))%mod)+pow(n,2,mod)*cmb(n*m-2,k-2)*sum((m-i)*i%mod for i in range(1,m))%mod)%mod)

Submission status: Time Limit Exceeded

Solution code:
from math import factorial
mod=10**9+7
def cmb(n, r):
    return factorial(n) // factorial(r) // factorial(n - r)%mod

n,m,k=map(int,input().split())
print(((pow(m,2,mod)*cmb(n*m-2,k-2)*sum((n-i)*i for i in range(1,n)))+pow(n,2,mod)*cmb(n*m-2,k-2)*sum((m-i)*i for i in range(1,m)))%mod)

Submission status: Time Limit Exceeded

Solution code:
import math
N,M,k = map(int,input().split())
p = N*M
PP = 1
for i in range(p-k+1,p-1):
    PP *= i
P = PP//math.factorial(k-2)
    
Q = N*(N-1)*(N+1)*M*M//6
R = M*(M-1)*(M+1)*N*N//6
print((P*(Q+R))%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
import math
N,M,k = map(int,input().split())
p = N*M
X = math.factorial(p-2)
Y = math.factorial(p-k)
Z = math.factorial(k-2)
P = X//(Y*Z)
Q = N*(N-1)*(N+1)*M*M//6
R = M*(M-1)*(M+1)*N*N//6
print((P*(Q+R))%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/abc127/tasks/abc127_e

import itertools
from collections import Counter
from collections import defaultdict
import bisect
import math

# Calculate count of combination
def combination(n, r):
    if r == 0:
        return 1
    a = 1
    b = 1
    for i in range(r):
        a *= (n - i)
        if a % (i + 1):
            a //= (i + 1)
        else:
            b *= (i + 1)
    return a // b


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

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

    ans = 0

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

    # y
    for dy in range(1, N):
        ans += dy * (N - dy) * pattern * (M * M)
        ans = ans % MOD

    ans = ans % MOD
    print(ans)



if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def combi(n, r) :
    ret = 1
    for i in range(n, n-r, -1) :
        ret *= i
        while r > 1 and ret % r == 0 :
            ret //= r
            r -= 1

    return ret

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

n, r = N * M - 2, K - 2
P = combi(n, r) % MOD

ans = 0
for n in range(N) :
    for m in range(M) :
        if n == 0 and m == 0 :
            continue

        d = n + m
        cnt = (N - n) * (M - m) * (1 if n == 0 or m == 0 else 2)

        ans += d * cnt * P
        ans %= MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def combi(n, r) :
    ret = 1
    for i in range(n, n-r, -1) :
        ret *= i
    for i in range(r, 0, -1) :
        ret //= i
    return ret

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

n, r = N * M - 2, K - 2
P = combi(n, r) % MOD

ans = 0
for n in range(N) :
    for m in range(M) :
        if n == 0 and m == 0 :
            continue

        d = n + m
        cnt = (N - n) * (M - m) * (1 if n == 0 or m == 0 else 2)

        ans += d * cnt * P
        ans %= MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from math import factorial

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

n, r = N * M - 2, K - 2
P = factorial(n) // factorial(n-r) // factorial(r) % MOD

ans = 0
for n in range(N) :
    for m in range(M) :
        if n == 0 and m == 0 :
            continue

        d = n + m
        cnt = (N - n) * (M - m) * (1 if n == 0 or m == 0 else 2)

        ans += d * cnt * P
        ans %= MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from math import factorial

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

n, r = N * M - 2, K - 2
P = factorial(n) // factorial(n-r) // factorial(r)

ans = 0
for n in range(N) :
    for m in range(M) :
        if n == 0 and m == 0 :
            continue

        d = n + m
        cnt = (N - n) * (M - m) * (1 if n == 0 or m == 0 else 2)

        ans += d * cnt * P

ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def comb(n, k):
    x, y = 1, 1
    if 2*k > n:
        k = n - k
    for i in range(k):
        x *= n - i
        y *= i + 1
    return x//y

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) % (10**9+7))

Submission status: Time Limit Exceeded

Solution code:
from scipy.misc import comb

MAX = 10**9 + 7

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 * comb(M*N-2, K-2, exact=True)
    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

def powmod(x, n):
  ret = 1
  while n > 0:
    if n & 1:
      ret *= x; ret %= mod; n -= 1
    else:
      x *= x; x %= mod; n >>= 1
  return ret

fact = [1 for _ in range(200010)]
revfact = [1 for _ in range(200010)]

def setfact(n):
  for i in range(n):
    fact[i+1] = fact[i] * (i+1); fact[i+1] %= mod
  revfact[n] = powmod(fact[n], mod-2)
  for i in range(n):
    revfact[n-i-1] = revfact[n-i] * (n-i); revfact[i] %= mod
  return

def getC(n, r):
  return fact[n] * revfact[r] % mod * revfact[n-r] % mod
  
setfact(n*m)
ans = 0
for i in range(m):
    ans += n*n*(m-i)*i
    ans %= mod
for i in range(n):
    ans += m*m*(n-i)*i
    ans %= mod
print(ans * getC(n*m-2, k-2) % mod)

Submission status: Time Limit Exceeded

Solution code:
import math
N,M,K = map(int,input().split())
pat = math.factorial(N*M-2) // (math.factorial(K-2)*math.factorial(N*M-K))
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())
ans = 0
MOD = 10**9+7
from scipy.misc import comb
C = comb(m*n-2,k-2,exact=True)%MOD
for i in range(1,n):
    ans += (i*(n-i)*(m**2))*C
for i in range(1,m):
    ans += (i*(m-i)*(n**2))*C
print(ans%MOD)

Submission status: Time Limit Exceeded

Solution code:
import itertools
from copy import deepcopy

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

def dist(komas):
    total = 0
    for koma1, koma2 in itertools.combinations(komas, 2):
        total += abs(koma1 // M - koma2 // M) + abs(koma1 % M - koma2 % M)
    return total

total = 0
for komas in itertools.combinations(range(N * M), K):
    total += dist(komas)

print(total % 1000000007)

Submission status: Time Limit Exceeded

Solution code:
n,m,k = map(int,input().split())
ans = 0
MOD = 10**9+7
for i in range(1,n):
    ans += (i*(n-i)*(m**2))%MOD
    ans %= MOD
for i in range(1,m):
    ans += (i*(m-i)*(n**2))%MOD
    ans %= MOD
from scipy.misc import comb
print((ans*comb(m*n-2,k-2,exact=True))%MOD)

Submission status: Time Limit Exceeded

Solution code:
n,m,k = map(int,input().split())
ans = 0
MOD = 10**9+7
for i in range(1,n):
    ans += i*(n-i)*(m**2)
for i in range(1,m):
    ans += i*(m-i)*(n**2)
from scipy.misc import comb
print((ans*comb(m*n-2,k-2,exact=True))%MOD)

Submission status: Time Limit Exceeded

Solution code:
import math
n,m,k=map(int,input().split())
mod=10**9+7
s=math.factorial(n*m-2)//(math.factorial(n*m-k)*math.factorial(k-2))
cnt=0
s%=mod
a=(m*m*s)%mod
for d in range(1,n):
        cnt+=d*(n-d)*a
        cnt%=mod
a=(n*n*s)%mod
for d in range(1,m):
        cnt+=d*(m-d)*a
        cnt%=mod
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import math
n,m,k=map(int,input().split())
mod=10**9+7
s=math.factorial(n*m-2)//(math.factorial(n*m-k)*math.factorial(k-2))
cnt=0
s%=mod
for d in range(1,n):
        cnt+=d*(n-d)*m*m*s
        cnt%=mod
for d in range(1,m):
        cnt+=d*(m-d)*n*n*s
        cnt%=mod
print(cnt)

Submission status: Time Limit Exceeded

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

def expo_div_p(a: int,n: int,p: int):
    if n == 1:
        d = a
    elif n % 2 == 0:
        d = expo_div_p(a, n//2, p)**2 % p
    else:
        d = a * expo_div_p(a, n//2, p)**2 % p
    return d

def combi(x, y, p):
    c = 1
    for i in range(1,y+1):
        c *= (x-i+1) * expo_div_p(i, p-2, p)
        c %= p
    return c

ans = 0
C = 0
C += combi(N*M-2, K-2, ppp)

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

#print(C)
print(ans % ppp)

Submission status: Time Limit Exceeded

Solution code:
def reduce_mul(s,e):
     a = 1
     for i in range(s,e+1):
          a = a*i
     return a
     
def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce_mul(n-r+1,n)
    under = reduce_mul(1,r)
    return over // under

n,m,k = map(int,input().split())
nm = n*m%(10**9+7)
k = k%(10**9+7)
a = (cmb(nm-2,k-2)%(10**9+7))*(nm*(m*(n**2-1)+n*(m**2-1)))//6
print(a%(10**9+7))

Submission status: Time Limit Exceeded

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

def expo_div_p(a: int,n: int,p: int):
    if n == 1:
        d = a
    elif n % 2 == 0:
        d = expo_div_p(a, n//2, p)**2 % p
    else:
        d = a * expo_div_p(a, n//2, p)**2 % p
    return d

def combi(x, y, p):
    c = 1
    for i in range(1,y+1):
        c *= (x-i+1) * expo_div_p(i, p-2, p)
        c %= p
    return c

ans = 0
C = combi(N*M-2, K-2, ppp)

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

#print(C)
print(ans % ppp)

Submission status: Time Limit Exceeded

Solution code:
def reduce_mul(s,e):
     a = 1
     for i in range(s,e+1):
          a = a*i
     return a
     
def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce_mul(n-r+1,n)
    under = reduce_mul(1,r)
    return over // under

n,m,k = map(int,input().split())
a = (cmb(n*m-2,k-2)%(10**9+7))*(n*m*(m*(n**2-1)+n*(m**2-1)))//6
print(a%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
N,M,K=map(int, input().split())
div=10**9+7
def ncr(n, r):
    res = 1
    for i in range(1, r+1):
        res = res*n//i
        n = n-1
    return res % div

result = 0
comb = ncr(N*M-2, K-2)
for d in range(1, N):
    result += d*comb*M*M*(N-d)

for d in range(1, M):
    result += d*comb*(M-d)*N*N

print(result % div)

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

def main():
     n,m,k = map(int,input().split())
     a = (cmb(n*m-2,k-2)%(10**9+7))*(n*m*(m*(n**2-1)+n*(m**2-1)))//6
     print(a%(10**9+7))
     return 0

if __name__=="__main__":
     main()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
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

def main():
     n,m,k = [int(x) for x in stdin.readline().split()]
     a = cmb(n*m-2,k-2)*n*m*(m*(n**2-1)+n*(m**2-1))
     a = a//6
     a = a%(10**9+7)
     print(a)
     return

if __name__=="__main__":
     main()

Submission status: Time Limit Exceeded

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

MOD = 10**9+7

def comb(n, r):
    r = n-r if n-r < r else r
    if r == 0:
        return 1
    ndfact = 1
    for i in range(n, n-r, -1):
        ndfact *= i
    return ndfact // factorial(r)

p = comb(N*M-2, K-2) % MOD
ans = 0
for i in range(N):
    for j in range(M):
        if i == 0 and j == 0:
            continue
        d = i+j
        cnt = (N-i) * (M-j)
        if i != 0 and j != 0:
            cnt *= 2
        ans += d * cnt
        ans %= MOD

print((ans*p)%MOD)

Submission status: Time Limit Exceeded

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

MOD = 10**9+7

def comb(n, r):
    r = n-r if n-r < r else r
    if r == 0:
        return 1
    ndfact = 1
    for i in range(n, n-r, -1):
        ndfact *= i
    return ndfact // factorial(r)

p = comb(N*M-2, K-2)
ans = 0
for i in range(N):
    for j in range(M):
        if i == 0 and j == 0:
            continue
        d = i+j
        #print(i, j, calc_rec_num(N, M, 0, 0, i, j))
        cnt = (N-i) * (M-j)
        if i != 0 and j != 0:
            cnt *= 2
        ans += d * cnt
        #if ans > DIV:
        #    ans %= DIV
        #print(ans)

print((ans*p)%MOD)

Submission status: Time Limit Exceeded

Solution code:
import math

dp = [0 for _ in range(2*10**5+1)]
f = math.factorial
def fact(n):
    if n == 0:
        return 1
    if dp[n] != 0:
        return dp[n]
    else:
        fn = f(n)
        dp[n] = fn
        return fn

def nCr(n,r):
    return fact(n) // fact(r) // fact(n-r)

def distancesum(arr, n): 
      
    # sorting the array. 
    arr.sort() 
      
    # for each point, finding  
    # the distance. 
    res = 0
    sum = 0
    for i in range(n): 
        res += (arr[i] * i - sum) 
        sum += arr[i] 
      
    return res 

flatten = lambda x: [z for y in x for z in (flatten(y) if hasattr(y, '__iter__') and not isinstance(y, str) else (y,))]

div = 10**9 + 7

N, M, K = map(int, input().split())
repeat = nCr(N*M-2, K-2)
f_row = flatten([[i for _ in range(M)] for i in range(N)])
f_col = flatten([[i for i in range(M)] for _ in range(N)])

manhsum = distancesum(f_row, len(f_row)) + distancesum(f_col, len(f_col))
print(((repeat % div) * (manhsum % div))%div)

Submission status: Time Limit Exceeded

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

n = 5 * 10**5 
fac = [1] + [0] * n
fac_inv = [1] + [0] * n
for i in range(1, n+1):
    fac[i] = fac[i-1] * (i) % MOD
    # Fermat's little theorem says
    # a**(p-1) mod p == 1
    # then, a * a**(p-2) mod p == 1
    # it means a**(p-2) is inverse element
    fac_inv[i] = fac_inv[i-1] * pow(i, MOD-2, MOD) % MOD

def mod_nCr(n, r):
    if n == 0 and r == 0:
        return 1
    if n < r or n < 0:
        return 0
    tmp = fac_inv[n-r] * fac_inv[r] % MOD
    return tmp * fac[n] % MOD 

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

Submission status: Time Limit Exceeded

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

MOD = 10**9+7
fact = [1 for i in range(N*M+1)]
for i in range(2, N*M+1):
    fact[i] = fact[i-1] * i

def comb(n, r):
    if n == 0 or r == 0:
        return 1
    return fact[n] // fact[n-r] // fact[r]

p = comb(N*M-2, K-2)
ans = 0
for i in range(N):
    for j in range(M):
        if i == 0 and j == 0:
            continue
        d = i+j
        #print(i, j, calc_rec_num(N, M, 0, 0, i, j))
        cnt = (N-i) * (M-j)
        if i != 0 and j != 0:
            cnt *= 2
        ans += d * cnt
        #if ans > DIV:
        #    ans %= DIV
        #print(ans)

print((ans*p)%MOD)

Submission status: Time Limit Exceeded

Solution code:
n,m,k=map(int,input().split())
ans=0
INF=10**9+7
if n<=m:
    M=-(m-1)*m*(2*m-1)//3+m*m*(m-1)
    Ms=m*m*(m-1)//2-(m-1)*m*(2*m-1)//6
    M=M%INF
    Ms=Ms%INF
    for i in range(1,n+1):
        for j in range(i,n+1):
            if i==j:
                ans=ans+Ms
            else:
                d=j-i
                ans=ans+d*m**2+M
            ans=ans%INF
else:
    (n,m)=(m,n)
    M=-(m-1)*m*(2*m-1)//3+m*m*(m-1)
    Ms=m*m*(m-1)//2-(m-1)*m*(2*m-1)//6
    M=M%INF
    Ms=Ms%INF
    for i in range(1,n+1):
        for j in range(i,n+1):
            if i==j:
                ans=ans+Ms
            else:
                d=j-i
                ans=ans+d*m**2+M
            ans=ans%INF
a=1
b=1
c=n*m-2
x=min(c,k-2)
for i in range(x):
    a=a*(c-i)
    b=b*(i+1)
ans=(ans*a//b)%INF
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,m,k=map(int,input().split())
ans=0
INF=10**9+7
if n<=m:
    M=-(m-1)*m*(2*m-1)//3+m*m*(m-1)
    Ms=m*m*(m-1)//2-(m-1)*m*(2*m-1)//6
    M=M%INF
    Ms=Ms%INF
    for i in range(1,n+1):
        for j in range(i,n+1):
            if i==j:
                ans=ans+Ms
            else:
                d=j-i
                ans=ans+d*m**2+M
            ans=ans%INF
else:
    (n,m)=(m,n)
    M=-(m-1)*m*(2*m-1)//3+m*m*(m-1)
    Ms=m*m*(m-1)//2-(m-1)*m*(2*m-1)//6
    M=M%INF
    Ms=Ms%INF
    for i in range(1,n+1):
        for j in range(i,n+1):
            if i==j:
                ans=ans+Ms
            else:
                d=j-i
                ans=ans+d*m**2+M
            ans=ans%INF
a=1
b=1
x=min(n*m-2,k-2)
for i in range(x):
    a=a*(n*m-2-i)
    b=b*(i+1)
ans=(ans*a//b)%INF
print(ans)

Submission status: Time Limit Exceeded

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

MOD = 10**9+7
fact = [1 for i in range(N*M+1)]
for i in range(2, N*M+1):
    fact[i] = fact[i-1] * i

def comb(n, r):
    return fact[n] // fact[n-r] // fact[r]

p = comb(N*M-2, K-2)
ans = 0
for i in range(N):
    for j in range(M):
        if i == 0 and j == 0:
            continue
        d = i+j
        #print(i, j, calc_rec_num(N, M, 0, 0, i, j))
        cnt = (N-i) * (M-j)
        if i != 0 and j != 0:
            cnt *= 2
        ans += d * cnt
        #if ans > DIV:
        #    ans %= DIV
        #print(ans)

print((ans*p)%MOD)

Submission status: Time Limit Exceeded

Solution code:
from math import factorial

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

DIV = 10**9+7

#def comb(l, r):
#    if l == 0:
#        return 1
#    val = 1
#    for i in range(r, r-l, -1):
#        val *= i
#    for i in range(l, 0, -1):
#        val //= i
#    return val

#p = comb(K-2, N*M-2)
p = factorial(N*M-2) // factorial(K-2) // factorial((N*M-2) - (K-2))
#print(K-2, N*M-2, p)
ans = 0
for i in range(N):
    for j in range(M):
        if i == 0 and j == 0:
            continue
        d = i+j
        #print(i, j, calc_rec_num(N, M, 0, 0, i, j))
        cnt = (N-i) * (M-j)
        if i != 0 and j != 0:
            cnt *= 2
        ans += d * cnt
        #if ans > DIV:
        #    ans %= DIV
        #print(ans)

print((ans*p)%DIV)

Submission status: Time Limit Exceeded

Solution code:
import math


def combi(n, k):
    ret = math.factorial(n) // math.factorial(k) // math.factorial(n - k)
    return ret


def calc_1dim(x, y, k):
    ret = 0

    for i in range(1, x):
        ret += i * (x - i)

    ret *= y * y * combi(x * y - 2, k - 2)

    return ret


mod = int(1e9) + 7
n, m, k = map(int, input().split())

x1 = calc_1dim(n, m, k)
x2 = calc_1dim(m, n, k)
ans = x1 + x2

ans %= mod

print(ans)

Submission status: Time Limit Exceeded

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

DIV = 10**9+7

def comb(l, r):
    if l == 0:
        return 1
    val = 1
    for i in range(r, r-l, -1):
        val *= i
    for i in range(l, 0, -1):
        val //= i
    return val


p = comb(K-2, N*M-2)
#print(K-2, N*M-2, p)
ans = 0
for i in range(N):
    for j in range(M):
        if i == 0 and j == 0:
            continue
        d = i+j
        #print(i, j, calc_rec_num(N, M, 0, 0, i, j))
        cnt = (N-i) * (M-j)
        if i != 0 and j != 0:
            cnt *= 2
        ans += d * cnt
        #if ans > DIV:
        #    ans %= DIV
        #print(ans)

print((ans*p)%DIV)

Submission status: Time Limit Exceeded

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

DIV = 10**9+7

def comb(l, r):
    if l == 0:
        return 1
    val = 1
    for i in range(r, r-l, -1):
        val *= i
    for i in range(l, 0, -1):
        val //= i
    return val

def calc_rec_num(N, M, xi, xj, yi, yj):
    cnt = 1
    cnt *= N - yi
    cnt *= M - yj
    # rotate
    if xi != yi and xj != yj:
        cnt *= 2
    return cnt


p = comb(K-2, N*M-2)
#print(K-2, N*M-2, p)
ans = 0
for i in range(N):
    for j in range(M):
        if i == 0 and j == 0:
            continue
        d = i+j
        #print(i, j, calc_rec_num(N, M, 0, 0, i, j))
        ans += d * calc_rec_num(N, M, 0, 0, i, j)
        #if ans > DIV:
        #    ans %= DIV
        #print(ans)

print((ans*p)%DIV)

Submission status: Time Limit Exceeded

Solution code:
def factorial_mod(n, mod):
    a = 1
    for i in range(1, n + 1):
        a *= i
        a %= mod
    return a


def comb_mod(n, k, mod):
    fact_n = factorial_mod(n, mod)
    fact_k = factorial_mod(k, mod)
    fact_n_k = factorial_mod(n - k, mod)
    return (fact_n * pow(fact_k, mod - 2, mod) * pow(fact_n_k, mod - 2, mod)) % mod


n, m, k = map(int, input().split())
s = 0
mod = 10 ** 9 + 7
for x in range(m):
    for i in range(x, m):
        s += abs(x-i) * n **2
for y in range(n):
    for j in range(y, n):
        s += abs(y-j) * m ** 2


print(s * comb_mod(n * m - 2, k - 2, mod) % mod)

Submission status: Time Limit Exceeded

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

DIV = 10**9+7

def comb(l, r):
    if l == 0:
        return 1
    val = 1
    for i in range(r, r-l, -1):
        val *= i
    for i in range(l, 0, -1):
        val //= i
    return val

def calc_rec_num(N, M, xi, xj, yi, yj):
    cnt = 1
    cnt *= N - yi
    cnt *= M - yj
    # rotate
    if xi != yi and xj != yj:
        cnt *= 2
    return cnt


p = comb(K-2, N*M-2)
#print(K-2, N*M-2, p)
ans = 0
for i in range(N):
    for j in range(M):
        if i == 0 and j == 0:
            continue
        d = i+j
        #print(i, j, calc_rec_num(N, M, 0, 0, i, j))
        ans += d * calc_rec_num(N, M, 0, 0, i, j)
        if ans > DIV:
            ans %= DIV
        #print(ans)

print((ans*p)%DIV)

Submission status: Time Limit Exceeded

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

DIV = 10**9+7

def comb(l, r):
    if l == 0:
        return 1
    val = 1
    for i in range(r, r-l, -1):
        val *= i
    for i in range(l, 0, -1):
        val //= i
    return val

def calc_rec_num(N, M, xi, xj, yi, yj):
    cnt = 1
    cnt *= N - yi
    cnt *= M - yj
    # rotate
    if xi != yi and xj != yj:
        cnt *= 2
    return cnt


p = comb(K-2, N*M-2)
#print(K-2, N*M-2, p)
ans = 0
for i in range(N):
    for j in range(M):
        if i == 0 and j == 0:
            continue
        d = i+j
        #print(i, j, calc_rec_num(N, M, 0, 0, i, j))
        ans += d * calc_rec_num(N, M, 0, 0, i, j) * p
        if ans > DIV:
            ans %= DIV
        #print(ans)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from math import factorial
n,m,K=map(int,input().split())
ans=0
def comb(n,r):
    return factorial(n)//factorial(n-r)//factorial(r)
for i in range(3,n+m+1):
    t=0
    for j in range(max(1,i-n),i):
        if(j>m):
            ans+=t*(i-2)
            break
        k=i-j
        if(j==1 or k==1):
            t+=(m-j+1)*(n-k+1)
        else:
            t+=(m-j+1)*(n-k+1)*2
    else:
        ans+=t*(i-2)
print((ans*comb(n*m-2,K-2))%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
from scipy.misc import comb

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

mod = 10 ** 9 + 7
ans = 0
for d in range(1, N):
    ans += d * (N - d) * M**2
for d in range(1, M):
    ans += d * (M - d) * N**2
print(ans * comb(N * M - 2, K - 2, exact=True) % mod)

Submission status: Time Limit Exceeded

Solution code:
n,m,k=map(int,input().split())
ans=0
INF=10**9+7
if n<=m:
    M=-(m-1)*m*(2*m-1)//3+m*m*(m-1)
    Ms=m*m*(m-1)//2-(m-1)*m*(2*m-1)//6
    M=M%INF
    Ms=Ms%INF
    for i in range(1,n+1):
        for j in range(i,n+1):
            if i==j:
                ans=ans+Ms
            else:
                d=j-i
                ans=ans+d*m**2+M
            ans=ans%INF
else:
    (n,m)=(m,n)
    M=-(m-1)*m*(2*m-1)//3+m*m*(m-1)
    Ms=m*m*(m-1)//2-(m-1)*m*(2*m-1)//6
    M=M%INF
    Ms=Ms%INF
    for i in range(1,n+1):
        for j in range(i,n+1):
            if i==j:
                ans=ans+Ms
            else:
                d=j-i
                ans=ans+d*m**2+M
            ans=ans%INF
import math
ans=(math.factorial(n*m-2)//(math.factorial(n*m-k)*math.factorial(k-2)))*ans
ans=ans%INF
print(ans)

Submission status: Time Limit Exceeded

Solution code:



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

an = 0

for i in range(1,n+1):
    for j in range(1,m+1):
        an += abs(i-1)+abs(j-1)

ans  = 0
#print(an)

fact = 1
f = 1
for i in range(n*m-2-k+2+1,n*m-2+1):
    fact = (i)*fact
   # print(i,end=" ")
for i in range(k-2):
    f = f*(i+1)

#print(fact,f)
fact = fact//f


ans = 0;

for i in range(1,n+1):
    for j in range(1,m+1):
        #if i==1 and j==1:continue
        #print(i,j,ans)
        an = m*( (i-1)*i + (n-i)*(n-i+1) ) + n*( j*(j-1) + (m-j)*(m-j+1) )
        #print(i,j,an , (i-1)*i, (n-i)*(n-i+1), (m-i)*(m-i+1) )
        ans += fact*(an//2)

ans = ans//2
print(ans%1000000007)

Submission status: Time Limit Exceeded

Solution code:
N,M,K=map(int,input().split())
O,S,T=10**9+7,N+M,6
for i in range(K):S=S*(N*M-i)%O;T*=i+1
print(S*K*~-K*pow(T,O-2,O)%O)

Submission status: Time Limit Exceeded

Solution code:
N,M,K=map(int,input().split())
O,S,T=10**9+7,N+M,6
for i in range(K):S*=N*M-i;T*=i+1
print(S*K*~-K*pow(T,O-2,O)%O)

Submission status: Time Limit Exceeded

Solution code:
N,M,K=map(int,input().split())
O=10**9+7
S=N+M
for i in range(K):S=S*(N*M-i)*pow(i+1,O-2,O)
print(S*K*~-K*-~O//6%O)

Submission status: Time Limit Exceeded

Solution code:
import itertools
import sys
from functools import reduce
from operator import mul

sys.setrecursionlimit(10000)
INF = float('inf')


def comb(n, r):
    """
    scipy.misc.comb または scipy.special.comb と同じ
    組み合わせの数 nCr
    :param int n:
    :param int r:
    :rtype: int
    """
    assert n >= r
    r = min(n - r, r)
    if r == 0:
        return 1
    return reduce(mul, range(n, n - r, -1)) // reduce(mul, range(r, 0, -1))


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

def pyramid(n):
    return n * (n + 1) * (n + 2) // 6


# K ==2 の場合
# print(pyramid(N - 1) * M ** 2 + pyramid(M - 1) * N ** 2)
a = comb(N * M-2, K-2)
b = pyramid(N - 1) * M ** 2 + pyramid(M - 1) * N ** 2
print(a*b% (10**9+7))