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:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

class InverseTable:
    __slots__ = ['In', 'fac', 'Ifac']

    def __init__(self, mod, maxnum):
        self.In = [0, 1]; self.fac = [1, 1]; self.Ifac = [1, 1]
        for i in range( 2, maxnum + 1 ):
            self.In.append( ( -self.In[mod % i] * (mod//i) ) % mod )
            self.fac.append( ( self.fac[-1] * i ) % mod )
            self.Ifac.append( (self.Ifac[-1] * self.In[-1]) % mod )
        
    def cmb(self, n, r):
        if ( r<0 or r>n ): return 0
        r = min(r, n-r)
        return self.fac[n] * self.Ifac[r] * self.Ifac[n-r] % mod
    
    def per(self, n, r):
        if ( r<0 or r>n ): return 0
        return self.fac[n] * self.Ifac[n-r] % mod

IT = InverseTable(mod, 10**6)
# maxnum=10**6だとテーブル生成に200ms程かかるので（Pythonだと1000msほど）
# 最大生成領域は問題ごとに要検討

n,m,k=map(int,input().split())
N0=n*m
for i in range(n):
  for j in range(m):
    ans += IT.cmb(N0-2,k-2)*\
      (((n-(i+1))*(n-(i+1)+1)+i*(i+1))//2*m+\
        ((m-(j+1))*(m-(j+1)+1)+j*(j+1))//2*n)
    ans %= mod
print(ans*IT.In[2]%mod)
# print(4*IT.Ifac[3]*9%mod)

Submission status: Accepted

Solution code:
# inverse x^(-1)
def inv(x):
    global mod
    return pow(x, mod - 2, mod)

# factorial x!
def fact(x):
    global mod
    res=1
    for i in range(2 , x + 1):
        res=res * i % mod
    return res

# combination nCr
def combi(n,r):
    if r < 0 or r > n:
        return 0
    else:
        return fact(n) * inv(fact(r)) * inv(fact(n - r)) % mod

mod = 10 ** 9 + 7
N, M, K = map(int,input().split())
x = (N - 1) * N * (N + 1) * inv(6) % mod
x = x * M * M % mod
y = (M - 1) * M * (M + 1) * inv(6) % mod
y = y * N * N % mod
z = combi(M * N - 2, K - 2)
ans = (x + y) * z % mod
print(ans)

Submission status: Accepted

Solution code:
n,m,k=map(int,input().split())
#n*mからk個選ぶ
#x方向
mod=10**9+7
kaidan=[1]*(n*m+1)
gyaku=[1]*(n*m+1)
for i in range(1,n*m+1):
    kaidan[i]=i*kaidan[i-1]%mod
    gyaku[i]=pow(kaidan[i],mod-2,mod)
def comb(n,r):
    if n-r>0 and n>0 and r>0:
        return (kaidan[n]*gyaku[n-r]*gyaku[r])%mod
    elif n==0 or r==0 or n==r:
        return 1
    else:
        0
ans=0
for d in range(1,n):
    ans+=d*(n-d)*m*m*comb(n*m-2,k-2)
for d in range(1,m):
    ans+=d*(m-d)*n*n*comb(n*m-2,k-2)
print(ans%mod)

Submission status: Accepted

Solution code:
U = 2*10**5
MOD = 10**9+7
 
fact = [1]*(U+1)
fact_inv = [1]*(U+1)
 
for i in range(1,U+1):
    fact[i] = (fact[i-1]*i)%MOD
fact_inv[U] = pow(fact[U], MOD-2, MOD)
 
for i in range(U,0,-1):
    fact_inv[i-1] = (fact_inv[i]*i)%MOD

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

n, m, k = map(int, input().split())
ans = ((n-1)*n*(n+1)//6*m**2 + (m-1)*m*(m+1)//6*n**2) * comb(n*m-2, k-2)
print(ans%MOD)

Submission status: Accepted

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

def main():
    N,M,K = map(int,input().split())
    MOD = 10**9+7
    fac = [0 for _ in range(N*M-1)]
    fac[0],fac[1] = 1,1
    inv = copy.deepcopy(fac)
    invfac = copy.deepcopy(fac)
    
    for i in range(2,N*M-1):
        fac[i] = (fac[i-1]*i)%MOD
        inv[i] = MOD-(MOD//i)*inv[MOD%i]%MOD
        invfac[i] = (invfac[i-1]*inv[i])%MOD
        
    def coef(x,y):
        num = (((fac[x]*invfac[y])%MOD)*invfac[x-y]%MOD)
        return num

    xa = ((M**2)*N*(N-1)*(N+1)//6)%MOD
    ya = ((N**2)*M*(M-1)*(M+1)//6)%MOD
    print((xa+ya)*coef(N*M-2,K-2)%MOD)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
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):
    return g1[n]*g2[r]*g2[n-r]%mod


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

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

MOD = 10 ** 9 + 7 

def make_table(size=10**6, p=MOD):
    fac = [None] * (size + 1)
    fac[0] = 1
    for i in range(size):
        fac[i+1] = fac[i] * (i + 1) % p
    ifac = [None] * (size + 1)
    ifac[size] = pow(fac[size], p-2, p)
    for i in range(size, 0, -1):
        ifac[i-1] = ifac[i] * i % p
    return fac, ifac

fac, ifac = make_table(2*10**5)

def comb(n, r, mod=MOD):
    if r > n or r < 0: return 0
    return fac[n] * ifac[r] % mod * ifac[n-r] % mod

n, m, k = map(int, sys.stdin.readline().split())

def main():
    vert = list(range(n+1))
    horiz = list(range(m+1))
    for i in range(1, n):
        vert[i+1] += vert[i]
        vert[i+1] %= MOD
    for i in range(1, m):
        horiz[i+1] += horiz[i]
        horiz[i+1] %= MOD
    
    res = 0
    for i in range(1, n):
        res += (vert[n] - vert[i] - i * (n - i)) * m % MOD * m % MOD
        res %= MOD
    for i in range(1, m):
        res += (horiz[m] - horiz[i] - i * (m - i)) * n % MOD * n % MOD
        res %= MOD
    
    res *= comb(n*m-2, k-2)
    res %= MOD
    return res

if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Accepted

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

class ModTools:
    """ 階乗たくさん使う時用のテーブル準備 """

    def __init__(self, MAX, MOD):
        """ MAX：階乗に使う数値の最大以上まで作る """
        
        MAX += 1
        self.MAX = MAX
        self.MOD = MOD
        # 階乗テーブル
        factorial = [1] * MAX
        factorial[0] = factorial[1] = 1
        for i in range(2, MAX):
            factorial[i] = factorial[i-1] * i % MOD
        # 階乗の逆元テーブル
        inverse = [1] * MAX
        # powに第三引数入れると冪乗のmod付計算を高速にやってくれる
        inverse[MAX-1] = pow(factorial[MAX-1], MOD-2, MOD)
        for i in range(MAX-2, 0, -1):
            # 最後から戻っていくこのループならMAX回powするより処理が速い
            inverse[i] = inverse[i+1] * (i+1) % MOD
        self.fact = factorial
        self.inv = inverse
    
    def nCr(self, n, r):
        """ 組み合わせの数 (必要な階乗と逆元のテーブルを事前に作っておく) """

        if n < r: return 0
        # 10C7 = 10C3
        r = min(r, n-r)
        # 分子の計算
        numerator = self.fact[n]
        # 分母の計算
        denominator = self.inv[r] * self.inv[n-r] % self.MOD
        return numerator * denominator % self.MOD

H, W, K = MAP()

N = H * W
mt = ModTools(N, MOD)

ansh = 0
for i in range(1, H+1):
    ansh += i * (H-i) * pow(W, 2, MOD)
    ansh %= MOD
ansh *= mt.nCr(N-2, K-2)
ansh %= MOD

answ = 0
for i in range(1, W+1):
    answ += i * (W-i) * pow(H, 2, MOD)
    answ %= MOD
answ *= mt.nCr(N-2, K-2)
answ %= MOD

print((ansh + answ) % MOD)

Submission status: Accepted

Solution code:
n,m,k=map(int,input().split())
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

mod = 10**9+7 #出力の制限
N = 3*10**5
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 )

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

Submission status: Accepted

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

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

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

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

w = (m * n - 2) % MOD
u = 1
v = 1
for i in range(1, k-1):
  u *= (w - i + 1)
  u %= MOD
  v *= i
  v %= MOD

ans = ((a + b) % MOD) 
ans *= u
ans %= MOD
ans *= mod_inv(v)
ans %= MOD


print(ans)

Submission status: Accepted

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

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

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

def inv(i):
    return pow(fac[i], mod - 2)

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

x = sum(d * (m - d) for d in range(m)) % mod
y = sum(d * (n - d) for d in range(n)) % mod

c = cmb(n * m - 2, k - 2)
x = (x * n * n * c) % mod
y = (y * m * m * c) % mod

print((x + y) % mod)

Submission status: Accepted

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

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

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

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

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

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

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7

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

def f(x):
    return (x * (x + 1) * (x - 1)) // 6 % MOD

tmp = (N * N * f(M)) % MOD + (M * M *f(N)) % MOD

class Factorial:
    def __init__(self, n, mod):
        self.f = [1]
        self.mod = mod
        for j in range(1, n + 1):
            self.f.append(self.f[-1] * j % mod)
        self.i = [pow(self.f[-1], mod - 2, mod)]
        for j in range(n, 0, -1):
            self.i.append(self.i[-1] * j % mod)
        self.i.reverse()
    def factorial(self, j):
        return self.f[j]
    def ifactorial(self, j):
        return self.i[j]
    def comb(self, n, k):
        return self.f[n] * self.i[n - k] % self.mod * self.i[k] % self.mod if n >= k else 0


c = Factorial(N * M - 2, MOD).comb

tmp *= c(N * M - 2, K - 2)
tmp %= MOD

print (tmp)

Submission status: Accepted

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


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

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

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

Submission status: Accepted

Solution code:

#modの掛け算

def modmal(a,b,mod): #a*bをmodを法にして求める

    return a * b % mod


#modの割り算

def moddiv(a,b,mod): #a/bをmodを法にして求める

    return (a * pow(b,mod-2,mod)) % mod


#逆元

def inverse(a,mod): #aのmodを法にした逆元を返す
    return pow(a,mod-2,mod)



#modのn!と、n!の逆元を格納したリストを返す(拾いもの)
#factorialsには[1, 1!%mod , 2!%mod , 6!%mod… , n!%mod] が入っている
#invsには↑の逆元が入っている

def modfac(n, MOD):
 
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv
    return factorials, invs


def modnCr(n,r,mod,fac,inv): #上で求めたfacとinvsを引数に入れるべし(上の関数で与えたnが計算できる最大のnになる)

    return fac[n] * inv[n-r] * inv[r] % mod

"""
とある二つのxのみに着目すると
距離0になるのは N * M * (M-1)通り
距離xになるのは (N-x) * M * M 通り
すべての場合において他の駒のおき方が (N*M-2)! / (N*M-K)! 通りある
駒を区別しないので駒の割り当て方→K!でわる

110 1
101 2
011 1
"""

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

fac,inv = modfac(N*M+1,mod)


ansx = 0

for dis in range(N):

    if dis == 0:
        ansx += N*M*(M-1) * dis
    else:
        ansx += 2 * (N-dis) * M * M * dis

    ansx %= mod

ansx *= fac[N*M-2] * inv[N*M-K]
ansx %= mod
ansx *= modnCr(K,2,mod,fac,inv)
ansx *= inv[K]

ansy = 0
for dis in range(M):

    if dis == 0:
        ansy += M*N*(N-1) * dis
    else:
        ansy += 2 * (M-dis) * N * N * dis

    ansy %= mod

ansy *= fac[N*M-2] * inv[N*M-K]
ansy %= mod
ansy *= modnCr(K,2,mod,fac,inv)
ansy *= inv[K]

print ((ansx+ansy)%mod)

Submission status: Accepted

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

mod = 10**9 + 7

A = ((N**2)*(N-1))//2 - (N*(2*N-1)*(N-1))//6
A = A*(M**2)
A %= mod
B = 1
for i in range(1,K-1):
    B *= N*M-1-i
    B %= mod
    B *= pow(i,mod-2,mod)
    B %= mod
ans1 = A*B

N,M = M,N
A = ((N**2)*(N-1))//2 - (N*(2*N-1)*(N-1))//6
A = A*(M**2)
A %= mod
B = 1
for i in range(1,K-1):
    B *= N*M-1-i
    B %= mod
    B *= pow(i,mod-2,mod)
    B %= mod
ans2 = A*B

print((ans1+ans2)%mod)

Submission status: Accepted

Solution code:
n,m,k = map(int,input().split())
mod = 10**9+7
rng = n*m+10
fctr = [1]
finv = [1]
for i in range(1,rng):
  fctr.append(fctr[-1]*i%mod)
for i in range(1,rng):
  finv.append(pow(fctr[i],mod-2,mod))
def cmb(n,k):
  if n<0 or k<0:
    return 0
  else:
    return fctr[n]*finv[n-k]*finv[k]%mod

cost = [[0 for i in range(m+1)] for j in range(n+1)]
cost[1][1] = ((n-1)+(m-1))*n*m//2
for i in range(1,n+1):
  for j in range(1,m+1):
    if j>1:
      cost[i][j] = cost[i][j-1]-(m-2*(j-1))*n
    elif i>1:
      cost[i][j] = cost[i-1][j]-(n-2*(i-1))*m
ans = 0
for i in cost:
  ans = (ans+sum(i))%mod
ans = ans*pow(2,mod-2,mod)%mod
ans = ans*cmb(n*m-2,k-2)%mod
print(ans)

Submission status: Accepted

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

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

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

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

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

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



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

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

print(sum_)

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 = [int(_) for _ in input().split()]

mod = 10**9+7 #出力の制限
N = n * m
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 )

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

Submission status: Accepted

Solution code:
import math
def com(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
N,M,K = map(int,input().split())
mod = 10**9+7

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

         
print(ans*com(N*M-2,K-2)//2%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

mod = 10**9+7 #出力の制限
N = 10**6
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 )


def main():
    N, M, K = map(int, input().split())
    mod = 10 ** 9 + 7
    ans = 0
    for i in range(1,N):
        ans += i * (N - i) * M * M
        ans %= mod

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

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



if __name__ == "__main__":
    main()

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)*C(k,2)%mod*(n+m)*inverse[3]%mod)

Submission status: Accepted

Solution code:
n,m,k=map(int,input().split())
U = 2*10**5
MOD = 10**9+7
 
fact = [1]*(U+1)
fact_inv = [1]*(U+1)
 
for i in range(1,U+1):
  fact[i] = (fact[i-1]*i)%MOD
fact_inv[U] = pow(fact[U],MOD-2,MOD)
 
for i in range(U,0,-1):
	fact_inv[i-1] = (fact_inv[i]*i)%MOD
 
def comb(n,k):
  if k < 0 or k > n:
    return 0
  x = fact[n]
  x *= fact_inv[k]
  x %= MOD
  x *= fact_inv[n-k]
  x %= MOD
  return x

ans=0
for i in range(n):
    for j in range(m):
        if i!=0 and j!=0:
            ans+=2*(n-i)*(m-j)*(i+j)
        else:
            ans+=(n-i)*(m-j)*(i+j)
        ans%=MOD

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

Submission status: Accepted

Solution code:
n, m, k = map(int, input().split())
mod = 10**9 + 7
cum_n = 0
t = 0
for i in range(1, n):
  t += i
  cum_n += t

cum_m = 0
t = 0
for i in range(1, m):
  t += i
  cum_m += t

ans = (cum_n * m**2 + cum_m * n**2) % mod

def nCr(n,r,mod = 10**9+7):
    r = min(n-r,r)
    numer = denom = 1
    for i in range(1,r+1):
        numer = numer * (n+1-i) %mod
        denom = denom * i % mod
    return numer * pow(denom,mod-2,mod) %mod

if n*m-2 == 0:
  p = 1
else:
  p = nCr(n*m-2, k-2)

ans = (ans*p)%mod
print(ans)

Submission status: Accepted

Solution code:
MOD = 10**9+7

# フェルマーの小定理
def nCr(n, r, mod=10**9+7):
    r = min(r, n-r)
    numer = denom = 1
    for i in range(1, r+1):
        numer = numer * (n+1-i) % mod
        denom = denom * i % mod
    return numer * pow(denom, mod-2, mod) % mod

N, M, K = map(int, input().split())
ans = 0
# 2点の差がxになる組み合わせは同じ行でM-x通り、2点の行の組み合わせはN*N通り
for x in range(M):
    ans += x * (M-x) * N*N
for y in range(N):
    ans += y * (N-y) * M*M

# 2点以外(K-2)をN*M-2のマスに配置する組み合わせはnCr(N*M-2, K-2)通り
ans *= nCr(N*M-2, K-2, MOD)
ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
n,m,k=map(int,input().split())
mod = 10**9+7
fac = [1]
caf = [1]
def pow(n,p):
    res=1
    while p >0:
        if p%2==0:
            n = n**2 % mod
            p //= 2
        else:
            res = res * n % mod
            p -= 1
    return res % mod

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

def ncr(n,r):
    if n < r or r < 0: return 0
    return fac[n]*caf[r]*caf[n-r]

div2 = caf[2]

sums = [0]
for i in range((max(n,m))):
    sums.append((sums[-1]+i+1) % mod)

res1 = 0
for i in range(m):
    res1 += sums[i]+sums[m-1-i]
    res1 %= mod
res1 *= (n*n)%mod
res1 %= mod

res2 = 0
for i in range(n):
    res2 += sums[i]+sums[n-1-i]
    res2 %= mod
res2 *= (m*m)%mod
res2 %= mod

res = ((res1+res2)*div2)%mod
kc2 = ncr(n*m-2,k-2)
print((res*kc2)%mod)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#ABC127 E

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def C(n,r):
    return fact[n]*pow(fact[n-r],mod-2,mod)*pow(fact[r],mod-2,mod) % mod

n,m,k = LI()

fact = [1]*(n*m+1)
for i in range(1,n*m+1):
    fact[i] = i*fact[i-1]
    fact[i] %= mod

ans = 0
"""xの差"""
for d in range(1,m):
    ans += d*(m-d)*n*n
    ans %= mod

"""yの差"""
for d in range(1,n):
    ans += d*(n-d)*m*m
    ans %= mod

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

Submission status: Accepted

Solution code:
n,m,k = map(int, input().split())
n_ = n*m
mod = 10**9+7
fun = [1]*(n_+1)
for i in range(1,n_+1):
    fun[i] = fun[i-1]*i%mod
rev = [1]*(n_+1)
rev[n_] = pow(fun[n_],mod-2,mod)
for i in range(n_-1,0,-1):
    rev[i] = rev[i+1]*(i+1)%mod

def nCr(n,r):
    if r > n:
        return 0
    return fun[n]*rev[r]%mod*rev[n-r]%mod
  
x = sum(i*(n-i) for i in range(n))%mod
y = sum(i*(m-i) for i in range(m))%mod
ans = (x*m**2 + y*n**2)%mod*nCr(n*m-2,k-2)%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()

class modfact(object):
    def __init__(self,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
        self.__fact=fact; self.__invfact=invfact

    def inv(self,n):
        assert(n>0)
        return self.__fact[n-1]*self.__invfact[n]%MOD

    def fact(self,n):
        return self.__fact[n]

    def invfact(self,n):
        return self.__invfact[n]

    def comb(self,n,k):
        if(k<0 or n<k): return 0
        return self.__fact[n]*self.__invfact[k]*self.__invfact[n-k]%MOD

    def perm(self,n,k):
        if(k<0 or n<k): return 0
        return self.__fact[n]*self.__invfact[n-k]%MOD

def resolve():
    n,m,k=map(int,input().split())
    N=n*m
    ans=0
    mf=modfact(N)
    for d in range(1,n):
        ans+=d*(m**2)*(n-d)*mf.comb(N-2,k-2)
        ans%=MOD
    for d in range(1,m):
        ans+=d*(n**2)*(m-d)*mf.comb(N-2,k-2)
        ans%=MOD
    print(ans)
resolve()

Submission status: Accepted

Solution code:
def solve():
    mod = 10 ** 9 + 7

    def cmb(n, r):
        def build():
            fs = [1]
            t = 1
            for x in range(1, h * w):
                t = (t * x) % mod
                fs.append(t)

            invs = [1] * (h * w)
            t = pow(t, mod - 2, mod)
            invs[-1] = t
            for x in range(h * w - 2, 0, -1):
                t = (t * (x + 1)) % mod
                invs[x] = t
            return fs, invs

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

        fs, invs = build()
        return fs[n] * invs[n - r] * invs[r] % mod

    h, w, k = map(int, input().split())
    c = cmb(h * w - 2, k - 2)
    ret = (pow(w, 2) * sum((h - d) * d for d in range(h))
           + pow(h, 2) * sum((w - d) * d for d in range(w))) * c % mod

    return ret


print(solve())

Submission status: Accepted

Solution code:
n,m,k=map(int,input().split())
num=n*m
MOD = 10**9+7

def inv_mod(a, p=MOD):
    def inv_mod_sub(a, p):
        if a == 1:
            return 1, 0
        else:
            d, r = p//a, p%a
            x, y = inv_mod_sub(r, a)
            return y-d*x, x
    if p < 0: p = -p
    a %= p
    return inv_mod_sub(a,p)[0] % p

def comb_mod(n, k):
    if k < 0 or k > n:
        return 0
    else:
        return f_mod[n]*f_mod_inverse[k]*f_mod_inverse[n-k] % MOD
f_mod=[1]*(num+1)
f_mod_inverse=[1]*(num+1)
for i in range(1,num+1):
  f_mod[i]=f_mod[i-1]*i%MOD
  f_mod_inverse[i]=f_mod_inverse[i-1]*inv_mod(i)%MOD
N=0;M=0
for i in range(1,n):
  N+=i*(n-i)
  N%=MOD
for i in range(1,m):
  M+=i*(m-i)
  M%=MOD
print((N*(m**2)%MOD+M*(n**2)%MOD)*comb_mod(n*m-2,k-2)%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

print((n*m*(m-1)*(m+1)*k*(k-1)*cmb(n*m,k)//(6*m*(n*m-1))+m*n*(n-1)*(n+1)*k*(k-1)*cmb(n*m,k)//(6*n*(n*m-1)))%(10**9+7))

Submission status: Accepted

Solution code:
#15:50
n,m,k = list(map(int,input().split()))
mod = 10 ** 9 + 7
def inv(x):
  y = 1
  while x != 1:
    y *= mod//x+1
    y %= mod
    x -= mod%x
  return y
#print(inv(5))
ans = 1
for i in range(k-2):
  ans *= n*m-2-i
  ans %= mod
  ans *= inv(k-2-i)
  ans %= mod
#print(ans)
zsum = [0]
for i in range(1,max(n,m)):
  zsum.append(zsum[-1]+i)
#print(zsum)
ans1 = 0
for i in range(m):
  ans1 += zsum[i]
  ans1 += zsum[m-1-i]
  ans1 %= mod
ans1 *= n ** 2
ans1 %= mod
ans2 = 0
for j in range(n):
  ans2 += zsum[j]
  ans2 += zsum[n-1-j]
ans2 *= m ** 2
ans2 %= mod
ans *= ans1 + ans2
ans *= inv(2)
ans %= mod
#print(ans1)
#print(ans2)
print(ans)

Submission status: Accepted

Solution code:
#設定
import sys
input = sys.stdin.buffer.readline

con = 10 ** 9 + 7
#ライブラリインポート
from collections import defaultdict

class Combination(object):
	def __init__(self, N, con):
		self.fac = [0] * (N + 1)
		self.inv = [0] * (N + 1)
		self.finv = [0] * (N + 1)
		self.fac[0], self.fac[1] = 1, 1
		self.inv[1] = 1
		self.finv[0], self.finv[1] = 1, 1

		# 前計算
		for i in range(2, N + 1):
			self.fac[i] = self.fac[i - 1] * i % con
			self.inv[i] = self.inv[con % i] * (con - (con // i)) % con
			self.finv[i] = self.finv[i - 1] * self.inv[i] % con

	def com(self, N, k):
		return (self.fac[N] * self.finv[k] * self.finv[N - k]) % con

#入力受け取り
def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	N, M, K = getlist()
	C = Combination(N * M - 2, con)
	c = C.com(N * M - 2, K - 2)
	s = (N * (N + 1) * (N - 1)) // 6 * (M ** 2)
	t = (M * (M + 1) * (M - 1)) // 6 * (N ** 2)
	ans = c * (s + t)
	print(ans % con)

if __name__ == '__main__':
	main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
class combination():
    #素数のmod取るときのみ　速い
    def __init__(self, n, mod):
        self.n = n
        self.fac = [1] * (n + 1)
        self.inv = [1] * (n + 1)
        for j in range(1, n + 1):
            self.fac[j] = self.fac[j - 1] * j % mod

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

    def comb(self, n, r, mod):
        if r > n or n < 0 or r < 0:
            return 0
        return self.fac[n] * self.inv[n - r] * self.inv[r] % mod


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)
    L %= mod
for j in range(M):
    L += (M - j - 1) * (N ** 2) * (j + 1)
    L %= mod
#    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)
C = combination(N*M-2,mod)
cou = C.comb(N*M-2,K-2,mod)*L%mod

print(cou)