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: Wrong Answer

Solution code:
LARGE = 10**9 + 7


def p_inv(k, p):
    return pow(k, p-2, p)


def nck_mod(n, k, m):
    res = 1
    for i in range(n, n-k, -1):
        res = res * i % m
    for i in range(1, k+1):
        res = res * p_inv(i, m) % m
    return res


def solve(n, m, k):
    res_1 = 0
    r = n * (n - 1) // 2
    res_1 += r
    for i in range(1, n):
        r += i
        r -= n - i
        res_1 += r
    res_2 = 0
    r = m * (m - 1) // 2
    res_2 += r
    for i in range(1, m):
        r += i
        r -= m - i
        res_2 += r
    res = (res_1 * m * m + res_2 * n * n) % LARGE

    weight = nck_mod(n * m - 1, k - 1, LARGE) * p_inv(n * m - 1, LARGE) * (k - 1) * p_inv(2, LARGE) % LARGE

    return res * weight % LARGE


if __name__ == "__main__":
    #N, M, K = map(int, input().split())
    #print(solve(N, M, K))
    print(solve(2, 2, 2))
    print(solve(4, 5, 4))
    print(solve(100, 100, 5000))

Submission status: Wrong Answer

Solution code:
from math import factorial

def combinations_count(n, r):
    
#     return factorial(n) // (factorial(n - r) * factorial(r))

    result = 1
    for i in range(n-r+1,n+1):
        result = result * i % div_num

    bunbo = 1
    for i in range(1,r+1):
        bunbo *= i

    return result//bunbo

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

div_num = 10**9 + 7

cost = 0
def func(n,m,k):
    result = 0
    for d in range(1,n):
        select_2cell_cnt = (n-d)*(m**2)
        result += d * select_2cell_cnt * combinations_count(n*m-2,k-2)
        result = result % div_num
    
    return result % div_num

cost += func(N,M,K)
cost += func(M,N,K)

print(cost % div_num)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat May 25 21:24:29 2019

