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:
#!python3

def LI():
    return list(map(int, input().split()))

# input
N, M, K = LI()

MOD = 10 ** 9 + 7
MAX = 10 ** 5 * 2
fac, finv, inv = [None] * MAX, [None] * MAX, [None] * MAX


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


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


def s(x):
    return x * (x + 1) // 2


def cal(a, b):
    ret = a * s(b - 1) + b * s(a - 1)
    return ret % MOD


def main():
    comb_init()
    ans = 0
    for i in range(N):
        for j in range(M):
            v = cal(N - i, M - j) + cal(N - i, j + 1) - (s(j) + s(N - i - 1))
            ans = (ans + v) % MOD

    ans = ans * comb(N * M - 2, K - 2) % MOD
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N,M,K=map(int,input().split())
MOD=10**9+7
ans=0
x,y=1,1
k=min(K-2,N*M-K)
for i in range(k):
    x*=N*M-2-i
    y*=k-i
    x%=MOD
    y%=MOD
comb=x*pow(y,MOD-2,MOD)
comb%=MOD
for i in range(1,N):
    a=i*comb*(N-i)*M**2
    ans+=a
    ans%=MOD
for i in range(1,M):
    a=i*comb*(M-i)*N**2
    ans+=a
    ans%=MOD
print(ans%MOD)

Submission status: Accepted

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

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

ans=0
k=MODCOMB(N*M-2, K-2)
for sa in range(1, N):
  ans=(ans+sa*(N-sa)*M*M*k)%MOD
    
for sa in range(1, M):
  ans=(ans+sa*(M-sa)*N*N*k)%MOD
    
print(ans)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    #from math import gcd

    #inf = 10**17
    mod = 10**9 + 7

    # max_nCrまで調べられる
    max_n = 4*10**5
    fac, inv = [1]*(max_n+1), [0]*(max_n+1)
    for i in range(2, max_n+1):
        fac[i] = fac[i-1] * i % mod
    inv[-1] = pow(fac[-1], mod-2, mod)
    for i in range(max_n, 0, -1):
        inv[i-1] = inv[i] * i % mod
    
    # nCrを求める
    def ncr(n, r):
        return fac[n]*inv[r]*inv[n-r]%mod

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

    base = ncr(n*m-2, k-2)

    res = 0
    # x方向
    for i in range(1, m):
        res += n**2 * i * (m-i)
        res %= mod

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

    print(res*base%mod)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def combination_mod(n,r,MOD=10**9+7):
    n_=1
    for i in range(1,n+1):
        n_=(n_*i)%MOD
    r_=1
    for i in range(1,r+1):
        r_=(r_*i)%MOD
    nr_=1
    for i in range(1,n-r+1):
        nr_=(nr_*i)%MOD

    power_r=pow(r_,MOD-2,MOD)
    power_nr=pow(nr_,MOD-2,MOD)

    return (n_*power_r*power_nr)%MOD


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

    MOD=10**9+7
    num=combination_mod(N*M-2,K-2)

    col_ans=0
    row_ans=0

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

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

    ans=(col_ans+row_ans)%MOD

    print(ans)

if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
from operator import mul
from functools import reduce
from fractions import gcd
import math
import bisect
import itertools
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
INF = float("inf")

