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:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############
N,M,K = IL()

print((((N*(N+1)*(N-1)//6)*M**2+(M*(M+1)*(M-1)//6)*N**2) * nCr(K,2)*nCr(N*M,K)*inv(nCr(N*M,2)))%MOD)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc127/tasks/abc127_e
# 自分の計算画像を参考に
# ポイントは二点
# 1. 通りを決定してからpairwiseの和→pairを先に決定してから条件を満たす通りを加算 というΣの入れ替え
# 2. 二点の全通りの差を加算は無理→二点の差は何回現れるか を加算


class ModInt:
    def __init__(self, x, MOD=10 ** 9 + 7):
        '''
        pypyじゃないと地獄みたいな遅さなので注意
        '''
        self.mod = MOD
        self.x = x % MOD

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

    __repr__ = __str__

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

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

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

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

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

    __radd__ = __add__

    def __rsub__(self, other):  # 演算の順序が逆
        if isinstance(other, ModInt):
            return ModInt(other.x - self.x, self.mod)
        else:
            return ModInt(other - self.x, self.mod)

    __rmul__ = __mul__

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

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


def combination(n, r):
    # 上記のModIntを用いた通りの数の実装
    if r > n:
        return 0  # このような通りの数は無いため便宜上こう定義する
    r = min(r, n - r)
    nf = rf = ModInt(1)
    for i in range(r):
        nf = nf * (n - i)
        rf = rf * (i + 1)
    return nf / rf


N, M, K = map(int, input().split())
C = combination(N * M - 2, K - 2)
x_term = ModInt(0)
for dx in range(1, N):
    x_term += (N - dx) * dx
x_term *= M**2

y_term = ModInt(0)
for dy in range(1, M):
    y_term += (M - dy) * dy
y_term *= N**2

print(C * (x_term + y_term))

Submission status: Accepted

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

class Comb:
    def __init__(self, n, mod=pow(10, 9)+7, f=True, i=False):
        self.n = n
        self.mod = mod
        self.factorial_table = None
        self.inverse_table = None
        if f: self.get_factorial()
        if i: self.get_inverse()
        
    def get_factorial(self):
        self.factorial_table = [1]*(self.n+1)
        for i in range(1, self.n+1):
            self.factorial_table[i] = self.factorial_table[i-1]*i%self.mod
        self.inverse_table = None
    
    def get_inverse(self):
        mod = self.mod
        self.inverse_table = [1]*(self.n+1)
        for i in range(self.n+1):
            self.inverse_table[i] = pow(self.factorial_table[i], -1, mod)
    
    def factorial(self, n):
        if self.factorial_table == None:
            return None
        return self.factorial_table[n]
    
    def inverse(self, n):
        if self.inverse_table == None:
            return None
        return self.inverse_table[n]   
    
    def permutation(self, n, k):
        if self.factorial_table == None:
            return None
        mod = self.mod
        if self.inverse_table == None:
            return self.factorial_table[n]*pow(self.factorial_table[n-k], -1, mod)%mod
        return self.factorial_table[n]*self.inverse_table[n-k]%mod
            
    def comb(self, n, k):
        mod = self.mod
        if self.factorial_table == None:
            res = 1
            for i in range(k):
                res *= n-i
                res *= i+1
                res %= mod
            return res
        if self.inverse_table == None:
            res = self.factorial_table[n]*pow(self.factorial_table[n-k], -1, mod)%mod\
                                    *pow(self.factorial_table[k], -1, mod)%mod
        else:
            res = self.factorial_table[n]*self.inverse_table[n-k]%mod\
                                    *self.inverse_table[k]%mod
        return res
    
    def recomb(self, n, k):
        if n+k-1 > self.n:
            return None
        return self.comb(n+k-1, k)
        


def main():
    n, m, k = map(int, input().split())
    mod = pow(10, 9) + 7
    
    comb = Comb(n*m, i=True)
    
    ans = 0
    
    for i in range(n):
        ans += (i) * (n-i) * m**2
        ans %= mod
        
    
    for i in range(m):
        ans += (i) * (m-i) * n**2
        ans %= mod
    
    
    
    ans *= comb.comb(n*m-2, k-2)
    ans %= mod
    
    print(ans)
    
    
if __name__ == "__main__":
    main()

Submission status: Accepted

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

#n*m-2個の中からk-2個選ぶときの組み合わせ数
cmb=1
for i in range(k-2):
  cmb*=n*m-i-2
  cmb%=mod
  cmb*=pow(i+1,mod-2,mod)
  cmb%=mod
for i in range(1,n):
  tmp=i*(n-i)
  tmp*=m**2
  tmp%=mod
  tmp*=cmb
  tmp%=mod
  ans+=tmp
  ans%=mod
for i in range(1,m):
  tmp=i*(m-i)
  tmp*=n**2
  tmp%=mod
  tmp*=cmb
  tmp%=mod
  ans+=tmp
  ans%=mod
print(ans)

Submission status: Accepted

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

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return input().rstrip().decode()
def II(): return int(input())
def FI(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()


def main():
	n,m,k=MI()
	mod=10**9+7

	ans=0

	cnt=0
	for i in range(1,m):
		cnt+=i*(m-i)
		cnt%=mod

	ans+=cnt*n*n
	ans%=mod

	cnt=0
	for i in range(1,n):
		cnt+=i*(n-i)
		cnt%=mod

	ans+=cnt*m*m
	ans%=mod

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

	finv=[]
	for i in f:
		finv.append(pow(i,mod-2,mod))
	#print(finv)

	#print(ans)

	ans*=k*(k-1)

	ans*=f[n*m-2]
	ans%=mod
	#print(ans)


	ans*=finv[n*m-2-(k-2)]
	ans%=mod
	#print(ans)


	ans*=finv[k]
	ans%=mod



	print(ans)






























if __name__ == "__main__":
	main()

Submission status: Accepted

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

mod = 10**9 + 7

# (n * m - 2)C(k - 2)
# 距離xの組 -  n - x + 1
# 横 n - x + 1
# 縦 m * m
ans = 0
for y in range(1, n):
    ans += y * (n - y) * m * m % mod
for x in range(1, m):
    ans += x * (m - x) * n * n % mod


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


# comb
for i in range(k - 2):
    ans = ans * (n * m - 2 - i) * inv(i + 1) % mod

print(ans)

Submission status: Accepted

Solution code:
MOD=10**9+7

def com(n,k,mod):
    res=1
    tmp=1
    for i in range(1,k+1):
        res=res*(n-i+1)%mod
        tmp=tmp*i%mod
    a=pow(tmp,mod-2,mod)
    return res*a%mod

N,M,K=map(int,input().split())
C=com(N*M-2,K-2,MOD)

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

Submission status: Accepted

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


def nCr(n, r, MOD=10**9 + 7):
    from functools import reduce
    if r == 0:
        return 1
    num = reduce(lambda x, y: x * y % MOD, range(n, n - r, -1))
    den = reduce(lambda x, y: x * y % MOD, range(1, r + 1))
    return num * pow(den, MOD - 2, MOD) % MOD


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

Submission status: Accepted

Solution code:

def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return x0

def modinv(a, m):
    x = xgcd(a, m)
    return x % m


max_num = 10 ** 9 + 7
res = 0
n, m, k = map(int, input().strip().split())

for d in range(1, n):
    res += (n - d) * d * m * m
    res %= max_num
for d in range(1, m):
    res += (m - d) * d * n * n
    res %= max_num

r = min(n*m-2, k-2)
for i in range(1, r+1):
    res *= n * m - 1 - i
    res %= max_num
for i in range(1, r+1):
    res *= modinv(i, max_num)
    res %= max_num

print(res)

Submission status: Accepted

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


# コンビネーション、さらに高速。あらかじめO(N)の計算をすることでのちの計算が早くなる
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] # g1[i]=i! % mod　:階乗
g2=[1,1] # g2[i]=(i!)^(-1) % mod　:階乗の逆元
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 d in range(1,n):
  tmp=d*(n-d)*m**2
  tmp%=mod
  tmp*=cmb(n*m-2,k-2,mod)
  ans+=tmp
  ans%=mod
for d in range(1,m):
  tmp=d*(m-d)*n**2
  tmp%=mod
  tmp*=cmb(n*m-2,k-2,mod)
  ans+=tmp
  ans%=mod
print(ans)

Submission status: Accepted

Solution code:
# 1 つの組を固定したとき、その他の置き方は (N*M-2)C(K-2) 通り
# x 座標が h 離れる組み合わせは、(N-h)*M*M 通り (h!=0)

def combination(n, r, mod=10**9+7):
    # nCr mod m
    # rがn/2に近いと非常に重くなる
    n1, r = n+1, min(r, n-r)
    numer = denom = 1
    for i in range(1, r+1):
        numer = numer * (n1-i) % mod
        denom = denom * i % mod
    return numer * pow(denom, mod-2, mod) % mod

def main():
    N, M, K = map(int, input().split())
    mod = 10**9 + 7
    ans1 = 0
    for h in range(1, N):
        ans1 += (N - h) * h
    ans1 = ans1 * M * M % mod
    ans2 = 0
    for w in range(1, M):
        ans2 += (M - w) * w
    ans2 = ans2 * N * N % mod
    ans = (ans1 + ans2) * combination(N*M-2, K-2) % mod
    print(ans)

main()

Submission status: Accepted

Solution code:
N,M,K=map(int,input().split())
P=10**9+7
import math
print(M*N*(M+N)*(M*N-1)//6*math.factorial(N*M-2)*pow(math.factorial(K-2),P-2,P)*pow(math.factorial(N*M-K),P-2,P)%P)

Submission status: Accepted

Solution code:
N,M,K=map(int,input().split())
P=1000000007
import math
print(M*N*(M+N)*(M*N-1)//6*math.factorial(N*M-2)*pow(math.factorial(K-2),P-2,P)*pow(math.factorial(N*M-K),P-2,P)%P)

Submission status: Accepted

Solution code:
N,M,K=map(int,input().split())
P=1000000007
import math
ans=M**2*(N-1)*N*(N+1)//6
ans+=N**2*(M-1)*M*(M+1)//6
print(ans*math.factorial(N*M-2)*pow(math.factorial(K-2),P-2,P)*pow(math.factorial(N*M-K),P-2,P)%P)

Submission status: Accepted

Solution code:
N,M,K=map(int,input().split())
P=1000000007
import math
ans=0
for A in [N,M]:
    for i in range(1,A):
        ans = (ans+(N^M^A)**2*i*(i+1)//2)%P
print(ans*math.factorial(N*M-2)*pow(math.factorial(K-2),P-2,P)*pow(math.factorial(N*M-K),P-2,P)%P)

Submission status: Accepted

Solution code:
N,M,K=map(int,input().split())
P=1000000007
f=[0]*(N*M+1)
f[0]=1
for i in range(N*M):
    f[i+1]=(i+1)*f[i]%P
ans=0
for A in [N,M]:
    for i in range(1,A):
        ans = (ans+(N^M^A)**2*i*(i+1)//2)%P
print(ans*f[N*M-2]*pow(f[K-2],P-2,P)*pow(f[N*M-K],P-2,P)%P)

Submission status: Accepted

Solution code:
N,M,K = map(int, input().split())
P=1000000007
MPL = 1
f = 1
for i in range(1, N*M-1):
    MPL = MPL * i % P
    MPL %= P
    if i == K - 2:
        f *= pow(MPL, P - 2, P)
    if i == N*M - K:
        f *= pow(MPL, P - 2, P)
MPL = MPL * f % P
ans = 0
for A in [N, M]:
    width = N ^ M ^ A
    for i in range(1, A):
        ans = (ans + width * width * i * (i + 1) // 2) % P
print(ans * MPL % P)

Submission status: Accepted

Solution code:
from functools import reduce

def combination2(n, r, MOD=10**9+7):
    if not 0 <= r <= n: return 0
    r = min(r, n - r)
    numerator = reduce(lambda x, y: x * y % MOD, range(n, n - r, -1), 1)
    denominator = reduce(lambda x, y: x * y % MOD, range(1, r + 1), 1)
    return numerator * pow(denominator, MOD - 2, MOD) % MOD

def q(x,y):
    return cn*(x**2)*(y**3-y)//6

N, M, K = map(int, input().split())
MOD=10**9+7
cn = combination2(N*M - 2, K-2, MOD)
print((q(N,M) + q(M,N))%MOD)

Submission status: Accepted

Solution code:
N,M,K=map(int,input().split())
c=[0 for i in range(N*M)]
c[1]=1
c[0]=1
mod=10**9+7
for i in range(1,N*M-1):
  c[i+1]=(i+1)*c[i]%mod
def comb(a,b):
  return c[a]*pow(c[b],mod-2,mod)*pow(c[a-b],mod-2,mod)%mod
ans=0
for i in range(N):
  ans+=i*(N-i)*pow(M,2)
  ans%=mod
for i in range(M):
  ans+=i*(M-i)*pow(N,2)%mod
  ans%=mod
ans*=comb(N*M-2,K-2)

ans%=mod
print(ans)

Submission status: Accepted

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

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return input().rstrip().decode()
def II(): return int(input())
def FI(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()

def main():
	n,m,k=MI()
	mod=10**9+7

	f=[1]
	for i in range(1,n*m+10):
		f.append((f[-1]*i)%mod)
	#print(f)

	finv=[]
	for i in f:
		finv.append(pow(i,mod-2,mod))
	#print(finv[:10])


	ans=0

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

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

	ans%=mod
	#print(ans)

	ans*=k*(k-1)
	ans%=mod

	ans*=f[n*m-2]*finv[n*m-2-(k-2)]
	ans*=finv[k]

	print(ans%mod)


















if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
def solve():
  N, M, K = map(int, input().split())
  mod = 10**9+7
  com = 1
  for i in range(1,K-1):
    com *= N*M-1-i
    com *= pow(i,mod-2,mod)
    com %= mod
  ans = com*M*N*(M*N-1)*(M+N)//6
  return ans%mod
print(solve())

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7

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

MOD = 10 ** 9 + 7
N = n * m + 10
fact = [0 for _ in range(N)]
invfact = [0 for _ in range(N)]
fact[0] = 1
for i in range(1, N):
    fact[i] = fact[i - 1] * i % MOD

invfact[N - 1] = pow(fact[N - 1], MOD - 2, MOD)

for i in range(N - 2, -1, -1):
    invfact[i] = invfact[i + 1] * (i + 1) % MOD
def nCk(n, k):
    if k < 0 or n < k:
        return 0
    else:
        return fact[n] * invfact[k] * invfact[n - k] % MOD
        
ans = 0
for i in range(n-1, 0, -1):
    ans += m * m * (i + 1) * i // 2 
    ans %= MOD
for i in range(m - 1, 0, -1):
    ans += n * n * (i + 1) * i // 2
    ans %= MOD

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

Submission status: Accepted

Solution code:
N,M,K=map(int,input().split())
mod=10**9+7
X=N*M%mod
C=[1]
for i in range(K+1):
  C.append(C[i]*(X-2-i)*pow(i+1,mod-2,mod)%mod)
P=0
for i in range(N):
  P=(P+(i*(i+1)//2)+((N-i)*(N-i-1)//2))%mod
P=P*M*M%mod
Q=0
for i in range(M):
  Q=(Q+(i*(i+1)//2)+((M-i)*(M-i-1)//2))%mod
Q=Q*N*N%mod
print((P+Q)*C[K-2]*((mod+1)//2)%mod)

Submission status: Accepted

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

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

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

ans = 0
for i in range(n*m):
    x, y = divmod(i, m)
    # x
    ans += x*m*cmb1(n*m-2, k-2, mod)*x
    ans -= (n-1-x)*m*cmb1(n*m-2, k-2, mod)*x
    # y
    ans += y*n*cmb1(n*m-2, k-2, mod)*y
    ans -= (m-1-y)*n*cmb1(n*m-2, k-2, mod)*y

ans %= mod
print(ans)

Submission status: Accepted

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

MAXN = N*M+5
fac = [1,1] + [0]*MAXN
finv = [1,1] + [0]*MAXN
inv = [0,1] + [0]*MAXN
for i in range(2,MAXN+2):
    fac[i] = fac[i-1] * i % MOD
    inv[i] = -inv[MOD%i] * (MOD // i) % MOD
    finv[i] = finv[i-1] * inv[i] % MOD

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

a = 0
for d in range(1,N):
    a += d*(N-d)*M*M
b = 0
for d in range(1,M):
    b += d*(M-d)*N*N

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

Submission status: Accepted

Solution code:
class Combination:
    def __init__(self, n_max=10**6, mod=10**9+7):
        # self._n_max = n_max
        self._fac, self._finv, self._inv = [0]*n_max, [0]*n_max, [0]*n_max
        self._fac[0], self._fac[1] = 1, 1
        self._finv[0], self._finv[1] = 1, 1
        self._inv[1] = 1
        for i in range(2, n_max):
            self._fac[i] = self._fac[i - 1] * i % MOD
            self._inv[i] = MOD - self._inv[MOD%i] * (MOD // i) % MOD
            self._finv[i] = self._finv[i - 1] * self._inv[i] % MOD
    def com(self, n, r):
        if n < r: return 0
        if n < 0 or r < 0: return 0
        return self._fac[n] * (self._finv[r] * self._finv[n - r] % MOD) % MOD


def modinv(a,m):
    b, u, v = m, 1, 0
    while b:
        t = a//b
        a -= t*b
        a,b = b,a
        u -= t * v
        u,v = v,u
    u %= m
    return u


MOD = 10**9+7
comb = Combination(10**6, MOD)
n,m,k = map(int, input().split())

ans = 0
for i in range(m):
    other_sum = i*(i+1)//2 + (m-1-i)*(m-i)//2
    # other_sum *= n
    pattern = n*n*comb.com(n*m-2,k-2)
    ans += pattern*other_sum
    ans%=MOD

for i in range(n):
    other_sum = i*(i+1)//2 + (n-1-i)*(n-i)//2
    # other_sum *= m
    pattern = m*m*comb.com(n*m-2,k-2)
    ans += pattern*other_sum
    ans%=MOD

a = modinv(2,MOD)
ans = (ans*a)%MOD
print(ans)

Submission status: Accepted

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

mod = 10**9+7
f = [1]
for i in range(n*m):
  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 dist in range(1,n):
  c=n-dist
  p=(c*m*m)%mod
  ans+=p*dist
for dist in range(1,m):
  c=m-dist
  p=(c*n*n)%mod
  ans+=p*dist
ans%=mod
print(ans*comb(n*m-2,k-2)%mod)

Submission status: Accepted

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

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

def main():
    mod=10**9+7
    """
    まず，xとyを分離する=>xだけを考えるので1行とみなす．
    いっぺんにいくつも考えられないので，コマを2つだけ置いた時を考える．
    2この組み合わせで距離が1=>M-1通り，2=>M-2通り,...,M-1=>1通り
    (以下のように考えてΣしても良いがやや面倒
        (j列目にコマを固定すると，相手との距離はj,j-1,...,1,0,1,2,...,M-j))
    実際にはN列あるので，選び方がN^2
        同じ行・列を選んだ場合は不可能だけど，どうせ距離も0なので関係ない
        
    ある2つの組みに注目した時，それを何回数えるかは，外野の並べ方に依存
    (N*M-2)C(K-2)通り
    """
    N,M,K=MI()
    
    
    def cmb(n, r, mod):
        if (r < 0) or (n < r):
            return 0
        r = min(r, n - r)
        return (fact[n] * factinv[r] * factinv[n-r])%mod

    fact=[1,1]
    factinv=[1,1]
    inv=[0,1]
    
    for i in range(2, N*M+5+ 1):
        fact.append((fact[-1] * i) % mod)
        inv.append((-inv[mod % i] * (mod // i)) % mod)
        factinv.append((factinv[-1] * inv[-1]) % mod)
    
    tempj=0
    for j in range(M):
        tempj+=(M-j)*j
        
    tempi=0
    for i in range(N):
        tempi+=(N-i)*i

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

main()

Submission status: Accepted

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

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

print(ans)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
#mod = 998244353
INF = 10**18
eps = 10**-7

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

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

ans = m*n*(m+n)*(m*n-1)//3

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

print(ans)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
#mod = 998244353
INF = 10**18
eps = 10**-7

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

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

def f1(x,y,a,b):
    return (a+b-x-y)*(a-x+1)*(b-y+1)//2

def f2(x,a):
    return (a-x)*(a-x+1)//2

ans = 0

for x in range(1,n+1):
    for y in range(1,m+1):
        a = n-x+1
        b = m-y+1
        c = m*(a*(a-1)+x*(x-1))
        d = n*(b*(b-1)+y*(y-1))
        ans += (c+d)//2
        ans %= mod

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

print(ans)

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
from collections import Counter
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())

N, M, K = map(int, input().split())
MAX = 2 * 10 ** 5 + 5
MOD = 10 ** 9 + 7

fac = [0 for i in range(MAX)]
finv = [0 for i in range(MAX)]
inv = [0 for i in range(MAX)]

def comInit(mod):
    fac[0], fac[1] = 1, 1
    finv[0], finv[1] = 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 com(n, r, mod):
    if n < r:
        return 0
    if n < 0 or r < 0:
        return 0
    return fac[n] * (finv[r] * finv[n - r] % mod) % mod

def p(n, r, mod):
    return fac[n] * finv[n - r] % mod
comInit(MOD)

xs = 0
for i in range(M):
    xs += i * (M - i)
    xs %= MOD
xs *= N ** 2
ys = 0
for i in range(N):
    ys += i * (N - i)
    ys %= MOD
ys *= M ** 2
ys %= MOD
print(((xs + ys) % MOD) * com(N * M - 2, K - 2, MOD) % MOD)

Submission status: Accepted

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

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

p = 10 ** 9 + 7
mod = 10 ** 9 + 7
n = 3 * 10 ** 5  # 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)
#一つの配置でK C 2本の線
#配置はMN C K 通り
#よって、MNCK * KC2 / MNC2 = (MN - 2)C(K - 2)回
#各2頂点間のコストは足される。
#答えは全ての2頂点間のコストの和 * (MN - 2)C(K - 2)

#全ての2頂点間のコストの和を求める
#距離 i 離れた二点の個数は (1 + 2 + ... N - i) * N
#つまり、N * (N - i + 1) * (N - i) / 2
#縦横あるので、 それぞれ足す
ans1 = 0
for i in range(1, M):
  ans1 += i * (M - i) % mod
  #print(ans1)
ans1 = (ans1 * N * N) % mod

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

#print(ans1, ans2)

ans = ans1 + ans2
print(ans * cmb(M * N - 2, K - 2, p) % mod)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
def main():
    N, M, K = map(int, input().split())
    m = 10**9+7
    # 方針: ２つの駒の距離だけ考えれば良い、それ以外K-2個の駒の位置が(N*M-2)C(K-2)通りある
    # マンハッタン距離はx方向とy方向を独立に扱える
    ans = 0
    for d in range(1,M):
        ans += (d*(M-d)%m) * pow(N,2,m) % m
        ans %= m

    for d in range(1,N):
        ans += (d*(N-d)%m) * pow(M,2,m) % m
        ans %= m

    # 答えに(NM-2)C(K-2)かける
    # K回しか処理しないから間に合う
    for r in range(K-2):
        ans *= ((N*M%m-2)%m-r)%m
        ans %= m
        ans *= pow(r+1,m-2,m)
        ans %= m
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def cmb(n, r, p):
  if (r < 0) or (n < r):
    return 0
  r = min(r, n - r)
  return fac[n]*finv[r]*finv[n-r]%p

n,m,K = map(int,input().split())
MOD = pow(10,9)+7
N = pow(10,6)
fac = [-1]*(N+1); fac[0] = 1; fac[1] = 1 #階乗
finv = [-1]*(N+1); finv[0] = 1; finv[1] = 1 #階乗の逆元
inv = [-1]*(N+1); inv[0] = 0; 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

factor = cmb(n*m-2,K-2,MOD)
X = factor*(m-1)*m*(m+1)//6*n*n%MOD
Y = factor*(n-1)*n*(n+1)//6*m*m%MOD
#print(X,Y)
ans = (X+Y)%MOD
print(ans)

Submission status: Accepted

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

MAXN = N*M+5
fac = [1,1] + [0]*MAXN
finv = [1,1] + [0]*MAXN
inv = [0,1] + [0]*MAXN
for i in range(2,MAXN+2):
    fac[i] = fac[i-1] * i % MOD
    inv[i] = -inv[MOD%i] * (MOD // i) % MOD
    finv[i] = finv[i-1] * inv[i] % MOD

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

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

Submission status: Accepted

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

factorial = [1, 1]
inverse = [1, 1]
invere_base = [0, 1]
for i in range(2, H * W + 2):
    factorial.append((factorial[-1] * i) % MOD)
    invere_base.append((-invere_base[MOD % i] * (MOD // i)) % MOD)
    inverse.append((inverse[-1] * invere_base[-1]) % MOD)


def nCr(n, r):
    if not 0 <= r <= n:
        return 0
    return factorial[n] * inverse[r] * inverse[n - r] % MOD


ans = 0
for dh in range(1, H):
    ans += dh * (H - dh) * pow(W, 2, MOD) * nCr(H * W - 2, K - 2) % MOD
    ans %= MOD
for dw in range(1, W):
    ans += dw * (W - dw) * pow(H, 2, MOD) * nCr(H * W - 2, K - 2) % MOD
    ans %= MOD

print(ans)