Problem:


Score : 500 points

Problem Statement

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

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

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

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

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

Constraints

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

2 \leq K \leq N \times M

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M K

Output

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

Sample Input 1

2 2 2

Sample Output 1

8

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

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

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

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

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

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

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

The sum of these costs is 8.

Sample Input 2

4 5 4

Sample Output 2

87210

Sample Input 3

100 100 5000

Sample Output 3

817260251

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



Sample input:
2 2 2


Sample output:
8

Submission status: Wrong Answer

Solution code:
import sys,heapq
from collections import deque,defaultdict
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
R = 10**9+7
DBG = True # and False
def ddprint(x):
  if DBG:
    print(x)

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

# return y s.t. x*y mod p == 1
def modinv(x,p):
    g,a,b = exgcd(x,p)  # ax+bp = g, g=1 if mutually prime
    return a%p

def comb(p,q):
    if q==0:
        return 1
    if q > p-q:
        q = p-q
    num = p
    den = q
    for i in range(1,q):
        num = (num * (p-i))%R
        den = (den * (q-i))%R
    xden = modinv(den,R)
    return (num*xden)%R

n,m,k = inm()
x = ( (n*n*(m-1)*m*(m+1)+m*m*(n-1)*n*(n+1))//6 )%R
y = comb(n*m-2,k-2)
ddprint(x)
ddprint(y)
print((x*y)%R)

Submission status: Wrong Answer

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

xd = m * (m-1) / 2 * n 
total =  xd * k * (k-1) / 2 
dis = xd * (k-1) * (k-2) / 2

ans = (total - dis) % (10e9+7)
print(ans)

Submission status: Wrong Answer

Solution code:
n, m, k = map(int, input().split())
t = n * m - 2
memo = 1

for i in range(k - 2):
    memo *= t
    memo = memo // (i + 1) % (10 ** 9 + 7)
    t -= 1
nmemo = memo * n * n % (10 ** 9 + 7)
mmemo = memo * m * m % (10 ** 9 + 7)

answer = (((n*(n+1)) % (10 ** 9 + 7)*(n-1))*mmemo//6 % (10**9+7))
answer = (answer+(((m - 1) * m) % (10 ** 9 + 7)
                  * (m + 1)*nmemo // 6)) % (10 ** 9 + 7)

print(answer)

Submission status: Wrong Answer

Solution code:
import sys
import bisect
from collections import defaultdict

ans=0
#n=int(input())
n,m,k=map(int,input().split())
#a=[(1,int(i)) for i in input().split()]

# http://drken1215.hatenablog.com/entry/2018/06/08/210000
max_value = n*m+2
mod = 10 ** 9 + 7

fac = [0 for _ in range(max_value)]
finv = [0 for _ in range(max_value)]
inv = [0 for _ in range(max_value)]

def com_init():
    fac[0] = 1
    fac[1] = 1
    finv[0] = 1
    finv[1] = 1
    inv[1] = 1

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

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

def dist(a,b):
    if a<=0 or b<=0:
        return 0
    
    a,b=min(a,b),max(a,b)
    a,b=a%mod,b%mod
    '''
    rt=((a*(a+1))%mod)*(a+b)//2
    rt+=((a*(a+b))%mod)*(b-a-1) if a!=b else 0
    rt+= - a*a if a==b else 0
    '''
    rt=b*((a*(a+1)//2)%mod + (a*(b-1)//2)%mod)
    rt//=1
    return rt%mod

com_init()

#print(ans,dist(2,2),dist(1,0))
d=0
for i in range(n):
    for j in range(m):
        d+=dist(j,i+1)+dist(i,m-j)+dist(j+1,n-i-1)+dist(n-i,m-j-1)
        d%=mod
ans=d*com(n*m-2,k-2)
ans//=2

print(ans%mod)

Submission status: Wrong Answer

Solution code:
import sys
import bisect
from collections import defaultdict

ans=0
#n=int(input())
n,m,k=map(int,input().split())
#a=[(1,int(i)) for i in input().split()]

# http://drken1215.hatenablog.com/entry/2018/06/08/210000
max_value = n*m+2
mod = 10 ** 9 + 7

fac = [0 for _ in range(max_value)]
finv = [0 for _ in range(max_value)]
inv = [0 for _ in range(max_value)]

def com_init():
    fac[0] = 1
    fac[1] = 1
    finv[0] = 1
    finv[1] = 1
    inv[1] = 1

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

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

def dist(a,b):
    if a<=0 or b<=0:
        return 0
    
    a,b=min(a,b),max(a,b)
    a,b=a%mod,b%mod
    '''
    rt=((a*(a+1))%mod)*(a+b)//2
    rt+=((a*(a+b))%mod)*(b-a-1) if a!=b else 0
    rt+= - a*a if a==b else 0
    '''
    rt=b*((a*(a+1)//2)%mod + (a*(b-1))%mod)
    rt//=1
    return rt%mod

com_init()

#print(ans,dist(2,2),dist(1,0))
d=0
for i in range(n):
    for j in range(m):
        d+=dist(j,i+1)+dist(i,m-j)+dist(j+1,n-i-1)+dist(n-i,m-j-1)
        d%=mod
ans=d*com(n*m-2,k-2)
ans//=2

print(ans%mod)

Submission status: Wrong Answer

Solution code:
import math, string, itertools, fractions, heapq, collections, re, array, bisect, copy, functools, random
import sys
from collections import deque, defaultdict, Counter; from heapq import heappush, heappop
from itertools import permutations, combinations, product, accumulate, groupby
from bisect import bisect_left, bisect_right, insort_left, insort_right
from operator import itemgetter as ig
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20; INF = float("INF"); ans = 0; tmp = 0; ansli = []; tmpli = []; candili = []
eps = 1.0 / 10 ** 10; mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]; ddn = dd + [(-1, 1), (1, 1), (1, -1), (-1, -1)]; ddn9 = ddn + [(0, 0)]
"""for dx, dy in dd:
        nx = j + dx; ny = i + dy
            if 0 <= nx < w and 0 <= ny < h:"""
def wi(): return list(map(int, sys.stdin.readline().split()))
def wip(): return [int(x) - 1 for x in sys.stdin.readline().split()]#WideIntPoint
def ws(): return sys.stdin.readline().split()
def i(): return int(sys.stdin.readline())
def s(): return input()
def hi(n): return [i() for _ in range(n)]
def hs(n): return [s() for _ in range(n)]#HeightString
def mi(n): return [wi() for _ in range(n)]#MatrixInt
def mip(n): return [wip() for _ in range(n)]
def ms(n): return [ws() for _ in range(n)]

n, m, k = wi()

tmp = 0
for j in range(m):
    if j <= (m - 1) // 2:
        tmp += (j * (j + 1) + ((m - 1 - j) * (m - 1 - j + 1)) // 2) * n ** 2
        tmp = tmp % mod
        ans += (j * (j + 1) + ((m - 1 - j) * (m - 1 - j + 1)) // 2) * n ** 2
    elif j == (m - 1) // 2:
        ans += (j * (j + 1)) * n ** 2
    else:
        ans += tmp
        if m % 2 != 0:
            ans -= (((m - 1) // 2) * (((m - 1) // 2) + 1)) * n ** 2
        break
    ans = ans % mod
ans = ans % mod

tmp = 0
for i in range(n):
    if i <= (n - 1) // 2:
        tmp += (i * (i + 1) + ((n - 1 - i) * (n - 1 - i + 1)) // 2) * m ** 2
        tmp = tmp % mod
        ans += (i * (i + 1) + ((n - 1 - i) * (n - 1 - i + 1)) // 2) * m ** 2
    elif i == (n - 1) // 2:
        ans += (i * (i + 1)) * m ** 2
    else:
        ans += tmp
        if n % 2 != 0:
            ans -= (((n - 1) // 2) * (((n - 1) // 2) + 1)) * m ** 2
        break
        break
    ans = ans % mod
ans = ans % mod
ans = ans // 2

MAX_N = 3 * 10 ** 5 + 100
factorial = [1] * MAX_N
#事前に階上テーブルを用意
def calc_factorial():
    for i in range(1, MAX_N):
        factorial[i] = i * factorial[i - 1] % mod

def comb(n, k):
    a = factorial[n] % mod
    b = (factorial[k] * factorial[n - k]) % mod
    b_ = pow(b, mod - 2, mod)
    return (a * b_) % mod


# 階乗を用意
calc_factorial()

ans *= comb(n * m, k - 2)
print(ans % mod)

Submission status: Wrong Answer

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

mod = int(1000000007)
g1 = [1, 1] # 元テーブル
g2 = [1, 1] # 逆元テーブル
inverse = [0, 1] # 逆元テーブル計算用テーブル

for i in range( 2, N*M-1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

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

var_1 = M**2 * (N-1) * N * (N+1) / 3
var_2 = N**2 * (M-1) * M * (M+1) / 3
cost_allpairs = (var_1 + var_2) / 2
cost_allpairs = cost_allpairs % mod
print(cost_allpairs)

cmb = combination(N*M-2, K-2, mod)
print(cmb)

ans = (cost_allpairs * cmb) % mod
print(int(ans))

Submission status: Wrong Answer

Solution code:
import sys
import bisect
from collections import defaultdict

ans=0
#n=int(input())
n,m,k=map(int,input().split())
#a=[(1,int(i)) for i in input().split()]

# http://drken1215.hatenablog.com/entry/2018/06/08/210000
max_value = n*m+2
mod = 10 ** 9 + 7

fac = [0 for _ in range(max_value)]
finv = [0 for _ in range(max_value)]
inv = [0 for _ in range(max_value)]

def com_init():
    fac[0] = 1
    fac[1] = 1
    finv[0] = 1
    finv[1] = 1
    inv[1] = 1

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

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

def dist(a,b):
    if a<=0 or b<=0:
        return 0
    
    a,b=min(a,b),max(a,b)
    a,b=a%mod,b%mod
    '''
    rt=((a*(a+1))%mod)*(a+b)//2
    rt+=((a*(a+b))%mod)*(b-a-1) if a!=b else 0
    rt+= - a*a if a==b else 0
    '''
    rt=b*((a*(a+1))%mod + (a*(b-1))%mod)
    rt//=2
    return rt%mod

com_init()

#print(ans,dist(2,2),dist(1,0))
d=0
for i in range(n):
    for j in range(m):
        d+=dist(j,i+1)+dist(i,m-j)+dist(j+1,n-i-1)+dist(n-i,m-j-1)
        d%=mod
ans=d*com(n*m-2,k-2)
ans//=2

print(ans%mod)

Submission status: Wrong Answer

Solution code:
def getInv(N):#Qはmod
    inv = [0] * (N + 1)
    inv[0] = 1
    inv[1] = 1
    for i in range(2, N + 1):
        inv[i] = (-(Q // i) * inv[Q%i]) % Q
    return inv

Q = 10**9+7
modinv = getInv(4*10**5)
N, M, K = map( int, input().split())
T = N*M
comb = 1
for i in range(K-2):
    comb *= T-2-i
    comb %= Q
    comb *= modinv[K-2-i]
    comb %= Q
ans = (N**2)%Q*(N-1)*(N+1)%Q*M%Q*modinv[6]%Q + (M**2)%Q*(M-1)*(M+1)%Q*N%Q*modinv[6]%Q
ans %= Q
# print(ans,T-2, K-2, comb)
print( ans*comb%Q)

Submission status: Wrong Answer

Solution code:
def getInv(N):#Qはmod
    inv = [0] * (N + 1)
    inv[0] = 1
    inv[1] = 1
    for i in range(2, N + 1):
        inv[i] = (-(Q // i) * inv[Q%i]) % Q
    return inv

Q = 10**9+7
modinv = getInv(4*10**5)
N, M, K = map( int, input().split())
T = N*M
comb = 1
for i in range(K-2):
    comb *= T-2-i
    comb %= Q
    comb *= modinv[K-2-i]
    comb %= Q
ans = N**2%Q*(N-1)*(N+1)%Q*M%Q*modinv[6]%Q + M**2%Q*(M-1)*(M+1)%Q*N%Q*modinv[6]%Q
ans %= Q
print(ans,T-2, K-2, comb)
print( ans*comb%Q)

Submission status: Wrong Answer

Solution code:
import sys
import bisect
from collections import defaultdict

ans=0
#n=int(input())
n,m,k=map(int,input().split())
#a=[(1,int(i)) for i in input().split()]

# http://drken1215.hatenablog.com/entry/2018/06/08/210000
max_value = n*m+2
mod = 10 ** 9 + 7

fac = [0 for _ in range(max_value)]
finv = [0 for _ in range(max_value)]
inv = [0 for _ in range(max_value)]

def com_init():
    fac[0] = 1
    fac[1] = 1
    finv[0] = 1
    finv[1] = 1
    inv[1] = 1

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

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

def dist(a,b):
    if a<=0 or b<=0:
        return 0
    
    a,b=min(a,b),max(a,b)
    a,b=a%mod,b%mod
    '''
    rt=((a*(a+1))%mod)*(a+b)//2
    rt+=((a*(a+b))%mod)*(b-a-1) if a!=b else 0
    rt+= - a*a if a==b else 0
    '''
    rt=b*((a*(a+1))%mod + (a*(b-1))%mod)
    rt//=2
    return rt%mod

com_init()

#print(ans,dist(2,2),dist(1,0))
d=0
for i in range(n):
    for j in range(m):
        d+=dist(j,i+1)+dist(i,m-j)+dist(j+1,n-i-1)+dist(n-i,m-j-1)
        d%=mod
ans=d*com(n*m,k-2)
ans//=2

print(ans%mod)

Submission status: Wrong Answer

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

NM = N * M
bai = (K * combinations_count(NM , K)) // (NM**2 - NM)

sum_cost = 0

ich_list = [(i, j) for i in range(1, N+1) for j in range(1, M+1)]

for p in range(len(ich_list) - 1):
    for q in range(p+1, len(ich_list)):
        i1, j1 = ich_list[p]
        i2, j2 = ich_list[q]
#         print(i1, j1, i2, j2)
#         print(abs(i2 - i1) + abs(j2 - j1))
        sum_cost += abs(i2 - i1) + abs(j2 - j1)
                
print((sum_cost * bai) % (10**9 + 7))

Submission status: Wrong Answer

Solution code:
from functools import reduce

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)

# mを法とするaの乗法的逆元
def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

MOD = 10**9+7

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

patterns = reduce(lambda a,b: (a*b)%MOD, range(N*M-K+1, N*M+1))
patterns *= modinv(reduce(lambda a,b: (a*b)%MOD, range(1, K+1)), MOD)

patterns *= (N+M)*K*(K-1)
patterns //= 6
patterns %= MOD

print(patterns)

Submission status: Wrong Answer

Solution code:
# Enter your code here. Read input from STDIN. Print output to STDOUT

MOD=10**9+7
fact=[1]
infact=[1]
temp=1
intemp=1
for i in xrange(1,10**6):
    temp*=i
    temp%=MOD
    fact+=[temp]
    intemp*=pow(i,MOD-2,MOD)
    intemp%=MOD
    infact+=[intemp]
    

def binom(a,b):
    up=fact[a]
    down=(infact[b]*infact[a-b])%MOD
    ans=(up*down)%MOD
    return ans


N,M,k=list(map(int,raw_input().strip().split(' ')))

ans=(binom(M*N,k)*binom(k,2))%MOD
ans*=((M*M*binom(N+1,3))%MOD+(N*N*binom(M+1,3))%MOD)%MOD
ans*=pow(binom(M*N,2),MOD-2,MOD)
ans%=MOD
print(ans)

Submission status: Wrong Answer

Solution code:
n,m,k=map(int,input().split())
sn=0
sm=0
for i in range(n+1):
  sn+=(i*(i+1)+(n-i)*(n-i+1))//2
for i in range(m+1):
  sm+=(i*(i+1)+(m-i)*(m-i+1))//2
sn=sn*((m+1)**2)
sm=sm*((n+1)**2)
c=k*(k-1)/2
sn=(sn*c)%(10**9+7)
sm=(sm*c)%(10**9+7)
print((sn+sm)%(10**9+7))

Submission status: Wrong Answer

Solution code:
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

list=input().split(" ")
n=int(list[0])
m=int(list[1])
k=int(list[2])

niko1=int(m*m*(n*(n+1)*(2*n+1)/6 - (n+1)*n*(n+1)/2 + n*n*(n+1)/2))
niko2=int(n*n*(m*(m+1)*(2*m+1)/6 - (m+1)*m*(m+1)/2 + m*m*(m+1)/2))
niko1=niko1%(10**9+7)
niko2=niko2%(10**9+7)
niko=niko1+niko2
kosu=cmb(m*n-2, k-2)
kosu=kosu%(10**9+7)
kotae=int(niko*kosu/2)
kotae=kotae%(10**9+7)
print(kotae)

Submission status: Wrong Answer

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

def cell_dist_sum(i,j):
    x = (i*(i+1)//2+(N-i-1)*(N-i)//2)*M
    y = (j*(j+1)//2+(M-j-1)*(M-j)//2)*N
    return x+y

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

def factorial(n):
    ans = 1
    for i in range(n):
        ans *= (i+1)
    return ans

c_sum = 0
for i in range(N):
    for j in range(M):
        c_sum += cell_dist_sum(i,j)//2
        c_sum = c_sum % 1000000007
c_sum *= nCm(N*M-2, K-2)
c_sum = c_sum % 1000000007

print(c_sum)

Submission status: Wrong Answer

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

MOD = int(1e9 + 7)
NM = N * M

def su(n):
  return n * (n + 1) // 2
class comb():
  F = [1, 1]
  Fi = [1, 1]
  I = [0, 1]
  def __init__(self, num, mod):
    self.MOD = mod
    for i in range(2, num + 1):
      self.F.append((self.F[-1] * i) % mod)
      self.I.append(mod - self.I[mod % i] * (mod // i) % mod)
      self.Fi.append(self.Fi[-1] * self.I[i] % mod)
  def com(self, n, k):
    if n < k: return 0
    if n < 0 or k < 0: return 0
    return self.F[n] * (self.Fi[k] * self.Fi[n - k] % self.MOD) % self.MOD

co = comb(NM, MOD)
times = co.com(NM - 2, K - 2)
Ans = 0
for i in range(N):
  for j in range(M):
    k = (su(i) + su(N - i - 1)) * M % MOD
    k = k + (su(j) + su(M - j - 1)) * N % MOD
    k = k * times // 2 % MOD
    Ans += k % MOD
    Ans = Ans % MOD

print(Ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
from collections import defaultdict
import math
sys.setrecursionlimit(20000000)
input = sys.stdin.readline
n,m,k = map(int,input().split())
mod = 10**9 + 7
fact = [1]*(n*m+10000+1)
rfact = [1]*(n*m+10000+1)
for i in range(n+10000):
    fact[i+1] = rr = ((i+1) * fact[i]) % mod
def comb(N, K,mod):
    return fact[N] * pow(fact[K], mod-2, mod) * pow(fact[N-K], mod-2, mod) % mod
ans = 0
ni = comb(n*m-2,k-2,mod)
for i in range(n):
    for j in range(m):
        ko = (1+j)*j*n//2
        ko += (m-j)*(m-1-j)*n//2
        ko += (1+i)*i*m//2
        ko += (n-i)*(n-1-i)*m//2
        ans += ni*ko
        ans %= mod
print(ans*pow(2,mod-2,mod)%mod)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
import math
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

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


N,M,K = map(int,input().split())
ans = 0
mod = 10**9 +7
by = cmb(N*M-2,K-2,mod)

#まずは、X軸の総和を求める。
X = []
for i in range(1,N+1):
    for j in range(M):
        X.append(i)

for a,b in list(combinations(X,2)):
    ans = (ans + abs(a-b)*by%mod)%mod


Y = []
for i in range(1,M+1):
    for j in range(N):
        Y.append(i)

for a,b in list(combinations(Y,2)):
    ans = (ans + abs(a-b)*by%mod)%mod

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
import math
def choose(n,k):
    return math.factorial(n)//(math.factorial(n-k)*math.factorial(k))

N,M,K = map(int,input().split())
ans = 0
mod = 10**9 +7
by = choose(N*M-2,K-2)

#まずは、X軸の総和を求める。
X = []
for i in range(1,N+1):
    for j in range(M):
        X.append(i)

for a,b in list(combinations(X,2)):
    ans = (ans + abs(a-b)*by%mod)%mod


Y = []
for i in range(1,M+1):
    for j in range(N):
        Y.append(i)

for a,b in list(combinations(Y,2)):
    ans = (ans + abs(a-b)*by%mod)%mod

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, M, K = map(int, readline().split())

    COM_MAX = N * M

    fac, finv, inv = [0] * (COM_MAX + 1), [0] * (COM_MAX + 1), [0] * (COM_MAX + 1)
    fac[0] = fac[1] = finv[0] = finv[1] = inv[1] = 1

    for i in range(2, COM_MAX + 1):
        fac[i] = fac[i - 1] * i % MOD
        inv[i] = MOD - inv[MOD % i] * (MOD // i) % MOD
        finv[i] = finv[i - 1] * inv[i] % MOD

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

    def solve(n, m, k):
        ans = 0
        for j in range(1, k):
            tmp = 0
            for i in range(1, n):
                tmp = (tmp + com(m * i, j) * com(m * (n - i), k - j)) % MOD
            ans = (ans + tmp * j * (k - j)) % MOD

        return ans

    ans = (solve(N, M, K) + solve(M, N, K)) % MOD
    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

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

ans = 0
for i in range(n*m-1):
    xi, yi = divmod(i, m)
    for j in range(i, n*m):
        xj, yj = divmod(j, m)
        d = abs(xi-xj)+abs(yi-yj)
        ans += d
        #ans += d*cmb1(n*m-2, k-2, mod)
ans %= mod
ans *= cmb1(n*m-2, k-2, mod)
ans %= mod
print(ans)

Submission status: Time Limit Exceeded

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

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

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

ans = 0
for i in range(n*m-1):
    xi, yi = divmod(i, m)
    for j in range(i, n*m):
        xj, yj = divmod(j, m)
        d = abs(xi-xj)+abs(yi-yj)
        ans += d
        #ans += d*cmb1(n*m-2, k-2, mod)
ans *= cmb1(n*m-2, k-2, mod)
ans %= mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
def choose(n,k):
    return math.factorial(n)//(math.factorial(n-k)*math.factorial(k))
mod = 10**9 +7
N,M,K = map(int,input().split())
ans = 0
memo = choose(N*M-2,K-2)
#まずはX軸について、総和を考える
d = 1
while d < M:
    ans += d*memo*(M-d)*N*N
    d += 1
    ans %= mod

#Y軸について、総和を考える
d = 1
while d < N:
    ans += d*memo*(N-d)*M*M
    d += 1
    ans %= mod

print(ans)

Submission status: Time Limit Exceeded

Solution code:
p,q,r=map(int,input().split())

    
def comb_mod(N,K,modp):

    K_fact=1
    NK_fact=1
    N_fact=1

    for i in range(1,K+1):
        K_fact*=i
    for i in range(1,N-K+1):
        NK_fact*=i
    for i in range(1,N+1):
        N_fact*=i

    K_inv=pow(K_fact, -1, modp)
    NK_inv=pow(NK_fact, -1, modp)
    pat=(N_fact*K_inv)%modp*NK_inv%modp
    return pat

pat=comb_mod(p*q-2,r-2,10**9+7)

ans=0
for i in range(0,q+1):
    ans+=i*(q-i)*p*p

for k in range(0,p+1):
    ans+=k*(p-k)*q*q


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

Submission status: Time Limit Exceeded

Solution code:
def cmb(a,b,c):
    b = min(b,a-b)
    num = 1
    for i in range(b):
        num = num*(a-i) % c
    den = 1
    for i in range(b):
        den = den*(i+1) % c
    return num * pow(den,c-2,c) % c
n,m,k = map(int,input().split())
mod = 10**9+7
ans = 0
for i in range(1,n):
    ans += i*(n-i)*m**2*cmb(n*m-2,k-2,mod)
    ans %= mod
for i in range(1,m):
    ans += i*(m-i)*n**2*cmb(n*m-2,k-2,mod)
    ans %= mod
print(ans)

Submission status: Time Limit Exceeded

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

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

ans=0
k=MODCOMB(N*M-2, K-2)
for x1 in range(N-1):
  for x2 in range(x1+1, N):
    ans=(ans+abs(x1-x2)*M*M*k)%MOD
    
for y1 in range(M-1):
  for y2 in range(y1+1, M):
    ans=(ans+abs(y1-y2)*N*N*k)%MOD
    
print(ans)

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

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

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

Submission status: 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 i in range(1, M):
    ans += (i * (M-i) * N**2) % (10**9 + 7) 
for i in range(1, N):
    ans += (i * (N-i) * M**2) % (10**9 + 7)

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

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

ans = 0

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

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

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

ans = 0

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

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

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

Submission status: Time Limit Exceeded

Solution code:
import math

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

facts = [1 for i in range(MAX)]
invs = [1 for i in range(MAX)]

def inv(x):
	return pow(x,mod-2,mod)

for i in range(1,MAX):
    facts[i] = (facts[i-1] * i)% mod
    invs[i] = inv(facts[i])

def nCr(n,r):
	return facts[n] * invs[r] * invs[n-r] % mod

def main():
    ans = 0
    complement = nCr((N*M-2)%mod,(K-2)%mod)
    for i in range(N-1):
        for j in range(i+1,N):
            d = abs(i - j)
            ans += d * M**2
    for i in range(M-1):
        for j in range(i+1,M):
            d = abs(i - j)
            ans += d * N**2
    print((ans*complement) % mod)

main()

Submission status: Time Limit Exceeded

Solution code:
import math

def cmb(n,r):
    if r == 0:
        return 1
    return math.factorial(n) // math.factorial(n-r) // math.factorial(r)

def main():
    N,M,K = map(int, input().split())
    ans = 0
    complement = cmb(N*M-2,K-2)
    for i in range(N-1):
        for j in range(i+1,N):
            d = abs(i - j)
            ans += d * M**2
    for i in range(M-1):
        for j in range(i+1,M):
            d = abs(i - j)
            ans += d * N**2
    print((ans*complement) % 1000000007)

main()

Submission status: Time Limit Exceeded

Solution code:
class ModInt:
    def __init__(self, num, mod):
        self.num = num
        self.mod = mod

    def __str__(self):
        return str(self.num)

    def __repr__(self):
        return "ModInt(num: {}, mod: {}".format(self.num, self.mod)

    def __add__(self, other):
        ret = self.num + other.num
        ret %= self.mod
        return ModInt(ret, self.mod)

    def __sub__(self, other):
        ret = self.num - other.num
        ret %= self.mod
        return ModInt(ret, self.mod)

    def __mul__(self, other):
        ret = self.num * other.num
        ret %= self.mod
        return ModInt(ret, self.mod)

    def pow(self, times):
        pw = pow(self.num, times, self.mod)
        return ModInt(pw, self.mod)

    def inverse(self):
        return self.pow(self.mod - 2)

    def __truediv__(self, other):
        num = self * other.inverse()
        return ModInt(num, self.mod)


class Combination:
    def __init__(self, n, mod):
        self.mod = mod
        self.fact = [ModInt(1, mod)]
        self.inverse = [ModInt(1, mod)]
        for i in range(1, n + 1):
            self.fact.append(self.fact[-1] * ModInt(i, mod))
            self.inverse.append(self.inverse[-1] * ModInt(i, mod).inverse())

    def comb(self, n, k):
        if k < 0 or n < k:
            return ModInt(0, self.mod)

        return self.fact[n] * self.inverse[k] * self.inverse[n-k]


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

cmb = Combination(2 * 10 ** 5, mod)
ans = ModInt(0, mod)
for i in range(n):
    for j in range(m):
        add = ModInt(n - i, mod) * ModInt(m - j, mod) * ModInt(i + j, mod)
        if i != 0 and j != 0:
            add *= ModInt(2, mod)

        ans += add

ans *= cmb.comb(n * m - 2, k - 2)
print(ans)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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(N):
    for j in range(M):
        ad = (N - i) * (M - j) * (i + j)
        if i != 0 and j != 0:
            ad *= 2
        ans += ad    
print(ans * C % MOD)

Submission status: Time Limit Exceeded

Solution code:
def main():
    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)
 
if __name__ == "__main__":
    main()