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:
n,m,k=map(int,input().split())
ans=0
INF=10**9+7
if n<=m:
    M=-(m-1)*m*(2*m-1)//3+m*m*(m-1)
    Ms=m*m*(m-1)//2-(m-1)*m*(2*m-1)//6
    M=M%INF
    Ms=Ms%INF
    for i in range(1,n+1):
        for j in range(i,n+1):
            if i==j:
                ans=ans+Ms
            else:
                d=j-i
                ans=ans+d*m**2+M
            ans=ans%INF
else:
    (n,m)=(m,n)
    M=-(m-1)*m*(2*m-1)//3+m*m*(m-1)
    Ms=m*m*(m-1)//2-(m-1)*m*(2*m-1)//6
    M=M%INF
    Ms=Ms%INF
    for i in range(1,n+1):
        for j in range(i,n+1):
            if i==j:
                ans=ans+Ms
            else:
                d=j-i
                ans=ans+d*m**2+M
            ans=ans%INF
def modcomb(n,k,m):
    fac=[0]*(n+1)
    finv=[0]*(n+1)
    inv=[0]*(n+1)
    fac[0]=fac[1]=1
    finv[0]=finv[1]=1
    inv[1]=1
    for i in range(2,n+1):
        fac[i]=fac[i-1]*i%m
        inv[i]=m-inv[m%i]*(m//i)%m
        finv[i]=finv[i-1]*inv[i]%m
    return fac[n]*(finv[k]*finv[n-k]%m)%m
ans=ans*modcomb(n*m-2,k-2,INF)%INF
print(ans)

Submission status: Accepted

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


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

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



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

Submission status: Accepted

Solution code:
from collections import deque
from heapq import heappush,heappop
import re

def int_raw():
    return int(input())

def ss_raw():
    return input().split()

def ints_raw():
    return list(map(int, ss_raw()))

INF = 1<<29

DIV = 10**9+7

def mod_inv(a,mod = DIV):
    return pow(a,mod-2,mod)

def ncr(n,r, mod =DIV):
	r = min(r,n-r)
	ret = 1
	for i in range(1,r+1):
		ret = ret * (n-i+1) % mod
		ret = ret * pow(i, mod-2, mod) % mod
	return ret


def main():
    N, M,K = ints_raw()
    ans = 0
    for d in range(1,N):
        ans =(ans+d*(N-d)*M*M)%DIV
    for d in range(1,M):
        ans =(ans+d*(M-d)*N*N)%DIV
    return (ans*ncr(N*M-2,K-2))%DIV
print(main())

Submission status: Accepted

Solution code:
mdl = 10**9 + 7

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

nm = N*M
mm = M*M % mdl
nn = N*N % mdl

U = 2*10**5
fact = [1] * (U+1)

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

def comb(n,k):
    x = fact[n]
    x *= pow(fact[n-k], mdl-2, mdl)
    x %= mdl
    x *= pow(fact[k], mdl-2, mdl)
    x %= mdl
    return x

def F(N):
    x = N*(N+1) // 2 * N
    y = N*(N+1)*(2*N+1) // 6
    return (x-y) % mdl

ans = mm*F(N) % mdl + nn*F(M) % mdl
ans %= mdl
ans *= comb(nm-2,K-2)
ans %= mdl

print(ans)

Submission status: Accepted

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

def pow(x, n) :
    y = 1
    while n > 0 :
        if n & 1 :
            y = (y * x) % MOD
        x = (x * x) % MOD
        n >>= 1

    return y

def comb(n, r) :
    if n < r or n < 0 :
        return 0

    factorial = [0] * (n + 1)
    factorial[0] = 1

    for i in range(1, n + 1) :
        factorial[i] = (factorial[i-1] * i) % MOD

    return (factorial[n] * pow(factorial[n-r], MOD - 2) * pow(factorial[r], MOD - 2)) % MOD

res = 0

for i in range(N) :
    for j in range(M) :
        if i > 0 and j > 0 :
            res += 2 * (N - i) * (M - j) * (i + j)
        else :
            res += (N - i) * (M - j) * (i + j)

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

print(res % MOD)

Submission status: Accepted

Solution code:
MOD = 10**9 + 7

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

invs = [1] * (K-1)
for x in range(2, K-1):
    invs[x] = (-(MOD//x) * invs[MOD%x]) % MOD

C = 1
for x in range(N*M-K+1, N*M-1):
    C *= x
    C %= MOD
for x in range(1, K-1):
    C *= invs[x]
    C %= MOD

ans1 = 0
for d in range(1, N):
    ans1 += (N-d) * d
    ans1 %= MOD
ans1 *= M**2
ans1 %= MOD

ans2 = 0
for d in range(1, M):
    ans2 += (M-d) * d
    ans2 %= MOD
ans2 *= N**2
ans2 %= MOD

print((ans1+ans2) * C % MOD)

Submission status: Accepted

Solution code:
def com(n,r):
    re=fct[n]*pow(fct[r],md-2,md)*pow(fct[n-r],md-2,md)
    re%=md
    return re

n,m,k=map(int,input().split())
md=10**9+7
ans=0
fct=[1]*(n*m-1)
f=1
for i in range(1,n*m-1):
    f=f*i%md
    fct[i]=f
for d in range(1,m):
    ans=(ans+d*(m-d)*n*n)%md
for d in range(1,n):
    ans=(ans+d*(n-d)*m*m)%md
ans=(ans*com(n*m-2,k-2))%md
print(ans)

Submission status: Accepted

Solution code:
class PERM_COMB_MOD():
    # http://drken1215.hatenablog.com/entry/2018/06/08/210000
    def __init__(self, max_n=510000, mod=10**9+7):
        self.fac = [0]*max_n
        self.finv = [0]*max_n
        self.inv = [0]*max_n
        self.fac[0] = self.fac[1] = 1
        self.finv[0] = self.finv[1] = 1
        self.inv[1] = 1
        self.max = max_n
        self.mod = mod
        self._maesyori()

    def _maesyori(self):
        for i in range(2,self.max):
            self.fac[i] = self.fac[i-1] * i % self.mod
            self.inv[i] = self.mod - self.inv[self.mod % i] * (self.mod // i) % self.mod
            self.finv[i] = self.finv[i-1] * self.inv[i] % self.mod

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

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

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

# xについて
for i in range(1,n):
    ans += i*(n-i)*m*m % mod
    ans %= mod
# yについて
for i in range(1,m):
    ans += i*(m-i)*n*n % mod
    ans %= mod
ans *= p.comb(n*m-2,k-2)
ans %= mod
print(ans)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc127/submissions/5606400

from functools import reduce
from operator import add


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


def cmb(n, r):
    r = min(r, n - r)
    if r == 0:
        return 1
    if r == 1:
        return n
    f = reduce(mod_mul, range(n - r + 1, n + 1))  # n!/(n-r)!
    d = reduce(mod_mul, range(2, r + 1))  # r!
    return (f * pow(d, MOD - 2, MOD)) % MOD


MOD = 10 ** 9 + 7

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

ans_x = reduce(add, (i * (M - i) for i in range(M))) * N ** 2
ans_y = reduce(add, (i * (N - i) for i in range(N))) * M ** 2
ans = (ans_x + ans_y) % MOD
pat = cmb(N * M - 2, K - 2)
ans = (ans * pat) % MOD

print(ans)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc127/submissions/5606400

from functools import reduce


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


def mod_add(a, b):
    return (a + b) % MOD


def cmb(n, r):
    r = min(r, n - r)
    if r == 0:
        return 1
    if r == 1:
        return n

    f = reduce(mod_mul, range(n - r + 1, n + 1))  # n!/(n-r)!
    d = reduce(mod_mul, range(2, r + 1))  # r!
    return (f * pow(d, MOD - 2, MOD)) % MOD


MOD = 10 ** 9 + 7

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

ans_x = reduce(mod_add, (i * (M - i) for i in range(M))) * N ** 2
ans_y = reduce(mod_add, (i * (N - i) for i in range(N))) * M ** 2
ans = ans_x + ans_y
pat = cmb(N * M - 2, K - 2)
ans = (ans * pat) % MOD

print(ans)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc127/submissions/5606400

from functools import reduce


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


def cmb(n, r):
    r = min(r, n - r)
    if r == 0:
        return 1
    if r == 1:
        return n

    f = reduce(mod_mul, range(n - r + 1, n + 1))  # n!/(n-r)!
    d = reduce(mod_mul, range(2, r + 1))  # r!
    return (f * pow(d, MOD - 2, MOD)) % MOD


MOD = 10 ** 9 + 7

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

ans_x = 0
for i in range(M):
    ans_x += i * (M - i)
ans_x *= N ** 2

ans_y = 0
for i in range(N):
    ans_y += i * (N - i)
ans_y *= M ** 2

ans = ans_x + ans_y

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

print(ans)

Submission status: Accepted

Solution code:
"""
https://atcoder.jp/contests/abc127/submissions/5606400
"""


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


def cmb(n, r):
    r = min(r, n - r)
    if r == 0:
        return 1
    if r == 1:
        return n

    f = 1
    for k in range(n, n - r, -1):
        f = (f * k) % MOD
        # n!/(n-r)!

    d = 1
    for k in range(2, r + 1):
        d = (d * k) % MOD
        # r!

    return (f * inv(d)) % MOD


MOD = 10 ** 9 + 7

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

ans = 0

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

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

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

print(ans)

Submission status: Accepted

Solution code:
"""
組み合わせ(nCr)計算
https://qiita.com/derodero24/items/91b6468e66923a87f39f#%E7%95%AA%E5%A4%96%E7%B7%A8
逆元の求め方
http://drken1215.hatenablog.com/entry/2018/06/08/210000
解法@公式放送
https://www.youtube.com/watch?v=SS6kW-d-rJ0&feature=youtu.be&t=7376
"""


def cmb(n, r):
    return (fact[n] * finv_t[r] * finv_t[n - r]) % MOD


MOD = 10 ** 9 + 7

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

fact = [1, 1]
inv_t = [0, 1]
finv_t = [1, 1]
for i in range(2, N * M - 2 + 1):
    fact.append((fact[-1] * i) % MOD)
    inv_t.append((-inv_t[MOD % i] * (MOD // i)) % MOD)
    finv_t.append((finv_t[-1] * inv_t[-1]) % MOD)

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

ans = 0

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

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

ans = (ans * pat) % MOD

print(ans)

Submission status: Accepted

Solution code:
from functools import reduce

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

MOD = 10**9 + 7


class ModInt:
    def __init__(self, x):
        self.x = x % MOD

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

    __repr__ = __str__

    def __add__(self, other):
        return (
            ModInt(self.x + other.x) if isinstance(other, ModInt) else
            ModInt(self.x + other)
        )

    def __sub__(self, other):
        return (
            ModInt(self.x - other.x) if isinstance(other, ModInt) else
            ModInt(self.x - other)
        )

    def __mul__(self, other):
        return (
            ModInt(self.x * other.x) if isinstance(other, ModInt) else
            ModInt(self.x * other)
        )

    def __truediv__(self, other):
        return (
            ModInt(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(self.x * pow(other, MOD - 2, MOD))
        )

    def __pow__(self, other):
        return (
            ModInt(pow(self.x, other.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(self.x, other, MOD))
        )

    __radd__ = __add__

    def __rsub__(self, other):
        return (
            ModInt(other.x - self.x) if isinstance(other, ModInt) else
            ModInt(other - self.x)
        )

    __rmul__ = __mul__

    def __rtruediv__(self, other):
        return (
            ModInt(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(other * pow(self.x, MOD - 2, MOD))
        )

    def __rpow__(self, other):
        return (
            ModInt(pow(other.x, self.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(other, self.x, MOD))
        )


ans = (N * M * (M * (N**2 - 1) + N * (M**2 - 1)) // 6) * reduce(
    lambda acc, i: acc * (N * M - 2 - i) / (K - 2 - i),
    range(K - 2),
    ModInt(1)
)
print(ans)

Submission status: Accepted

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

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

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

for i in range( 2, 10**6 +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 x in range(1,M):
    ans += x*(M-x)*n2*cmb(nm-2,K-2,mod)
    ans %= mod

for y in range(1,N):
    ans += y*(N-y)*m2*cmb(nm-2,K-2,mod)
    ans %= mod

print(int(ans))

Submission status: Accepted

Solution code:
import sys
from itertools import combinations

def comb_mod(n, r, MOD=10**9+7):
    if n < 0 or r < 0 or n < r:
        return 0

    factrial = [1] * (n+1)
    for k in range(1, n+1):
        factrial[k] = (factrial[k-1] * k) % MOD

    fact_inv = [1] * (n+1)
    fact_inv[n] = pow(factrial[n], MOD - 2, MOD)
    for k in range(n-1, -1, -1):
        fact_inv[k] = (fact_inv[k+1] * (k+1)) % MOD

    return (factrial[n] * fact_inv[r] * fact_inv[n-r]) % MOD


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

    # The number of times that pieces are located on certain two tiles.
    num = comb_mod(N*M-2, K-2)

    ans = 0
    # Column-wise distance
    for i in range(M):
        ans += i * (M - i) * N**2 * num
        ans %= MOD

    # Row-wise distance
    for i in range(N):
        ans += i * (N - i) * M**2 * num
        ans %= MOD

    return ans


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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)

MOD = 10**9 + 7
def power_mod(a,b,p):
    if b==0:
        return 1
    if b%2==0:
        d=power_mod(a,b//2,p)
        return (d*d)%p
    else:
        return(a*power_mod(a,b-1,p)%p)

def inverse(a,p):
    return power_mod(a,p-2,p)

def combination(n, r, p): # nCrを求める
    r = min(n-r, r)
    result = 1
    for i in range(n, n-r, -1):
        result *= i
        result %=p
    for i in range(1, r+1):
        result *= inverse(i,p)
        result %= p
    return result

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

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

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

print(ans)

Submission status: Accepted

Solution code:
N,m,k = (int(i) for i in input().split())
n,mod,x,y = N*m,10**9+7,0,0
fn,fk = [1]*n,[1]*n
for i in range(n-1): fn[i+1] = (fn[i]*(i+2))%mod
def power(n,k):
	if k==1: return n
	elif k%2==0: return power((n**2)%mod,k//2)
	else: return (n*power(n,k-1))%mod
def comb(n,k):
	if n==0 or k==0 or n==k: return 1
	else: return (((fn[n-1]*fk[n-k-1])%mod)*fk[k-1])%mod
fk[-1] = power(fn[-1],mod-2)
for i in range(2,n+1): fk[-i] = (fk[-i+1]*(n+2-i))%mod
for i in range(N): x+=i*(N-i)*(m**2)
for i in range(m): y+=i*(m-i)*(N**2)
print(comb(n-2,k-2)*(x+y)%mod)

Submission status: Accepted

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
mod=10**9+7
N,M,K=map(int,input().split())
retu=0
gyou=0
for i in range(1,M):
    retu+=i*(M-i)*N*N
for j in range(1,N):
    gyou+=j*(N-j)*M*M
cost=retu+gyou
num=cmb(N*M-2,K-2)%mod
ans=int((num*(cost %mod))%mod)
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python

import sys
#from sympy import isprime

class bigint:
    primeset = set()
    def __init__(self,n,mod):
        if not mod in bigint.primeset:
            assert mod**2 < sys.maxsize, "modulo is too large"
            #assert isprime(mod), "modulo should be a prime number"
            bigint.primeset.add(mod)
        #
        self.n = n % mod
        self.mod = mod
        return
    #
    def __str__(self):
        return str(self.n)
    #
    def __add__(self,other):
        assert self.mod==other.mod, "modulos of the two not match"
        return bigint(self.n+other.n,self.mod)
    #
    def __sub__(self,other):
        assert self.mod==other.mod, "modulos of the two not match"
        return bigint(self.n-other.n,self.mod)
    #
    def __mul__(self,other):
        assert self.mod==other.mod, "modulos of the two not match"
        return bigint(self.n*other.n,self.mod)
    #
    def __pow__(self,other):
        assert type(other)==int, "power should be integer"
        #
        if other<0: return self ** ( other % ( self.mod-1 ) )
        elif other==0: return 1
        elif other==1: return self
        elif other%2==0:
            tmp= self ** (other//2)
            return bigint( ( tmp.n**2 ) % self.mod,self.mod )
        else:
            tmp= self ** (other//2)
            return bigint( ( tmp.n**2 * self.n ) % self.mod,self.mod )
    #
    def __truediv__(self,other):
        assert self.mod==other.mod, "modulos of the two not match"
        return self * ( other ** (other.mod-2) )
#
#::::::::::::::::::::::::::::::::::::::::::::::::::
mod= 10**9 + 7

def combination(n,m):
    global mod
    assert type(n)==type(m)==int, "type error"
    #
    mm= min(m,n-m)
    if mm==0: return bigint(1,mod)
    elif mm>0:
        a = bigint(n,mod)
        b = bigint(1,mod)
        for i in range(1,mm):
            a = a * bigint(n-i,mod)
            b = b * bigint(i+1,mod)
        return a / b
    #
    raise ValueError
#
n,m,k = [ int(x) for x in sys.stdin.readline().split() ]
#
# const.
nn= n * n
mm= m * m
cc= combination(n*m-2,k-2)

# initialize
score=bigint(0,mod)

# scan over horizontal direction
for i in range(1,n):
    score= score + bigint(i * mm * (n-i),mod) * cc

# scan over vertical direction
for i in range(1,m):
    score= score + bigint(i * nn * (m-i),mod) * cc
#
print( score )

Submission status: Accepted

Solution code:
MOD = 10**9 + 7
list_size = 200001

f_list = [1] * list_size
f_r_list = [1] * list_size

for i in range(list_size - 1):
	f_list[i + 1] = int((f_list[i] * (i + 2)) % MOD)

f_r_list[-1] = pow(f_list[-1], MOD - 2, MOD)

for i in range(2, list_size + 1):
	f_r_list[-i] = int((f_r_list[-i + 1] * (list_size + 2 - i)) % MOD)

def comb(n, r):
	if n < r:
		return 0
	elif n == 0 or r == 0 or n == r:
		return 1
	else:
		return (((f_list[n - 1] * f_r_list[n - r - 1]) % MOD) * f_r_list[r - 1]) % MOD 

n, m, k = map(int, input().split())
print(((n+m)*k*(k-1))*comb(n*m, k)*f_r_list[2]%MOD)

Submission status: Accepted

Solution code:
def e_cell_distance(N, M, K, MOD=10**9 + 7):
    class Combination(object):
        """
        組み合わせ
        参考: https://harigami.net/contents?id=5f169f85-5707-4137-87a5-f0068749d9bb
        """
        __slots__ = ["mod", "factorial", "inverse"]

        def __init__(self, max_n: int = 10**6, mod: int = 10**9 + 7):
            fac, inv = [1], []
            fac_append, inv_append = fac.append, inv.append

            for i in range(1, max_n + 1):
                fac_append(fac[-1] * i % mod)

            inv_append(pow(fac[-1], mod - 2, mod))

            for i in range(max_n, 0, -1):
                inv_append(inv[-1] * i % mod)

            self.mod, self.factorial, self.inverse = mod, fac, inv[::-1]

        def combination(self, n, r):
            if r == n or r == 0:
                return 1
            if r > n:
                return 0
            return self.factorial[n] * self.inverse[r] * self.inverse[n - r] % self.mod

    comb = Combination(N * M).combination(N * M - 2, K - 2)
    t1 = sum([d * (M - d) * (N**2) for d in range(1, M)])
    t2 = sum([d * (N - d) * (M**2) for d in range(1, N)])
    t = (t1 + t2) % MOD
    return (comb * t) % MOD

N, M, K = [int(i) for i in input().split()]
print(e_cell_distance(N, M, K))

Submission status: Accepted

Solution code:
def power_mod(a,b,mod=10**9+7):
    i,temp,box=0,b,[]
    while(2**i<=b):
        i+=1
    for j in range(i-1,-1,-1):
        box=[[j,temp//2**j]]+box
        temp-=2**j*(temp//2**j)
    box[0].append(a)
    ans=box[0][1]*a%mod
    for j in range(1,i):
        box[j].append(box[j-1][2]**2%mod)
        if box[j][1]==1:
            ans=(ans*box[j][2])%mod
    return ans
def n_func(n,mod=10**9+7):
    ans=1
    for i in range(1,n+1):
        ans=(ans*i)%mod
    return ans
def nPr(n,r,mod=10**9+7):
    ans=n_func(n-r,mod)
    ans=power_mod(ans,mod-2,mod)
    return ans*n_func(n,mod)%mod
def nCr(n,r,mod=10**9+7):
    ans=n_func(n-r,mod)*n_func(r,mod)%mod
    ans=power_mod(ans,mod-2,mod)
    return ans*n_func(n,mod)%mod

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

sum_=0
for i in range(N):
    a=min(abs(i),abs(N-i-1))
    b=max(abs(i),abs(N-i-1))
    sum_+=(M**2)*((a*(a+1)//2)+(b*(b+1)//2))
for i in range(M):
    a=min(abs(i),abs(M-i-1))
    b=max(abs(i),abs(M-i-1))
    sum_+=(N**2)*((a*(a+1)//2)+(b*(b+1)//2))
print((keisuu * (sum_//2))%mod)

Submission status: Accepted

Solution code:
MOD = 10**9 + 7
list_size = 200001

f_list = [1] * list_size
f_r_list = [1] * list_size

for i in range(list_size - 1):
	f_list[i + 1] = int((f_list[i] * (i + 2)) % MOD)

f_r_list[-1] = pow(f_list[-1], MOD - 2, MOD)

for i in range(2, list_size + 1):
	f_r_list[-i] = int((f_r_list[-i + 1] * (list_size + 2 - i)) % MOD)

def comb(n, r):
	if n < r:
		return 0
	elif n == 0 or r == 0 or n == r:
		return 1
	else:
		return (((f_list[n - 1] * f_r_list[n - r - 1]) % MOD) * f_r_list[r - 1]) % MOD 

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

Submission status: Accepted

Solution code:
class Combination:

    def __init__(self, n, MOD):
        self.fact = [1]
        for i in range(1, n + 1):
            self.fact.append(self.fact[-1] * i % MOD)
        self.inv_fact = [pow(self.fact[i] ,MOD - 2 ,MOD) for i in range(n + 1)]
        self.MOD = MOD

    def factorial(self, k):
        '''k!を求める'''
        return self.fact[k]

    def inverse_factorial(self, k):
        '''k!の逆元を求める'''
        return self.inv_fact[k]

    def combination(self, k, r):
        '''kCrを求める'''
        return (self.fact[k] * self.inv_fact[k - r] * self.inv_fact[r]) % self.MOD
      
h, w, k = map(int, input().split())
MOD = 10**9 + 7
comb = Combination(h*w, MOD)

kumi = comb.combination(h*w - 2, k - 2)
ans = 0

for d in range(0, h):
    ans += d * (h - d) * kumi * w * w
    ans %= MOD

for d in range(0, w):
    ans += d * (w - d) * kumi * h * h
    ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
class FactMod:

    def __init__(self, n, mod):
        self.mod = mod
        self.f = [1] * (n + 1)
        for i in range(1, n + 1):
            self.f[i] = self.f[i - 1] * i % mod

        self.inv = [pow(self.f[-1], mod - 2, mod)]
        for i in reversed(range(1, n + 1)):
            self.inv.append(self.inv[-1] * i % mod)
        self.inv.reverse()

    def fact(self, n):
        """
        :return: n!
        """
        return self.f[n]

    def comb(self, n, r):
        """
        :return: nCr
        """
        return self.f[n] * self.inv[n - r] * self.inv[r] % self.mod


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

NM = N * M

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

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

factmod = FactMod(NM - 2, mod)
ans *= factmod.comb(NM - 2, K - 2)
ans %= mod
print(ans)

Submission status: Accepted

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

def mod_inv(a, m=MOD):
    def mod_inv_sub(a, m):
        if a == 1:
            return 1, 0
        else:
            d, r = m//a, m % a
            x, y = mod_inv_sub(r, a)
            return y - d*x, x

    x = mod_inv_sub(a,m)[0]
    if x < 0:
        x += (-x//m + 1) * m
    return x

factor = 1
# MN-2 C K-2 = MN-2 C MN-K = MN-2 C L
L = min(K-2,M*N-K)
for i in range(M*N-L-1,M*N-1):
    factor = factor * i % MOD
for i in range(1,L+1):
    factor = factor * mod_inv(i) % MOD
ans = ((M*(N-1)*(N+1) + N*(M-1)*(M+1))*M*N //6 * factor) % MOD
print(ans)

Submission status: Accepted

Solution code:

"""
xi,xjのペアにおいて、このペアは何通り出てくるか
sum(全通り)sum(i)sum(j){|xi-xj|+|yi-yj|}
和なので、どんな順序でもいい

sum(i)sum(j)sum(全通り){|xi-xj|}
sum(i)sum(j)sum(全通り){|yi-yj|}

あるi,jで固定して、sum(全通り){|xi-xj|}を求めるヤツ
固定したi,jが現れる回数は、

pat = NM-2_C_K-2 こいつはどこでも一緒

pat*sum(i)sum(j){|xi-xj|}を計算する
すべてのi,j(i>j)ペアにおいて、xi,xjの和は
sum(i=1,N){i*(N-i)}
"""
from math import factorial

N,M,K = map(int,input().split())
mod = 10**9+7
fa = 1
num = N*M - 2
# 固定したときの通り数
# フェルマーの小定理をつかって、mod(M)でのcombinationが高速で求まる
# http://keita-matsushita.hatenablog.com/entry/2016/12/05/184011
def mod_combination(n,r,mod):
    if n<0 or r<0 or n<r:
        return 0
    if n==0 or r == 0:
        return 1
    a = factorial(n) % mod
    b = factorial(r) % mod
    c = factorial(n-r) % mod
    return (a*pow(b,mod-2,mod)*pow(c,mod-2,mod)) % mod 

pat = mod_combination(N*M-2,K-2,mod)

n_x = M**2*((N-1)*N*(N+1))//6
n_y = N**2*((M-1)*M*(M+1))//6
print(pat*(n_x+n_y)%mod)

Submission status: Accepted

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

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

def mCn(m,n):
    return math.factorial(m)//(math.factorial(n)*math.factorial(m-n)) % mod

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

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

for i in range( 2, N1 + 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 i in range(1,M):
    ans += (M-i)*N**2*i*(cmb(M*N-2,K-2,mod))
    if ans > mod:
        ans = ans % mod

for i in range(1,N):
    ans += (N-i)*M**2*i*(cmb(M*N-2,K-2,mod))
    if ans > mod:
        ans = ans % mod

print(ans)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, log2
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N, M, K = MAP()

def C(n, r):
	return (((factorial[n] * power(factorial[r], MOD-2) % MOD) * power(factorial[n-r], MOD-2)) % MOD)

def power(x, y):
	if y == 0:
		return 1
	elif y == 1:
		return x % MOD
	elif y % 2 == 0:
		return power(x, int(y/2)) ** 2 % MOD
	else:
		return power(x, int((y-1)/2)) ** 2 * x % MOD

factorial = [1]
for n in range(1, 2*10**5+1):
    factorial.append(factorial[n-1]*n%MOD)

pat = C(N*M-2, K-2)

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

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

print(pat*(X+Y)%MOD)

Submission status: Accepted

Solution code:
import math
import sys

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


def ncr(n, r, mod=None):
    """
    scipy.misc.comb または scipy.special.comb と同じ
    組み合わせの数 nCr
    :param int n:
    :param int r:
    :param int mod: 3 以上の素数であること
    :rtype: int
    """
    assert n >= r

    def inv(a):
        """
        a の逆元
        :param a:
        :return:
        """
        return pow(a, mod - 2, mod)

    if mod:
        return math.factorial(n) * inv(math.factorial(r)) * inv(math.factorial(n - r)) % mod
    else:
        return math.factorial(n) // math.factorial(r) // math.factorial(n - r)


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


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


MOD = 10 ** 9 + 7

# K == 2 の場合
k2 = (pyramid(N - 1) * M ** 2 + pyramid(M - 1) * N ** 2) % MOD
# k2 を何回使うか
c = ncr(N * M - 2, K - 2, mod=MOD)
print(k2 * c % MOD)

Submission status: Accepted

Solution code:
def powerf(a, b, md):
    """a^b mod md"""
    if b == 0:
        return 1

    if b % 2 == 0:
        pf2 = powerf(a, b // 2, md)
        return pf2**2 % md
    else:
        return (a * powerf(a, b-1, md)) % md


def comb(n, k, md):
    """nCk mod md"""
    from math import factorial

    if n < 0 or k < 0 or n < k:
        return 0
    if n == 0 and k == 0:
        return 1

    a = factorial(n) % md
    b = factorial(k) % md
    c = factorial(n-k) % md
    return a * powerf(b, md-2, md) * powerf(c, md-2, md) % md


M = 10**9 + 7

n, m, k = list(map(int, input().split()))
ans = 0
for dx in range(1, m):
    ans += dx * (m - dx) * n**2

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

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

Submission status: Accepted

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-


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

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

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

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


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


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

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