@author: Yamazaki Kenichi
"""

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

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] # 逆元テーブル
inv = [0, 1] # 逆元テーブル計算用テーブル

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

def a(N,M):
    return N*(N+1)//2*(M+1) + M*(M+1)//2*(N+1)
def b(N):
    return N*(N+1)//2

ans = 0
for i in range(N):
    for j in range(M):
        ans += a(i,j) + a(N-i-1,j) + a(i,M-j-1) + a(N-i-1,M-j-1)
        ans -= b(i) + b(j) + b(N-i-1) + b(M-j-1)
        ans %= mod
#        print(i,j,a(i,j),a(N-i-1,j),a(i,M-j-1),a(N-i-1,M-j-1),b(i),b(j),ans)
ans //= 2

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

Submission status: Wrong Answer

Solution code:
n,m,k=map(int,input().split())
M=10**9+7
def combi(x,y):
  c=1
  m=min(x-y,y)
  for iii in range(y):
    c=c*(x-iii)*pow(y-iii,-1)%M
  return c

rem_combi=combi(n*m-2,k-2)

def calc(num):
  out=0
  for iii in range(num):
    out+=iii*(num-iii)%M
  return out

x_cost=m*m*calc(n)%M
y_cost=n*n*calc(m)%M
ans=rem_combi*(x_cost+y_cost)%M
print(int(ans))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
inf = float('inf')
mod = 10**9+7


def INT_(n): return int(n)-1


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


def MF(): return map(float, input().split())


def MI_(): return map(INT_, input().split())


def LI(): return list(MI())


def LI_(): return [int(x) - 1 for x in input().split()]


def LF(): return list(MF())


def LIN(n: int): return [input() for _ in range(n)]


def LLIN(n: int): return [LI() for _ in range(n)]


def LLIN_(n: int): return [LI_() for _ in range(n)]


def LLI(): return [list(map(int, l.split())) for l in input()]


def I(): return int(input())


def F(): return float(input())


def ST(): return input().replace('\n', '')


def main():

    class BigCombination(object):

        def __init__(self, mod: int = 10**9+7, max_n: int = 10**6):
            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 get_combination(self, n, r):
            return self.factorial[n] * self.inverse[r] * self.inverse[n-r] % self.mod

        def get_permutation(self, n, r):
            return self.factorial[n] * self.inverse[n-r] % self.mod
    N, M, K = MI()
    comb = BigCombination(max_n=N*M)
    get_comb = comb.get_combination

    ans = 0
    for distansssss in range(N):
        ans += distansssss * (M ** 2) * (N - distansssss)
        ans %= mod
    for distansssss in range(M):
        ans += distansssss * (N ** 2) * (M - distansssss)
        ans %= mod
    ans *= get_comb(N*M-2, K-2) % mod
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
inf = float('inf')
mod = 10**9+7


def INT_(n): return int(n)-1


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


def MF(): return map(float, input().split())


def MI_(): return map(INT_, input().split())


def LI(): return list(MI())


def LI_(): return [int(x) - 1 for x in input().split()]


def LF(): return list(MF())


def LIN(n: int): return [input() for _ in range(n)]


def LLIN(n: int): return [LI() for _ in range(n)]


def LLIN_(n: int): return [LI_() for _ in range(n)]


def LLI(): return [list(map(int, l.split())) for l in input()]


def I(): return int(input())


def F(): return float(input())


def ST(): return input().replace('\n', '')


def main():

    class BigCombination(object):

        def __init__(self, mod: int = 10**9+7, max_n: int = 10**6):
            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 get_combination(self, n, r):
            return self.factorial[n] * self.inverse[r] * self.inverse[n-r] % self.mod

        def get_permutation(self, n, r):
            return self.factorial[n] * self.inverse[n-r] % self.mod
    N, M, K = MI()
    comb = BigCombination(max_n=N*M)
    get_comb = comb.get_combination

    ans = 0
    for distansssss in range(N):
        ans += distansssss * (M ** 2) * (N - distansssss)
        ans %= mod
    for distansssss in range(M):
        ans += distansssss * (N ** 2) * (M - distansssss)
        ans %= mod
    ans *= get_comb(N*M-2, K-2)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import math

inf = 7 + (10 ** 9)

def combinations_count(n, r):
    return (math.factorial(n) // (math.factorial(n - r) * math.factorial(r))) % inf

n, m, k = map(int, input().split())
ans = 0
comb = ((combinations_count((n * m) - 2, k - 2)))
n_2 = (n * n * comb) % inf
m_2 = (m * m * comb) % inf
k_m = (m * (m - 1) * (m + 1)) % inf
k_n = (n * (n - 1) * (n + 1)) % inf
ans = (k_m * n_2) + (k_n * m_2)
ans = ans % inf
print(ans)

Submission status: Wrong Answer

Solution code:
import math

inf = 7 + (10 ** 9)

def combinations_count(n, r):
    return (math.factorial(n) // (math.factorial(n - r) * math.factorial(r))) % inf

n, m, k = map(int, input().split())
ans = 0
comb = ((combinations_count((n*m)-2, k-2)))
n_2 = (n * n * comb) % inf
m_2 = (m * m * comb) % inf
min_n_m = min(n, m)
for i in range(1, min_n_m):
    ans += (( n_2 * (i)) * (m - i)) % inf
    ans = ans % inf
for i in range(1, n):
    ans += (m_2 * (i) * (n - i)) % inf
    ans = ans % inf
ans = ans % inf
print(ans)

Submission status: Wrong Answer

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(N-1):
    ans += M2 * i * (N-1-i)
    ans %= mod
    
for i in range(M-1):
    ans += N2 * (M-1-i)
    ans %= mod
        
print(ans)

Submission status: Wrong Answer

Solution code:
import math

inf = 7 + (10 ** 9)

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


def permutations_count(n, r):
    return math.factorial(n) // math.factorial(n - r)


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

Submission status: Wrong Answer

Solution code:
import math


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


def permutations_count(n, r):
    return math.factorial(n) // math.factorial(n - r)


n, m, k = map(int, input().split())
ans = 0
for i in range(m-1):
    for j in range(i+1, m):
        ans += combinations_count((n*m)-2, k-2) * n * n * (j - i)
for i in range(n-1):
    for j in range(i+1, n):
        ans += combinations_count((n*m)-2, k-2) * m * m * (j - i)
print(ans)

Submission status: Wrong Answer

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))//6)*comb(n*m, k)%MOD)

Submission status: Wrong Answer

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

sum = 0
for d in range(1, M):
    c = factorial(N*M-2) // factorial(K-2) // factorial(N*M-K)
    sum += (N*N*(M-d) * c * d) % MOD

for d in range(1, N):
    c = factorial(N*M-2) // factorial(K-2) // factorial(N*M-K)
    sum += (M*M*(N-d) * c * d) % MOD

print(sum)

Submission status: Wrong Answer

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(int((((n+m)*k*(k-1))/6)*comb(n*m, k)%MOD))

Submission status: Wrong Answer

Solution code:
def combination(n, r, MOD):
    r = min(n - r, r)
    result = 1
    for i in range(n, n - r, -1):
        result *= i
        result %= MOD
    for i in range(1, r + 1):
        result //= i
        result %= MOD
    return result


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

NM = N * M
fa = [1] * (NM + 1)

for i in range(1, NM + 1):
    fa[i] = fa[i - 1] * i
    fa[i] %= mod

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

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

ans *= combination(NM-2, K-2, mod)
ans %= mod
print(ans)

Submission status: Wrong Answer

Solution code:
from math import factorial
mod=10**9+7
def cmb(n, r):
    return factorial(n)%mod // factorial(r)%mod // factorial(n - r)%mod

n,m,k=map(int,input().split())
print(((pow(m,2,mod)*cmb(n*m-2,k-2)*sum((n-i)*i%mod for i in range(1,n))%mod)+pow(n,2,mod)*cmb(n*m-2,k-2)*sum((m-i)*i%mod for i in range(1,m))%mod)%mod)

Submission status: Wrong Answer

Solution code:
from math import factorial
N, M, K = map(int, input().split())

MOD = 10**9+7

# WARN: Require mod number m is prime number
class ModComb:
    # For nCr mod m
    def __init__(self, n_max, m):
        self._n_max = n_max
        self._m = m
        self._mod_facts = [1] * (n_max+1)       # list of n! mod m
        self._mod_inv_facts = [1] * (n_max+1)   # list of inverse r! mod m

        if not m >= 3:
            raise ValueError('Require mod number m >= 3')

        # Calc n! mod m
        for i in range(2, n_max+1):
            self._mod_facts[i] = self._mod_facts[i-1] * i % m

        # Calc inverse r! mod m
        self._mod_inv_facts[n_max] = pow(self._mod_facts[n_max], m-2, m)
        for i in range(n_max-1, 1, -1):
            self._mod_inv_facts[i] = self._mod_inv_facts[i+1] * (i+1) % m

    def calc(self, n, r):
        # Return nCr mod m
        if n > self._n_max:
            raise Exception('n is larger than n_max')

        if r == 0:
            return 1

        m = self._m
        return self._mod_facts[n] * self._mod_inv_facts[r] * self._mod_inv_facts[n-r] % m

modcomb = ModComb(N*M-2, MOD)
p = modcomb.calc(N*M-2, K-2)
print(N*M-2, K-2, p)

ans = 0
for i in range(N):
    for j in range(M):
        if i == 0 and j == 0:
            continue
        d = i+j
        cnt = (N-i) * (M-j)
        if i != 0 and j != 0:
            cnt *= 2
        ans += d * cnt % MOD
ans = ans * p % MOD

print(ans)

Submission status: Wrong Answer

Solution code:
import math
N,M,K = map(int,input().split())
pat = 1

ans_x,ans_y = 0,0
for i in range(M):
    ans_x =(ans_x + i*(M-i))%(10**9+7)
for i in range(N):
    ans_y =(ans_y + i*(N-i))%(10**9+7)
ans_x = (ans_x*(N**2))%(10**9+7)
ans_y = (ans_y*(M**2))%(10**9+7)
ans = (ans_x+ans_y)%(10**9+7)
ans = (ans*pat)%(10**9+7)
print(ans)

Submission status: Wrong Answer

Solution code:
import math
H,W,K = map(int,input().split())

MOD = 10**9 + 7
class comb(object):
    def __init__(self, N, mod):
        self.mod = mod
        self.fac = [1] * N
        for i in range(1, N):
            self.fac[i] = (self.fac[i - 1] * i) % mod
        self.inv = [1] * N
        self.inv[N - 1] = pow(self.fac[N - 1], mod - 2, mod)
        for i in range(N - 1, 0, -1):
            self.inv[i - 1] = (self.inv[i] * i) % mod
 
    def calc(self, n, k):
        return self.fac[n] * (self.inv[k] * self.inv[n - k] %
                              self.mod) % self.mod

cb = comb(H*W, MOD).calc(H*W-2, K-2)

c = 0
for d in range(1,W):
    # score * 
    c += d*(W-d)*(H**2) * cb


for d in range(1,H):
    c += d*(H-d)*(W**2) * cb

print(c)

Submission status: Wrong Answer

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

## コンビネーション計算用 ========
## https://qiita.com/derodero24/items/91b6468e66923a87f39f
mod = int(1e9+7)
g1 = [1, 1] # 元テーブル
g2 = [1, 1] # 逆元テーブル
inverse = [0, 1] # 逆元テーブル計算用テーブル

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

def combination(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
## コンビネーション計算用 --------
  

## 二つの駒の距離の総和 = cost_allpairs
var_1 = M**2 * (N-1) * N * (N+1) // 3
var_2 = N**2 * (M-1) * M * (M+1) // 3
cost_allpairs = int((var_1 + var_2) // 2)
cost_allpairs = cost_allpairs % mod ## ここでmod取っておく

## コンビネーションの計算
cmb = combination(N*M-2, K-2, mod)
print(cmb)

## 答え
ans = (cost_allpairs * cmb) % mod
print(int(ans))

Submission status: Wrong Answer

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

def expo_div_p(a: int,n: int,p: int):
    if n == 1:
        d = a
    elif n % 2 == 0:
        d = expo_div_p(a, n//2, p)**2 % p
    else:
        d = a * expo_div_p(a, n//2, p)**2 % p
    return d

def combi(x, y, p):
    c = 1
    for i in range(1,y+1):
        c *= (x-i+1) * expo_div_p(i, p-2, p)
        c %= p
    return c

ans = 0
C = combi(N*M-2, K-2, ppp)

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

print(C)
print(ans % ppp)

Submission status: Wrong Answer

Solution code:
N,M,K=map(int, input().split())
div=10**9+7
def ncr(n, r):
    res = 1
    for i in range(1, r+1):
        res = (res*n//i)%div
        n = n-1
    return res % div

result = 0
comb = ncr(N*M-2, K-2)
for d in range(1, N):
    result += d*comb*M*M*(N-d)

for d in range(1, M):
    result += d*comb*(M-d)*N*N

print(result % div)

Submission status: Wrong Answer

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

MOD = 10**9+7

def comb(n, r):
    r = n-r if n-r < r else r
    if r == 0:
        return 1
    ndfact = 1
    for i in range(n, n-r, -1):
        ndfact *= i
        ndfact %= MOD
    rfact = 1
    for i in range(r, 1, -1):
        rfact *= i
        rfact %= MOD
    return ndfact // rfact

p = comb(N*M-2, K-2) % MOD
ans = 0
for i in range(N):
    for j in range(M):
        if i == 0 and j == 0:
            continue
        d = i+j
        cnt = (N-i) * (M-j)
        if i != 0 and j != 0:
            cnt *= 2
        ans += d * cnt
        ans %= MOD

print((ans*p)%MOD)

Submission status: Wrong Answer

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

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

def comb(n, r):
    return ((fact[n]*finv[n-r])%MOD*finv[r])%MOD

cumsum = [0]*(MAX+1)
for i in range(1, max(n, m)+1):
    cumsum[i] = cumsum[i-1]+i

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

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

Submission status: Wrong Answer

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

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

def comb(n, r):
    return ((fact[n]*finv[n-r])%MOD*finv[r])%MOD

cumsum = [0]*(MAX+1)
for i in range(1, max(n, m)+1):
    cumsum[i] = cumsum[i-1]+i

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

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

Submission status: Wrong Answer

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

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

def comb(n, r):
    return ((fact[n]*finv[n-r])%MOD*finv[r])%MOD

cumsum = [0]*(MAX+1)
for i in range(1, max(n, m)+1):
    cumsum[i] = cumsum[i-1]+i

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

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

Submission status: Wrong Answer

Solution code:
from math import factorial
N, M, K = map(int, input().split())

MOD = 10**9+7

def comb(n, r):
    r = n-r if n-r < r else r
    if r == 0:
        return 1
    ndfact = 1
    for i in range(n, n-r, -1):
        ndfact *= i
        ndfact %= MOD
    return ndfact // factorial(r)

p = comb(N*M-2, K-2) % MOD
ans = 0
for i in range(N):
    for j in range(M):
        if i == 0 and j == 0:
            continue
        d = i+j
        cnt = (N-i) * (M-j)
        if i != 0 and j != 0:
            cnt *= 2
        ans += d * cnt
        ans %= MOD

print((ans*p)%MOD)

Submission status: Wrong Answer

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

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

def comb(n, r):
    return ((fact[n]*finv[n-k])%MOD*finv[k])%MOD

cumsum = [0]*(MAX+1)
for i in range(1, max(n, m)+1):
    cumsum[i] = cumsum[i-1]+i

ans = 0
for i in range(n):
    ans += (cumsum[i] + cumsum[n-i-1])*(n**2)
for i in range(m):
    ans += (cumsum[i] + cumsum[m-i-1])*(m**2)

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

Submission status: Wrong Answer

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

fact, finv = [1]*(MAX+1), [1]*(MAX+1)
for i in range(1, MAX+1):
    fact[i] = (fact[i-1]*i)%MOD
    finv[i] = pow(fact[i], MOD-2, MOD)

def comb(n, r):
    return ((fact[n]*finv[n-k])%MOD*finv[k])%MOD

cumsum = [0]*(MAX+1)
for i in range(1, max(n, m)+1):
    cumsum[i] = cumsum[i-1]+i

ans = 0
for i in range(n):
    ans += ((cumsum[i] + cumsum[n-i-1])*n%MOD)*n%MOD
for i in range(m):
    ans += ((cumsum[i] + cumsum[m-i-1])*m%MOD)*m%MOD

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

Submission status: Wrong Answer

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
a=1
b=1
c=n*m-2
x=min(c,k-2)
for i in range(x):
    a=a*(c-i)
    b=b*(i+1)
    a=a%INF
ans=(ans*a//b)%INF
print(1)
print(ans)

Submission status: Wrong Answer

Solution code:
N, M, K = map(int, input().split())
ans=0
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 #出力の制限
max = 2*10**5
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル
for i in range( 2, max + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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
a=1
b=1
c=n*m-2
x=min(c,k-2)
for i in range(x):
    a=a*(c-i)
    b=b*(i+1)
ans=(ans*a//b)%INF
print(1)
print(ans)

Submission status: Wrong Answer

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

## コンビネーション計算用 ========
## https://qiita.com/derodero24/items/91b6468e66923a87f39f
mod = int(1e9+7)
g1 = [1, 1] # 元テーブル
g2 = [1, 1] # 逆元テーブル
inverse = [0, 1] # 逆元テーブル計算用テーブル

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

def combination(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
## コンビネーション計算用 --------
  

## 二つの駒の距離の総和 = cost_allpairs
var_1 = M**2 * (N-1) * N * (N+1) / 3
var_2 = N**2 * (M-1) * M * (M+1) / 3
cost_allpairs = (var_1 + var_2) / 2
cost_allpairs = cost_allpairs % mod ## ここでmod取っておく
print(cost_allpairs)

## コンビネーションの計算
cmb = combination(N*M-2, K-2, mod)
print(cmb)

## 答え
ans = (cost_allpairs * cmb) % mod
print(int(ans))

Submission status: Wrong Answer

Solution code:
LAW = 10 ** 9 + 7

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

def calc_rev(n, law):
	if n > law:
		n, law = [law, n]
	
	pre_r = law
	pre_x = 0
	pre_y = 1
	cur_r = n
	cur_x = 1
	cur_y = 0
	
	while True:
		d = pre_r // cur_r
		r = pre_r % cur_r
		
		nxt_r = r
		nxt_x = pre_x - d * cur_x
		nxt_y = pre_y - d * cur_y
		
		if nxt_r == 1:
			ret = nxt_x
			while ret < 0:
				ret += law;
			return ret;
		elif nxt_r == 0:
			return 1
		
		pre_r = cur_r;
		pre_x = cur_x;
		pre_y = cur_y;
		cur_r = nxt_r;
		cur_x = nxt_x;
		cur_y = nxt_y;

def c(n, m, k):
	ret = 1
	for i in range(k):
		ret = (ret * (n * m - i)) % LAW
	for i in range(1, k + 1):
		ret = (ret * calc_rev(i, LAW)) % LAW
	
#	print(ret)
	
	ret = (ret * k * (k - 1)) % LAW
	ret = (ret * calc_rev((n * m) * (n * m - 1), LAW)) % LAW
	
	dx = 0
	for i in range(1, n):
		dx += i * (n - i)
	
	dy = 0
	for i in range(1, m):
		dy += i * (m - i)
	dx *= m * m
	dy *= n * n
	
#	print(dx + dy)
	
	return (ret * (dx + dy)) % LAW

print(c(N, M, K))

Submission status: Wrong Answer

Solution code:
def factorial_mod(n, mod):
    a = 1
    for i in range(1, n + 1):
        a *= i
        a %= mod
    return a


def comb_mod(n, k, mod):
    fact_n = factorial_mod(n, mod)
    fact_k = factorial_mod(k, mod)
    fact_n_k = factorial_mod(n - k, mod)
    return (fact_n * pow(fact_k, mod - 2, mod) * pow(fact_n_k, mod - 2, mod)) % mod


n, m, k = map(int, input().split())
s = 0
mod = 10 ** 9 + 7
for x in range(m):
    for i in range(x, m):
        s += abs(x-i) * n **2
for y in range(n):
    for j in range(y, n):
        s += abs(y-j) * m ** 2


print(s * comb_mod(n * m - 2, k - 2, mod))

Submission status: Wrong Answer

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

MOD = 10**9 + 7
R = 1
for i in range(K - 2):
    R = (R * (N * M - 2 - i) * pow(i + 1, MOD - 2, MOD)) % MOD

print(R % MOD)
ans = 0
for i in range(1, N + 1):
    for j in range(1, M + 1):
        u = (N - i + 1)
        d = i
        l = j
        r = (M - j + 1)
        D = 0
        D += u * l * (u + l - 2) // 2
        D += u * r * (u + r - 2) // 2
        D += d * l * (d + l - 2) // 2
        D += d * r * (d + r - 2) // 2
        D -= u * (u - 1) // 2
        D -= d * (d - 1) // 2
        D -= l * (l - 1) // 2
        D -= r * (r - 1) // 2
        ans += D

ans = (ans * R // 2) % MOD
print(ans)

Submission status: Wrong Answer

Solution code:
import math
import sys
sys.setrecursionlimit(10 ** 6 + 10)
from collections import defaultdict

from math import factorial


def combinations_count(n, r):
    return factorial(n) // (factorial(n - r) * factorial(r))



def main():
    mod = 10 ** 9 + 7
    high, width, num = map(int, input().split())
    toori = combinations_count(high * width - 2, num - 2)

    kyori = high + width - 2

    ans = 0
    for now_kyori in range(1, min(kyori, num) + 1):
        if now_kyori < high:
            ans += now_kyori * width * width * (high - now_kyori)
        if now_kyori < width:
            ans += now_kyori * high * high * (width - now_kyori)

    ans = ans * toori % mod

    print(ans)



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys,heapq
from collections import deque,defaultdict
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
R = 10**9+7
DBG = True  and False
def ddprint(x):
  if DBG:
    print(x)

def exgcd(x,y):
    if y == 0:
        return (x,1,0)
    else:
        g,b,a = exgcd(y, x%y)
        return (g, a, b-(x//y)*a)

# return y s.t. x*y mod p == 1
def modinv(x,p):
    g,a,b = exgcd(x,p)  # ax+bp = g, g=1 if mutually prime
    return a%p

def comb(p,q):
    if q==0:
        return 1
    if q > p-q:
        q = p-q
    num = p
    den = q
    for i in range(1,q):
        num = (num * (p-i))%R
        den = (den * (q-i))%R
    xden = modinv(den,R)
    return (num*xden)%R

n,m,k = inm()
x = ( (n*n*(m-1)*m*(m+1)+m*m*(n-1)*n*(n+1))//6 )%R
y = comb(n*m-2,k-2)
ddprint(x)
ddprint(y)
print((x*y)%R)

Submission status: Wrong Answer

Solution code:
def getInv(N):#Qはmod
    inv = [0] * (N + 1)
    inv[0] = 1
    inv[1] = 1
    for i in range(2, N + 1):
        inv[i] = (-(Q // i) * inv[Q%i]) % Q
    return inv

Q = 10**9+7
modinv = getInv(4*10**5)
N, M, K = map( int, input().split())
T = N*M
comb = 1
for i in range(K-2):
    comb *= T-2-i
    comb %= Q
    comb *= modinv[K-2-i]
    comb %= Q
ans = 0
for i in range(1, M):
    ans += N**2*(M-i)
    ans %= Q
for i in range(1, N):
    ans += M**2*(N-i)
    ans %= Q
ans %= Q
print( ans*comb%Q)