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: Accepted

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


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


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

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

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

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

Submission status: Accepted

Solution code:
n,m,k=map(int,input().split())
mod=10**9+7
A=n*m-2
from math import factorial
def Comb(N, K):
    a = factorial(N) % mod
    b = factorial(K) % mod
    c = factorial(N-K) % mod
    return (a * pow(b, mod-2, mod) * pow(c, mod-2, mod)) % mod
v=Comb(A,k-2)
t=0
y=0
for i in range(1,n):
  t+=i*(n-i)*m*m%mod
for i in range(1,m):
  y+=i*(m-i)*n*n%mod

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

Submission status: Accepted

Solution code:
#cmb
mod=10**9+7
MAX=2*10**5+100

g1=[1,1]
g2=[1,1]
for i in range(2,MAX+1):
    num_1=g1[-1]*i%mod
    g1.append(num_1)
    g2.append(pow(num_1,mod-2,mod))
    
def cmb(n,r,MOD):
    return g1[n]*g2[r]*g2[n-r]%MOD

n,m,k=map(int,input().split())
s=0
t=0
for i in range(1,n):
    s+=i*(n-i)
for i in range(1,m):
    t+=i*(m-i)

ans=(n*n*t+m*m*s)%mod
ans=(ans*cmb(n*m-2,k-2,mod))%mod
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def modfact(n):
    fact=[1]*(n+1)
    invfact=[1]*(n+1)
    for i in range(1,n+1):
        fact[i]=i*fact[i-1]%MOD
    invfact[n]=pow(fact[n],MOD-2,MOD)
    for i in range(n-1,-1,-1):
        invfact[i]=invfact[i+1]*(i+1)%MOD
    return fact,invfact

def resolve():
    n,m,k=map(int,input().split())
    fact,invfact=modfact(n*m-2)
    ans=1
    ans*=fact[m*n-2]*invfact[k-2]*invfact[m*n-k]
    ans*=((n-1)*n*(n+1)*m*m+(m-1)*m*(m+1)*n*n)//6
    print(ans%MOD)
resolve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def modfact(n):
    fact=[1]*(n+1)
    invfact=[1]*(n+1)
    for i in range(1,n+1):
        fact[i]=i*fact[i-1]%MOD
    invfact[n]=pow(fact[n],MOD-2,MOD)
    for i in range(n-1,-1,-1):
        invfact[i]=invfact[i+1]*(i+1)%MOD
    return fact,invfact

def resolve():
    from math import factorial as fact
    n,m,k=map(int,input().split())
    fact,invfact=modfact(n*m)
    ans=1
    ans*=fact[m*n-2]*invfact[k-2]*invfact[m*n-k]
    ans*=((n-1)*n*(n+1)*m*m+(m-1)*m*(m+1)*n*n)//6
    print(ans%MOD)
resolve()

Submission status: Accepted