MOD = 1000000007
class Combination(object):
    def __init__(self, N, MOD):
        self.fac = [0] * (N + 1)
        self.inv = [0] * (N + 1)
        self.finv = [0] * (N + 1)
        self.fac[0] = 1
        self.finv[0] = 1
        if N > 0:
            self.fac[1] = 1
            self.inv[1] = 1
            self.finv[1] = 1
 
        # 前計算
        for i in range(2, N + 1):
            self.fac[i] = self.fac[i - 1] * i % MOD
            self.inv[i] = self.inv[MOD % i] * (MOD - (MOD // i)) % MOD
            self.finv[i] = self.finv[i - 1] * self.inv[i] % MOD
 
    def com(self, N, k):
        return (self.fac[N] * self.finv[k] * self.finv[N - k]) % MOD


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

    ans = 0
    Com = Combination(N*M-2, MOD)
    a = Com.com(N*M-2, K-2)
    for dx in range(1, M):
        b = (M-dx) * N * N
        ans += a * b * dx
        ans %= MOD
    for dy in range(1, N):
        b = (N-dy) * M * M
        ans += a * b * dy
        ans %= MOD
    
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def comb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

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

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

for d in range(1, N):
    cnt = (N-d)*M**2
    cnt %= MOD
    cnt *= comb(N*M-2, K-2, MOD)
    sumx += d*cnt
    sumx %= MOD

for d in range(1, M):
    cnt = (M-d)*N**2
    cnt %= MOD
    cnt *= comb(N*M-2, K-2, MOD)
    sumy += d*cnt
    sumy %= MOD
print((sumx + sumy)%MOD)

Submission status: Accepted

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

fac = [1] * n*m
finv = [1] * n*m
inv = [1] * n*m

ans = 0
def COMinit():
    for i in range(2, n*m):
        fac[i] = fac[i - 1] * i % mod
        inv[i] = mod - inv[mod % i] * (mod // i) % mod
        finv[i] = finv[i - 1] * inv[i] % mod


def COM(n, k):
    if n < 0 or k < 0 or n < k:
        return 0
    return fac[n] * (finv[k] * finv[n - k] % mod) % mod
COMinit()
for i in range(1, n):
    ans += (COM(n*m - 2, k-2)) * ((n-i)*i * m**2)%mod
for j in range(1, m):
    ans += (COM(n*m - 2, k-2)) * ((m-j)*j * n**2)%mod
print(ans%mod)

Submission status: Accepted

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

def make_array_for_comb(N, mod=10**9+7):
    fact = [1,1]
    fact_inv = [1,1]
    inv = [0,1]
    for i in range(2, N+1):
        fact.append((fact[-1]*i) % mod)
        inv.append((-inv[mod%i] * (mod//i)) % mod)
        fact_inv.append((fact_inv[-1]*inv[i]) % mod)
    return fact, fact_inv

def comb(n, r, mod=10**9+7):
  if (r < 0) or (n < r):
      return 0
  r = min(r, n - r)
  return fact[n] * fact_inv[r] * fact_inv[n-r] % mod

fact, fact_inv = make_array_for_comb(n*m,mod)

l = comb(n*m-2,k-2,mod)
ans = 0
for a in range(1,n+1):
  ans += a*m*(a-1)*m
  ans -= a*m*(n-a)*m
ans %= mod

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

print(ans*l%mod)

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def comb_mod(n, r):
    res = 1
    r = min(n - r, r)

    for i in range(r):
        res *= (n - i)
        res %= MOD
        res *= pow((r - i), MOD - 2, MOD)

    return res


def main():
    n, m, k = list(map(int, readline().split()))

    com = comb_mod(n * m - 2, k - 2)
    x = 0
    y = 0

    for i in range(n):
        right = n - 1 - i
        x += (right + 1) * right // 2
        x %= MOD

    for i in range(m):
        down = m - 1 - i
        y += (down + 1) * down // 2
        y %= MOD

    ans = 0
    ans += m ** 2 * x * com
    ans += n ** 2 * y * com
    ans %= MOD

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
input = lambda:sys.stdin.readline().rstrip()

class modfact(object):
    def __init__(self, n):
        fact, invfact = [1] * (n + 1), [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, self._invfact = fact, invfact

    def inv(self, n):
        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] % MOD * 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():
    m, n, k = map(int, input().split())
    mf = modfact(m * n - 2)
    res = 0
    for s in range(1, m):
        res += n * n * (m - s) * s
        res %= MOD
    for t in range(1, n):
        res += m * m * (n - t) * t
        res %= MOD
    res *= mf.comb(m * n - 2, k - 2)
    res %= MOD
    print(res)
resolve()

Submission status: Accepted

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

mod = 10**9 + 7
n = 2*10**5

fact = [1]*(n+1)
rfact = [1]*(n+1)
r = 1
for i in range(1, n+1):
  fact[i] = r = r * i % mod
rfact[n] = r = pow(fact[n], mod-2, mod)
for i in range(n, 0, -1):
  rfact[i-1] = r = r * i % mod

def comb(n, k):
  return fact[n] * rfact[k] * rfact[n-k] % mod

base = comb(N*M-2,K-2)
first = 0
for i in range(N):
  for j in range(M):
    first += (i+j)
dp = [0]*M
dp[0] = first
for i in range(1,M):
  dp[i] = dp[i-1] - (M-2*i) * N
SUM = sum(dp)
dp2 = [0]*N
dp2[0] = SUM
for i in range(1,N):
  dp2[i] = dp2[i-1] - (N-2*i) * (M ** 2)
SUM = sum(dp2)
ans = comb(N*M-2,K-2) * (SUM % mod) * pow(2,mod-2,mod)
ans %= mod
print(ans)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
mod = 10**9+7

class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

comb = Combination(2 * 100000)

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

    """
    xについてだけ考えればいいのはOK
    この後だが、xi, xjを固定したときに\Sum_{置き方} |xi - xj|を求めればよい。
    （シグマの順番を入れ替えた。つまりxiとxjに駒が置かれるような配置が何通りあるかを求めたい。）
    （iとjに騙されないこと！xi, xjと書くんじゃなくてx, x'と書いた方が分かりやすいかもしれない。）

    これは単純にcomb(NM-2, K-2)なので一応これで解けた。すなわち
        ans = \Sum_{xi, xj} |xi - xj| * comb(NM-2, K-2)

    しかしi, jに関してそれぞれforループを回しているのでこれだと間に合わない。
    まずcomb(NM-2, K-2)はi, jに依存しないので二重forループの外に出せる。
    そして\Sum_{i<=j}|xi-xj|だが、|xi-xj|=dとなる(i, j)の組は(N-d)*M^2個になる。（解説放送参照）
    """

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




if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n, m, k = [int(i) for i in input().split()]
mod = 10**9+7


def kai(x, p=mod):
    a = 1
    for i in range(1, x + 1):
        a *= i
        a %= p
    return a


def comb(a, b, p=mod):
    if a < 0 or b < 0:
        return 0
    elif a < b:
        return 0
    c = 1
    c *= kai(a, p)
    c *= pow(kai(b, p), p - 2, p)
    c *= pow(kai(a - b, p), p - 2, p)
    return c % p


ans = 0
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 *= comb(n * m - 2, k - 2)
ans %= mod
print(ans)

Submission status: Accepted

Solution code:
class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        if n < r:
            return 0
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

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

    ans *= comb(N*M-2,K-2)
    ans %= MOD
    print(ans)



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from itertools import accumulate, combinations, permutations, product
# from math import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

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

# MOD combination
def cmb(n, r, mod=10**9+7):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

N = 2*10**5+10
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
for i in range(n):
    ans+=i*(n-i)*m*m*cmb(n*m-2,k-2)
    ans%=mod

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

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N,M,K=map(int,input().split())
    
    def COMinit(n,MOD):
        fac,finv,inv=[0]*max(2,n+1),[0]*max(2,n+1),[0]*max(2,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%MOD
            inv[i]=MOD-inv[MOD%i]*(MOD//i)%MOD
            finv[i]=finv[i-1]*inv[i]%MOD
        return fac,finv,inv
    
    fac,finv,inv=COMinit(N*M,MOD)
    
    def COM(n, k, MOD):
        if n<k or n<0 or k<0:
            return 0
        return fac[n]*(finv[k]*finv[n-k]%MOD)%MOD
    
    ans=0
    for a,b in [(N,M),(M,N)]:
        for i in range(1,a):
            ans+=(i*(a-i)*b**2)
            ans%=MOD
    ans*=COM(N*M-2,K-2,MOD)
    ans%=MOD
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
MAX = 2*10**5+100
MOD = 10**9+7
fact = [0]*MAX #fact[i]: i!
inv = [0]*MAX #inv[i]: iの逆元
finv = [0]*MAX #finv[i]: i!の逆元
fact[0] = 1
fact[1] = 1
finv[0] = 1
finv[1] = 1
inv[1] = 1
    
for i in range(2, MAX):
    fact[i] = fact[i-1]*i%MOD
    inv[i] = MOD-inv[MOD%i]*(MOD//i)%MOD
    finv[i] = finv[i-1]*inv[i]%MOD

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

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

for d in range(1, N):
    ans += d*(N-d)*M**2
    ans %= MOD
    
for d in range(1, M):
    ans += d*(M-d)*N**2
    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())
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
g1=[1,1]
g2=[1,1]
inverse=[0,1]
for i in range(2,N*M+1):
    g1.append((g1[-1]*i)%mod)
    inverse.append((-inverse[mod%i]*(mod//i))%mod)
    g2.append((g2[-1]*inverse[-1])%mod)
ans=0
for i in range(1,N):
  ans+=i*(N-i)*M*M
for j in range(1,M):
  ans+=j*(M-j)*N*N
ans*=cmb(N*M-2,K-2,mod)
print(ans%mod)

Submission status: Accepted

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

ans = 0
mod = 10**9+7

def cmb(n, r, mod):
    if r<0 or r>n:
        return 0
    r = min(n, 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, N*M+1):
    g1.append((g1[-1] * i) % mod)
    inverse.append((-inverse[mod % i] * (mod//i)) % mod)
    g2.append((g2[-1] * inverse[-1]) % mod)

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

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

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

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

Submission status: Accepted

Solution code:
# E - Cell Distance

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

difx = 0
dify = 0

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

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

def comb_mod(n, r, p):
    num = 1
    den = 1
    r = min(r, n-r)
    for i in range(r):
        num = (num * (n-i))%p
        den = (den * (i+1))%p
    return num * pow(den, p-2, p)  

pat = comb_mod(n*m-2, k-2, mod)

ans = ((difx + dify) * pat)%mod

print(ans)

Submission status: Accepted

Solution code:
N, M, K = map(int, input().split())
mod = int(1e9) + 7
fact = [1 for _ in range(N*M+1)]
invf = [1 for _ in range(N*M+1)]
def inved(a):
  x, y, u, v, k, l = 1, 0, 0, 1, a, mod
  while l != 0:
    x, y, u, v = u, v, x - u * (k // l), y - v * (k // l)
    k, l = l, k % l
  return x % mod
for i in range(N*M):
  fact[i+1] = (fact[i] * (i + 1)) % mod
invf[-1] = inved(fact[-1])
for i in range(N*M, 0, -1):
  invf[i-1] = (invf[i] * i) % mod
Z = (fact[M*N-2] * invf[K-2] * invf[M*N-K]) % mod
X = M * (N + 1) * (N - 1)
X %= mod
Y = N * (M + 1) * (M - 1)
Y %= mod
XY = (inved(6) * M * N * (X + Y)) % mod
print((XY * Z) % mod)

Submission status: Accepted

Solution code:
n,m,k=map(int,input().split())
mod=10**9+7
f=[1]
for i in range(2*10**5+7):f+=[f[-1]*(i+1)%mod]
def comb(a,b):return f[a]*pow(f[b],mod-2,mod)*pow(f[a-b],mod-2,mod)%mod
ans=0
for i in range(1,n):
  ans+=(i*(n-i)*m**2)*(comb(n*m-2,k-2))
  ans%=mod
for i in range(1,m):
  ans+=(i*(m-i)*n**2)*(comb(n*m-2,k-2))
  ans%=mod
print(ans)

Submission status: Accepted

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

def powmod(a,p):
  if p==0:
    return 1
  elif p==1:
    return a
  else:
    pow2=powmod(a,p//2)
    if p%2==0:
      return (pow2**2)%MOD
    else:
      return (a*pow2**2)%MOD

def invmod(a):
  return powmod(a,MOD-2)

def comb_mod(n,r):
  nPr=1
  fact_r=1
  for i in range(r):
    nPr*=n-i
    nPr%=MOD
    fact_r*=r-i
    fact_r%=MOD  
  return (nPr*invmod(fact_r))%MOD

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

comb=comb_mod(N*M-2,K-2)
print(comb*(answer_tate+answer_yoko)%MOD)

Submission status: Accepted

Solution code:
import math
N,M,K=map(int,input().split())
mod=10**9+7
ans=0
for i in range(1,N):
  l=(N+1-i)*(N-i)//2%mod 
  ans+=l*M*M
  ans%mod
for i in range(1,M):
  l=(M+1-i)*(M-i)//2%mod 
  ans+=l*N*N
  ans%mod
  
def c_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
                                 
ans*=c_count(M*N-2,K-2)%mod
print(ans%mod)

Submission status: Accepted

Solution code:
def comb(n, k, mod=10**9+7):
    num = den = 1
    for i in range(k):
        num = num * (n-i) % mod
        den = den * (i+1) % mod
    return num * pow(den, mod-2, mod) % mod

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

Submission status: Accepted

Solution code:
MOD = 10**9 + 7

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

def getComb(n, k, MOD):
    if n < k:
        return 0
    if n-k < k:
        k = n-k
    comb = 1
    for x in range(n-k+1, n+1):
        comb = (comb * x) % MOD
    d = 1
    for x in range(1, k+1):
        d = (d * x) % MOD
    comb *= pow(d, MOD-2, MOD)
    return comb % MOD

comb = getComb(N*M-2, K-2, MOD)

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

for j in range(M):
    ans += j*(M-j)*N*N
    ans %= MOD

ans *= comb
ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def cmb(n, r, mod=10 ** 9 + 7):
    if r < 0 or n < r:
        return 0
    r = min(r, n - r)
    numerator, denominator = 1, 1
    for i in range(1, r + 1):
        numerator = (numerator * (n + 1 - i)) % mod
        denominator = (denominator * i) % mod
    return numerator * pow(denominator, mod - 2, mod) % mod


def solve():
    N, M, K = map(int, rl().split())
    MOD = 10 ** 9 + 7
    
    ans = 0
    for i in range(N):
        for j in range(M):
            tmp = (N - i) * (M - j) * (i + j) % MOD
            if i != 0 and j != 0:
                tmp *= 2
            ans = (ans + tmp) % MOD
    ans = ans * cmb(N * M - 2, K - 2) % MOD
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
MOD = 10**9 + 7
N = 10**6 + 10

fact = [1]*(N+1)
rfact = [1]*(N+1)
r = 1
for i in range(1, N+1):
  fact[i] = r = r * i % MOD
rfact[N] = r = pow(fact[N], MOD-2, MOD)
for i in range(N, 0, -1):
  rfact[i-1] = r = r * i % MOD

# nPk (mod MOD) を求める
def perm(n, k):
  return fact[n] * rfact[n-k] % MOD

# nCk (mod MOD) を求める
def comb(n, k):
  return fact[n] * rfact[k] * rfact[n-k] % MOD

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

p = comb(n*m-2, k-2)

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

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

print(ans)

Submission status: Accepted

Solution code:


def modinv(a, mod):
    b = mod
    x, u = 1, 0
    while b:
        q = a//b
        a, b = b, a-q*b
        x, u = u, x-q*u
    x %= mod
    return x


def mod_nCr_init(n, mod):
    fac[0] = fac[1] = 1
    facinv[0] = facinv[1] = 1
    inv[1] = 1
    for i in range(2, n):
        fac[i] = fac[i-1] * i % mod
        inv[i] = -inv[mod % i] * (mod // i) % mod
        facinv[i] = facinv[i-1] * inv[i] % mod


def mod_nCr(n, r, mod):
    if n < r or n < 0 or r < 0:
        return 0
    return fac[n] * (facinv[r] * facinv[n-r] % mod) % mod


N, M, K = map(int, input().split())
fac = [0]*(N*M)
facinv = [0]*(N*M)
inv = [0]*(N*M)

mod = 10**9 + 7
mod_nCr_init(N*M, mod)
C = mod_nCr(N*M-2, K-2, mod)

ans = 0
for _ in [0, 0]:
    for d in range(1, N):
        ans += (N-d)*M*M*d*C

    N, M = M, N

print(ans % mod)

Submission status: Accepted

Solution code:
class Calc:
    def __init__(self, max_value, mod):
        """combination(max_value, all)"""
        fact = [-1] * (max_value + 1)
        fact[0] = 1
        fact[1] = 1
        for x in range(2, max_value + 1):
            fact[x] = x * fact[x - 1] % mod

        invs = [1] * (max_value + 1)
        invs[max_value] = pow(fact[max_value], mod - 2, mod)
        for x in range(max_value - 1, 0, -1):
            invs[x] = invs[x + 1] * (x + 1) % mod

        self.fact = fact
        self.invs = invs
        self.mod = mod

    def combination(self, n, r):
        if n - r < r:
            return self.combination(n, n - r)
        if r < 0:
            return 0
        if r == 0:
            return 1
        if r == 1:
            return n
        return self.fact[n] * self.invs[r] * self.invs[n - r] % self.mod


def main():
    MOD = 10 ** 9 + 7

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

    calc = Calc(max_value=N * M - 2, mod=MOD)

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

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

    ans = (xsum + ysum) * calc.combination(N * M - 2, K - 2) % MOD

    print(ans)


if __name__ == '__main__':
    main()

# import sys
#
# sys.setrecursionlimit(10 ** 7)
#
# input = sys.stdin.readline
# rstrip()
# int(input())
# map(int, input().split())

Submission status: Accepted

Solution code:
import sys
mod = 7 + 10 ** 9

def comb(n, r, fact, revfact):
    return (fact[n] * revfact[n-r] * revfact[r]) % mod
def solve():
    input = sys.stdin.readline
    N, M, K = map(int, input().split())
    fact = [1] * (N * M + 1)
    for i in range(1, N * M + 1): fact[i] = (fact[i-1] * i) % mod
    revfact = [1] * ( N * M + 1)
    revfact[N * M] = pow(fact[N * M], mod-2, mod)
    for i in reversed(range(1, N * M)): revfact[i] = ((i + 1) * revfact[i+1]) % mod

    others = comb(N * M - 2, K - 2, fact, revfact)
    pair_type = 0
    for i in range(N): #縦の距離がi
        if i == 0:
            for j in range(1, M): #横の距離がj
                pair_type += (i + j) * (N - i) * (M - j) % mod
                pair_type %= mod
        else:
            for j in range(M):
                if j == 0: pair_type += (i + j) * (N - i) * (M - j) % mod
                else: pair_type += 2 * (i + j) * (N - i) * (M - j) % mod
                pair_type %= mod
    
    print(pair_type * others % mod)
    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
class Combination:
    def __init__(self, size, mod=10**9 + 7):
        self.size = size + 2
        self.mod = mod
        self.fact = [1, 1] + [0] * size
        self.factInv = [1, 1] + [0] * size
        self.inv = [0, 1] + [0] * size

        for i in range(2, self.size):
            self.fact[i] = self.fact[i - 1] * i % self.mod
            self.inv[i] = -self.inv[self.mod % i] * (self.mod // i) % self.mod
            self.factInv[i] = self.factInv[i - 1] * self.inv[i] % self.mod

    def npr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * self.factInv[n - r] % self.mod

    def ncr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * (self.factInv[r] * self.factInv[n - r] % self.mod) % self.mod

    def nhr(self, n, r):  # 重複組合せ
        return self.ncr(n + r - 1, n - 1)

    def factN(self, n):
        if n < 0:
            return 0
        return self.fact[n]

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

S = 0
for x in range(1, N):
    S += (N - x) * (M**2) * x
for y in range(1, M):
    S += (M - y) * (N**2) * y

ans = S * comb.ncr(N * M - 2, K - 2)
print(ans % MOD)

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

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

invt = InverseTable(mod, 10**6)
# maxnum=10**6だとテーブル生成に200ms程かかるので（Pythonだと1000msほど）
# 最大生成領域は問題ごとに要検討
for i in range(n):
  for j in range(m):
    # print(i,j,(i * (i+1) // 2 + (n-1-i) * (n-i) //2 + j * (j+1) // 2 + (m-1-j) * (m-j) //2) * invt.cmb(nm-2,k-2))
    ans += ((i * (i+1) // 2 + (n-1-i) * (n-i) //2) * m + (j * (j+1) // 2 + (m-1-j) * (m-j) //2) * n) * invt.cmb(nm-2,k-2)
    ans %= mod
print(ans*pow(2,mod-2,mod)%mod)