Solution code:
def cmb(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
 
n,m,k=map(int,input().split())
mod=10**9+7
 
g1=[1,1]
g2=[1,1]
inverse=[0,1]
 
for i in range(2,n*m):
  g1.append((g1[-1]*i)%mod)
  inverse.append((-inverse[mod%i]*(mod//i))%mod)
  g2.append((g2[-1]*inverse[-1])%mod)

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

Submission status: Accepted

Solution code:
def cmb(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
 
N,M,k=map(int,input().split())
m=10**9+7
 
g1=[1,1]
g2=[1,1]
inverse=[0,1]
 
for i in range(2,N*M):
  g1.append((g1[-1]*i)%m)
  inverse.append((-inverse[m%i]*(m//i))%m)
  g2.append((g2[-1]*inverse[-1])%m)

c=cmb(N*M-2,k-2,m)
ans=0
for i in range(N):
  ans+=((N-i)*M*M*i*c)%m
  ans%=m
for i in range(M):
  ans+=((M-i)*N*N*i*c)%m
  ans%=m
print(ans%m)

Submission status: Accepted

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

# comb init
nmax = 2 * 10 ** 5 + 1  # change here
fac = [0] * (nmax + 1)
finv = [0] * (nmax + 1)
inv = [0] * (nmax + 1)
fac[0] = 1
fac[1] = 1
finv[0] = 1
finv[1] = 1
inv[1] = 1
for i in range(2, nmax):
    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 comb(n, r):
    if n < r:
        return 0
    else:
        return (fac[n] * ((finv[r] * finv[n - r]) % mod)) % mod


def s(k):
    return ((k * (k+1) * (2 * k + 1))%mod * inv[6] + (k * (k+1) * inv[2])%mod)%mod


C = comb(N*M-2, K-2)
print(((C * ((N ** 2 * s(M-1))%mod + (M ** 2 * s(N-1))%mod)%mod)%mod) * inv[2]%mod)

Submission status: Accepted

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

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

NN = 10**6 # 使うデータによって変える
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

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

ans = 0
for n in range(1, N+1):
    le = n*(n-1)//2 + (N-n)*(N-n+1)//2
    le *= M**2
    ans += le

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

ans //= 2
ans %= mod
ans =  ans * cmb(N*M-2, K-2) % mod
print(ans)

Submission status: Accepted

Solution code:
from operator import mul
from functools import reduce
def comb2(n,r):
    r = min(n - r, r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1, r + 1))
    return over // under
def comb3(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


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

N, M, K = LI()

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

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

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

ans = cou *L%mod

print(ans)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

# 2点間の距離の平均を求めればよい

MOD = 10**9 + 7

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

def cumprod(arr,MOD):
    L = len(arr); Lsq = int(L**.5+1)
    arr = np.resize(arr,Lsq**2).reshape(Lsq,Lsq)
    for n in range(1,Lsq):
        arr[:,n] *= arr[:,n-1]; arr[:,n] %= MOD
    for n in range(1,Lsq):
        arr[n] *= arr[n-1,-1]; arr[n] %= MOD
    return arr.ravel()[:L]

def make_fact(U,MOD):
    x = np.arange(U,dtype=np.int64); x[0] = 1
    fact = cumprod(x,MOD)
    x = np.arange(U,0,-1,dtype=np.int64); x[0] = pow(int(fact[-1]),MOD-2,MOD)
    fact_inv = cumprod(x,MOD)[::-1]
    return fact,fact_inv

U = 10**6
fact, fact_inv = make_fact(U,MOD)

coef = fact[N*M-2] * fact_inv[K-2] % MOD * fact_inv[N*M-K] % MOD

x = (N-1)*N*(N+1)*M*M//6
y = (M-1)*M*(M+1)*N*N//6
answer = coef * ((x+y) % MOD) % MOD
print(answer)

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7

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

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

def mod_inv(a):
    return pow(a, MOD - 2, MOD)


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

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

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

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

print(ans)

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7

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

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


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

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

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

ans = (X + Y) * mod_pow(6, MOD - 2) * comb % MOD

print(ans)

Submission status: Accepted

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

mod = 10**9 + 7

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

ans = 0
c = chs(n*m-2,k-2,mod)

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

        

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

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[]]*num
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))

#################

#a!をmodしつつ求める
def fact(a,M=mod):
    ans = 1
    for i in range(2,a+1):
        ans = ans*i
        ans = ans%M
    return ans

#互いに素なa,bについて、a*x+b*y=1の一つの解[x,y]を出力
def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    return [w[0],w[1]]


#aの逆元(mod M)を求める（aとMは互いに素）
def mod_inv(a,M=mod):
    x = extgcd(a,M)[0]
    return (M+x%M)%M

N,M,K = II()
ans = 0
for i in range(N):
    x = i*(i+1)//2 + (N-1-i)*(N-i)//2
    for j in range(M):
        ans += M*x + N*(j*(j+1)+(M-1-j)*(M-j))//2
        ans %= mod

ans = ans*fact(N*M-2)*mod_inv(fact(K-2))*mod_inv(fact(N*M-K))*mod_inv(2)
ans %= mod
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
mod = 10**9+7
inv_2 = pow(2, mod-2, mod)
N, M, K = map(int, input().split())
def make_fact(n):#0~nの階乗を求める
    fact = [1]*(n+1)
    for i in range(1, n+1):
        fact[i] = fact[i-1]*i%mod
    return fact

def make_fact_inv(n):#0~nの階乗のmodに関する逆元を求める
    fact_inv = [1]*(n+1)
    fact_inv[n] = pow(fact[n], mod-2, mod)#フェルマーの小定理
    for i in range(n, 0, -1):
        fact_inv[i-1] = fact_inv[i]*i%mod
    return fact_inv

def comb(n, k):#nCk
    return fact[n]*fact_inv[k]*fact_inv[n-k]%mod
fact = make_fact(N*M)
fact_inv = make_fact_inv(N*M)
Sum = [0]*(max(N, M)+1)
for i in range(1, len(Sum)):
    Sum[i] = (Sum[i-1]+i)%mod
ans = 0

for x in range(1, N+1):
    for y in range(1, M+1):
        ans+=(Sum[x-1]+Sum[N-x])*M+(Sum[y-1]+Sum[M-y])*N
        ans%=mod
print(ans*comb(N*M-2, K-2)*inv_2%mod)

Submission status: Accepted

Solution code:
#21:50
h,w,k = map(int,input().split())
mod = 10 ** 9 + 7
def inv(x):
  y = 1
  while x != 1:
    y *= mod//x + 1
    y %= mod
    x = x - mod%x
  return y
others = 1
for i in range(k-2):
  others *= h*w-2-i
  others *= inv(i+1)
  others %= mod
hh = 0
for i in range(1,h):
  hh += i * (h-i)
  hh %= mod
ww = 0
for i in range(1,w):
  ww += i * (w-i)
  ww %= mod
ans = others * ( h * h * ww + w * w * hh )
print(ans % mod)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from functools import reduce



INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


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

    divisor = 1
    for j in range(1, r + 1):
        divisor = divisor * j % mod

    return fact * pow(divisor, mod - 2, mod) % mod


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


print(main())

Submission status: Accepted

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


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

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

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

Submission status: Accepted

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
        x %= mod
        y *= i + 1
        y %= mod
    return x * pow(y, mod - 2, mod) % mod

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

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

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

print(ans)

Submission status: Accepted

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


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


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


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

Submission status: Accepted

Solution code:
def comb(n, k, mod=10**9 + 7):
    from functools import reduce
    from operator import mul
    k = min(k, n - k)

    def calc(x, y):
        return x * y % mod

    x = reduce(calc, range(n - k + 1, n + 1), 1) % mod
    y = reduce(calc, range(1, k + 1), 1) % mod
    return x * pow(y, mod - 2, mod) % mod


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


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

Submission status: Accepted

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
        x %= mod
        y *= i + 1
        y %= mod
    return x * pow(y, mod - 2, mod) % mod


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


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

Submission status: Accepted

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
        x %= mod
        y *= i + 1
        y %= mod
    return x * pow(y, mod - 2, mod) % mod


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


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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys

MOD = 1000000007  # type: int

def mfact():
    f = [1]
    for i in range(1, 200007):
        f.append(f[-1] * i % MOD)
    return f

def inv(x):
    res = 1
    k = MOD - 2
    y = x
    while (k):
        if(k % 2 == 1):
            res = (res * y) % MOD
        y = (y ** 2) % MOD
        k = k // 2
    return res

def comb(n, k, f):
    a = f[n]
    b = f[n-k]
    c = f[k]
    bc = (b * c) % MOD
    return (a * inv(bc)) % MOD

def solve(N: int, M: int, K: int):
    ans = 0
    for i in range(N):
        for j in range(M):
            a = j * (j+1) // 2
            b = (M-1-j) * (M-1-j+1) // 2
            ans += (a+b) * i + M * (i*(i+1)//2) + a
            ans %= MOD
    f = mfact()
    ans *= comb(N*M-2, K-2, f)
    ans %= MOD
    print(ans)
    return


# Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    solve(N, M, K)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
mod = 10**9+7 #出力の制限
N = 2*(10**5)
def cmb(n, r):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod
def p(n,r):
    if ( r<0 or r>n ):
        return 0
    return g1[n] * g2[n-r] % mod

g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )
# a = cmb(n,r)


n,m,k = m()

sx = 0
sy = 0

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

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

Submission status: Accepted

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

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

mod=10**9+7
a=cmb(n*m-2,k-2)%mod
res=0
for d in range(1,n):
	res+=(d*(n-d)*m**2*a)%mod
	res%=mod
for d in range(1,m):
	res+=(d*(m-d)*n**2*a)%mod
	res%=mod
print(res)

Submission status: Accepted

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

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

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

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

print(res % mod)

Submission status: Accepted

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

# 組合せの総数
def comb(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])
            result%=MOD

    return result



ans_x=0
ans_y=0

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

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7
MAX = 200000 + 5
fact = [1 for _ in range(MAX)]
finv = [1 for _ in range(MAX)]
for i in range(2, MAX):
    fact[i] = fact[i - 1] * i % MOD
    finv[i] = pow(fact[i], MOD-2, MOD)

def comb(n: int, k: int) -> int:
    if n < k or n < 0 or k < 0:
        return 0
    return (fact[n] * finv[k] % MOD) * finv[n-k] % MOD

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

ans = 0
for i in range(n):
    for j in range(m):
        a = j * (j+1) // 2
        b = (m-1-j) * (m-1-j+1) // 2
        ans += (a + b) * i + m * (i*(i+1)//2) + a
        ans %= MOD

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

print(ans)

Submission status: Accepted

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

import math

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

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

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

Submission status: Accepted

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

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

score_c = 1
for i in range(2, K):
    score_c *= ((N * M - i) % mod * pow(K - i, mod - 2, mod))
    score_c %= mod

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

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


print(total)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000000)
def input():
    return sys.stdin.readline()[:-1]
from bisect import *
from collections import *
from heapq import *
from math import *
N, M, K = map(int, input().split())
L = N*M
mod = 10**9+7
def factrial(N):
    fc = [1, 1] + [None] * N
    inv = [0, 1] + [None] * N
    fcInv = [1, 1] + [None] * N
    for i in range(2, N+1):
        fc[i] = i*fc[i-1]%mod
        inv[i] = mod-(inv[mod%i]*(mod//i))%mod
        fcInv[i] = fcInv[i-1]*inv[i]%mod
    return fc, fcInv
fc, fcInv = factrial(L)
def modCom(n, k):
    return 0 if n < k else fc[n] * fcInv[k] * fcInv[n-k] % mod
ans = 0
for d in range(1, N):
    ans += d*(N-d)*M*M*modCom(L-2, K-2)
    ans %= mod
for d in range(1, M):
    ans += d*(M-d)*N*N*modCom(L-2, K-2)
    ans %= mod
print(ans)

Submission status: Accepted

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

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

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

Submission status: Accepted

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

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

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

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 - 2, k - 2)
print(ans % mod)

Submission status: Accepted

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import defaultdict

mod = 10 ** 9 + 7

memo = defaultdict(int)


def cmb(n, r):
    if (n, r) in memo:
        return memo[(n, r)]

    if n < r or r < 0:
        return 0

    if r > n - r:
        return cmb(n, n - r)

    res = f[n] * pow(f[n - r], mod - 2, mod) * pow(f[r], mod - 2, mod) % mod
    memo[(n, r)] = res
    return res


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

f = [1]
for i in range(1, 2 * 10 ** 5 + 1):
    f.append(f[-1] * i % mod)

ans = 0
for d in range(1, m):
    ans += d * (m - d) * n ** 2
    ans %= mod

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

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

print(ans)