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: Time Limit Exceeded

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
    for i in range(1,n+1):
        for j in range(i,n+1):
            if i==j:
                ans=ans+m*m*(m-1)//2-(m-1)*m*(2*m-1)//6
            else:
                d=j-i
                ans=ans+d*m+2*d*m*(m-1)+(m-d)*m*(m-1)-M
            ans=ans%INF
else:
    (n,m)=(m,n)
    M=(m-1)*m*(2*m-1)//3
    for i in range(1,n+1):
        for j in range(i,n+1):
            if i==j:
                ans=ans+m*m*(m-1)//2-(m-1)*m*(2*m-1)//6
            else:
                d=j-i
                ans=ans+d*m+2*d*m*(m-1)+(m-d)*m*(m-1)-M
            ans=ans%INF
import math
ans=(math.factorial(n*m-2)//(math.factorial(n*m-k)*math.factorial(k-2)))*ans
ans=ans%INF
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math

def comb(n, k):
  return math.factorial(n) // (math.factorial(n - k) * math.factorial(k))

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

csum = [0 for _ in range(m*n)]
for i in range(1, n*m):
  csum[i] = csum[i-1] + i

line_total = 0
for i in range(1, n):
  line_total += csum[i] * m ** 2
#  print(line_total)
for i in range(1, m):
  line_total += csum[i] * n ** 2
#  print(line_total)
ans = ((comb(n*m, k) * csum[k-1]) // csum[n*m-1]) * line_total
#print(comb(n*m, k), csum(k), csum(n*m))
print(ans%1000000007)

Submission status: Time Limit Exceeded

Solution code:
n, m, k = map(int, input().split())
t = n * m - 2
memo = 1

for i in range(k - 2):
    memo *= t
    memo = memo // (i + 1)
    t -= 1
nmemo = (memo % (10 ** 9 + 7)) * n * n % (10 ** 9 + 7)
mmemo = (memo % (10 ** 9 + 7)) * m * m % (10 ** 9 + 7)

answer = ((n*(n+1)) % (10 ** 9 + 7)*(n-1)*mmemo//6 % (10**9+7))
answer = (answer+(((m - 1) * m) % (10 ** 9 + 7)
                  * (m + 1)*nmemo // 6)) % (10 ** 9 + 7)

print(answer)

Submission status: Time Limit Exceeded

Solution code:
n,m,k=map(int,input().split())
ans=0
INF=10**9+7
if n<=m:
    for i in range(1,n+1):
        for j in range(i,n+1):
            if i==j:
                ans=ans+m*m*(m-1)//2-(m-1)*m*(2*m-1)//6
            else:
                d=j-i
                ans=ans+d*m+2*d*m*(m-1)+(m-d)*m*(m-1)-(m-1)*m*(2*m-1)//3
            ans=ans%INF
else:
    (n,m)=(m,n)
    for i in range(1,n+1):
        for j in range(i,n+1):
            if i==j:
                ans=ans+m*m*(m-1)//2-(m-1)*m*(2*m-1)//6
            else:
                d=j-i
                ans=ans+d*m+2*d*m*(m-1)+(m-d)*m*(m-1)-(m-1)*m*(2*m-1)//3
            ans=ans%INF
import math
ans=(math.factorial(n*m-2)//(math.factorial(n*m-k)*math.factorial(k-2)))*ans
ans=ans%INF
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
import itertools

MOD = 1000000007  # type: int


def solve(N: int, M: int, K: int):
    nm = N * M

    def get_pos(i,n,m):
        return i // m , i % m

    cost = 0
    for seq in itertools.combinations(range(nm),K):
        for i in range(len(seq)-1):
            x1,y1 = get_pos(seq[i],N,M)
            for j in range(i+1,len(seq)):
                x2,y2 = get_pos(seq[j],N,M)
                cost += (abs(x1-x2) + abs(y1-y2))

    print(cost)



# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    solve(N, M, K)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import math

def comb(n, k):
  return math.factorial(n) // (math.factorial(n - k) * math.factorial(k))

def csum(n):
  total = 0
  for i in range(n):
    total += i
  return total

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

line_total = 0
for i in range(1, n):
  line_total += csum(i+1) * m ** 2
#  print(line_total)
for i in range(1, m):
  line_total += csum(i+1) * n ** 2
#  print(line_total)
ans = ((comb(n*m, k) * csum(k)) // csum(n*m)) * line_total
#print(comb(n*m, k), csum(k), csum(n*m))
print(ans%1000000007)

Submission status: Time Limit Exceeded

Solution code:
from math import factorial
n,m,K=map(int,input().split())
ans=0
t=0
def comb(n,r):
    return factorial(n)//factorial(n-r)//factorial(r)
for i in range(3,n+m+1):
    for j in range(max(1,i-n),i):
        if(j>m):
            break
        k=i-j
        if(j==1 or k==1):
            ans+=(i-2)*(m-j+1)*(n-k+1)
        else:
            ans+=(i-2)*(m-j+1)*(n-k+1)*2
print((ans*comb(n*m-2,K-2))%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
import math
n,m,k = map(int,input().split())
ss = (math.factorial(m*n)//math.factorial(k))//math.factorial(m*n-k)
s = (ss*k*(k-1))//2
r = 10**9 +7
xav = ((m**3-m) *n**2)//6
yav = ((n**3-n)*m**2)//6
av = xav + yav
d = (m*n*(m*n-1))//2
print(int(((av*s)//d)%r))

Submission status: Time Limit Exceeded

Solution code:
from math import factorial
n,m,K=map(int,input().split())
ans=0
t=0
def comb(n,r):
    return factorial(n)//factorial(n-r)//factorial(r)
for i in range(3,n+m+1):
    for j in range(1,i):
        if(j>m):
            break
        k=i-j
        if(k<=n):
            if(j==1 or k==1):
                ans+=(i-2)*(m-j+1)*(n-k+1)
            else:
                ans+=(i-2)*(m-j+1)*(n-k+1)*2
print((ans*comb(n*m-2,K-2))%(10**9+7))

Submission status: Time Limit Exceeded

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

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

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

# 0~N*M-1までの1次元上と考える
ans = 0

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

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

for i in range(N*M):
    tate, yoko = i//M, i%M
    migi = f(M-1-yoko)
    hidari = f(yoko)
    sita = (hidari+migi)*(N-1-tate) + M*f(N-1-tate)
    coef = migi + sita
    ans += coef*c
    ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

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

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

def C(n, r):
    return P(n, r)//math.factorial(r)
dis = M * M * N * N * (N+1) // 2 % sosu
dis = dis - M * M * N * (N+1) * ( 2* N + 1) // 6 % sosu
dis = dis + N * N * M * M * (M+1) //2 % sosu
dis = dis - N * N * M * (M+1) * (2*M + 1) // 6 % sosu


if K >= 3:
    dis = dis * C(N*M-2, K-2) % sosu
if dis >= 0:
    print(dis)
else:
    print(dis + sosu)

Submission status: Time Limit Exceeded

Solution code:
import math
n,m,k = map(int,input().split())
ss = (math.factorial(m*n)//math.factorial(k))//math.factorial(m*n-k)
s = (ss*k*(k-1))//2
r = 10**9 +7
xav = 0
yav = 0
for i in range(1,m):
  xav += (i*(m-i)*n**2)%r
for j in range(1,n):
  yav += (j*(n-j)*m**2)%r
av = xav + yav
d = (m*n*(m*n-1))//2
print(int(((av*s)//d)%r))

Submission status: Time Limit Exceeded

Solution code:
import math
n,m,k = map(int,input().split())
ss = (math.factorial(m*n)//math.factorial(k))//math.factorial(m*n-k)
s = (ss*k*(k-1))//2
r = 10**9 +7
xav = 0
yav = 0
for i in range(1,m):
  xav += (i*(m-i)*n**2)%r
for j in range(1,n):
  yav += (j*(n-j)*m**2)%r
av = xav + yav
d = (m*n*(m*n-1))//2
print(int(((av*s)//d)%r))

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/abc127/tasks/abc127_e

import itertools
from collections import Counter
from collections import defaultdict
import bisect
import math

# Calculate count of combination
def combination(n, r):
    if r == 0:
        return 1
    a = 1
    b = 1
    for i in range(r):
        a *= (n - i)
        if a % (i + 1):
            a //= (i + 1)
        else:
            b *= (i + 1)
    return a // b


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

    com = combination(N * M - 2, K - 2)
    # print(com)
    com = com % MOD
    # print(com)

    ans = 0
    for i in range(N*M-1):
        for j in range(i + 1, N*M):
            # print('{} {}'.format(i, j))
            iy = i // M
            ix = i % M

            jy = j // M
            jx = j % M
            ans += (abs(iy - jy) + abs(ix - jx)) * com
            ans = ans % MOD

    print(ans)



if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import collections as c
ip = lambda : map(int, input().split())

def cmb(n,r):
    if n==0:return 0
    else:
        r=min(r,n-r)
        result=1
        for i in range(n-r+1,n+1):
            result*=i
        for i in range(1,r+1):
            result//=i
        return result

# ##############
N,M,K = ip()
ans = 0
mod = int(1e9+7)
pattern = cmb(N*M-2,K-2)
for i in range(N*M):
    s,t = i//M,i%M
    '''for j in range(i,N*M):
        jpair = (j//N,j%N)
        cost = abs(ipair[0] - jpair[0]) + abs(ipair[1] - jpair[1])'''
    tmpS = s*(s+1)//2 + (N-s-1)*(N-s)//2
    cost = tmpS*M + N*(t*(t+1) + (M-1-t)*(M-t))//2
    #print(s,t,cost)
    ans += ((cost*pattern)//2)%mod
    ans %= mod
        
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math

def nCr(n,r):
    f = math.factorial
    return f(n) // f(r) // f(n-r)

def distancesum(arr, n): 
      
    # sorting the array. 
    arr.sort() 
      
    # for each point, finding  
    # the distance. 
    res = 0
    sum = 0
    for i in range(n): 
        res += (arr[i] * i - sum) 
        sum += arr[i] 
      
    return res 

flatten = lambda x: [z for y in x for z in (flatten(y) if hasattr(y, '__iter__') and not isinstance(y, str) else (y,))]

div = 10**9 + 7

N, M, K = map(int, input().split())
repeat = nCr(N*M-2, K-2)
f_row = flatten([[i for _ in range(M)] for i in range(N)])
f_col = flatten([[i for i in range(M)] for _ in range(N)])

manhsum = distancesum(f_row, len(f_row)) + distancesum(f_col, len(f_col))
print(((repeat % div) * (manhsum % div))%div)

Submission status: Time Limit Exceeded

Solution code:
n, m, k = map(int, input().split())
t = n * m - 2
memo = 1
answer = 0

for i in range(k - 2):
    memo *= t
    memo = memo // (i + 1)
    t -= 1

for i in range(1, n):
    answer = (answer+((1+i)*(i)//2)*m*m*memo % (10**9+7)) % (10**9+7)
for i in range(1, m):
    answer = (answer + ((i+1) * (i) // 2) * n * n*memo %
              (10 ** 9 + 7)) % (10 ** 9 + 7)

print(answer)

Submission status: Time Limit Exceeded

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

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

def C(n, r):
    return P(n, r)//math.factorial(r)
dis = 0
for i in range(1,N):
    dis += i * (N-i) * M * M
    dis = dis % sosu
for j in range(1,M):
    dis += j * (M-j) * N * N
    dis = dis % sosu
#print(dis)

if K >= 3:
    dis = dis * C(N*M-2, K-2) % sosu
print(dis)

Submission status: Time Limit Exceeded

Solution code:
N, M, K = (int(x) for x in input().split())

def nCm(n,m):
    if m < 0 or m > n:
        return 0
    nf = factorial(n)
    nm = factorial(m)
    nm2 = factorial(n-m)
    return (nf//nm//nm2) % 1000000007

def factorial(n):
    ans = 1
    for i in range(n):
        ans *= (i+1)
    return ans

c_sum = (M*(N-1)*N*(N+1)*M+N*(M-1)*M*(M+1)*N)//3
c_sum = c_sum//2
c_sum *= nCm(N*M-2, K-2)
c_sum = c_sum % 1000000007

print(c_sum)

Submission status: Time Limit Exceeded

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

mod = 10**9 + 7


def choose(n,k):
  return (math.factorial(n) // (math.factorial(n - k) * math.factorial(k))) % mod

sum = 0
for i in range(1, n+1):
  for j in range(1, m+1):
    score = i-1 + j-1
    cnt = (n-i+1) * (m-j+1)
    sum += (score * cnt) % mod
    #print((i,j), score, cnt)

for i in range(2, n+1):
  for j in range(1, m):
    score = i-1 + m-j
    cnt = (n-i+1) * j
    sum += (score * cnt) % mod
    #print((i,j), score, cnt)

sum = sum * choose(m*n-2,k-2)
sum = sum % mod
print(sum)

Submission status: Time Limit Exceeded

Solution code:
import math
N,M,K=map(int,input().split())
xs=0
ys=0
inf=10**9+7
xs=(M*(M+1)*(2*M+1) - 3*M*(M+1))//12
ys=(N*(N+1)*(2*N+1) - 3*N*(N+1))//12
#for i in range(1,M):
	#xs+=i*(M-i)
	#xs = xs % inf
#for i in range(1,N):
	#ys+=i*(N-i)
	#ys = ys % inf
xs*=(N**2)
xs = xs % inf
ys*=(M**2)
ys = ys % inf

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

def comb_new(n,r):
	y = 1
	for i in range(r):
		y *= (n-i)
	return y//math.factorial(r)

#c = comb(N*M-2,K-2) % inf
c = comb_new(N*M-2,K-2) % inf
print(((xs+ys)*c)%inf)

Submission status: Time Limit Exceeded

Solution code:
N, M, K = (int(x) for x in input().split())

def cell_dist_sum(i,j):
    x = (i*(i+1)//2+(N-i-1)*(N-i)//2)*M
    y = (j*(j+1)//2+(M-j-1)*(M-j)//2)*N
    return x+y

def nCm(n,m):
    if m < 0 or m > n:
        return 0
    nf = factorial(n)
    nm = factorial(m)
    nm2 = factorial(n-m)
    return (nf//nm//nm2) % 1000000007

def factorial(n):
    ans = 1
    for i in range(n):
        ans *= (i+1)
    return ans

c_sum = 0
for i in range(N):
    for j in range(M):
        c_sum += cell_dist_sum(i,j)
c_sum = c_sum//2
c_sum *= nCm(N*M-2, K-2)
c_sum = c_sum % 1000000007

print(c_sum)

Submission status: Time Limit Exceeded

Solution code:
p = 10**9 + 7

from math import factorial as f

def choose(a,b):

        return (f(a))//(f(a-b)*f(b))

while True:
    inp=input().split()

    n=int(inp[0])
    m=int(inp[1])
    k=int(inp[2])

    col1 = (n*n*m*m*(n-1))//2 - (n*m*m*(n-1)*(2*n-1))//6
    n, m = m, n
    col2 = (n*n*m*m*(n-1))//2 - (n*m*m*(n-1)*(2*n-1))//6

    ans=((col1+col2)*choose(k,2)*choose(n*m,k))//choose(n*m,2)

    print(ans%p)

    break

Submission status: Time Limit Exceeded

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) // (i + 1)

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: Time Limit Exceeded

Solution code:
import math
N,M,K=map(int,input().split())
xs=0
ys=0
inf=10**9+7
xs=(M*(M+1)*(2*M+1) - 3*M*(M+1))//12
ys=(N*(N+1)*(2*N+1) - 3*N*(N+1))//12
#for i in range(1,M):
	#xs+=i*(M-i)
	#xs = xs % inf
#for i in range(1,N):
	#ys+=i*(M-i)
	#ys = ys % inf
xs*=(N**2)
xs = xs % inf
ys*=(M**2)
ys = ys % inf

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

c = comb(N*M-2,K-2) % inf
print(((xs+ys)*c)%inf)

Submission status: Time Limit Exceeded

Solution code:
import math
N,M,K=map(int,input().split())
xs=0
ys=0
inf=10**9+7
for i in range(1,M):
	xs+=i*(M-i)
	xs = xs % inf
for i in range(1,N):
	ys+=i*(N-i)
	ys = ys % inf
xs*=(N**2)
xs = xs % inf
ys*=(M**2)
ys = ys % inf

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

c = comb(N*M-2,K-2) % inf
print(((xs+ys)*c)%inf)

Submission status: Time Limit Exceeded

Solution code:
N, M, K = map(int, input().split())
P = 10**9+7
fact = [1]
for i in range(N*M):
    fact.append(fact[-1]*(i+1))
def inv(n):
    return pow(n, P-2, P)
def C(a, b):
    return fact[a]*inv(fact[a-b]*fact[b])%P
print((M**2*(N**3-N)+N**2*(M**3-M))//6*C(M*N-2, K-2)%P)

Submission status: Accepted

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

def nCk(n, k, mod):
    nu = 1
    de = 1 
    for i in range(1, k+1):
        nu *= (n-i+1)
        de *= i
        nu = nu % mod
        de = de % mod
    ans = nu * pow(de, mod-2, mod) % mod
    return ans

ans = nCk(N*M-2, K-2, mod)*N*M*(M+N)*(M*N-1)//6
ans = ans % mod
print(ans)

Submission status: Accepted

Solution code:
N, M, K = map(int, input().split())
P = int(1e9+7)
N -= 1
M -= 1

def comb(n, r):
    if n < r or r < 0:
        return 0
    nume = 1
    deno = 1
    for i in range(1, r + 1):
        nume = (nume * (n - i + 1)) % P
        deno = (deno * i) % P
    deno_inv = pow(deno, P-2, P)
    return (nume*deno_inv)%P

ans = 0

def sum_man_dist_ur(u, r):
    ret = 0
    u, r = min(u, r), max(u, r)
    if u == 0:
        ret =  r * (r + 1) // 2
    else:
        ret += (u * (u + 1) * (u - 1)) // 3
        ret += (u+1)*(r-u+1)*(r+u)//2
        ret += u * (u + 1) * (u + 3 * r + 2) // 6
    return ret%P

def sum_man_dist(x, y):
    ret = 0
    ret += sum_man_dist_ur(N - x, M - y)
    ret = (ret + sum_man_dist_ur(N - x, y)) % P
    ret = (ret + sum_man_dist_ur(x, M - y)) % P
    ret = (ret + sum_man_dist_ur(x, y)) % P
    ret -= (N-x)*(N-x+1)//2
    ret -= (x)*(x+1)//2
    ret -= (M-y)*(M-y+1)//2
    ret -= (y) * (y + 1) // 2
    return ret%P

ans = 0
c = comb((N+1)*(M+1)-2, K-2)
for x in range(N + 1):
    for y in range(M + 1):
        ans = (ans + c * sum_man_dist(x, y)) % P
print(ans*pow(2, P-2, P)%P)

Submission status: Accepted

Solution code:
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
import collections
import math
import itertools
import heapq as hq
import sys
import numpy as np
mod=10**9+7
def ncr_1(n,r,p):##　n>>r の場合のncr　O(r)
    x = 1
    y = 1
    for i in range(r):
        x*=(n-i)
        y*=(i+1)
        x%=p
        y%=p
    return x*modinv(y,p) %p
def modinv(a,p):
    b,u,v = p,1,0
    while b:
        t = a//b
        a -= t*b
        a,b = b,a
        u -=t*v
        u,v = v,u
    u %=p
    return u
n,m,k = ma()
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
print((ans*ncr_1(n*m-2,k-2,mod))%mod)

Submission status: Accepted

Solution code:
N=10**6
p=10**9+7
f,finv,inv=[0]*(N*5),[0]*(N*5),[0]*(N*5)

def nCr_init(L,p):
    for i in range(L+1):
        if i<=1:
            f[i],finv[i],inv[i]=1,1,1
        else:
            f[i]=(f[i-1]*i)%p
            inv[i]=(p-inv[p%i]*(p//i))%p
            finv[i]=(finv[i-1]*inv[i])%p

def nPr(n,r,p):
    if 0<=r<=n and 0<=n:
        return (f[n]*finv[n-r])%p
    else:
        return 0
    
nCr_init(N,p)

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

print((nPr(N*M,K,p)*((M+N)*inv[6]*finv[K-2])%p)%p)

Submission status: Accepted

Solution code:
"""
基本の方針は「各マンハッタン距離が何回足されるか」という考え方で距離の値を積み上げて行けばよい

まず、XとYは独立に考えることにする。
X軸の距離の方から積み上げる。
X1とX2の距離が足される回数は、
A.X1の列とX2の列の座標の組み合わせの数　×　B.その組み合わせが含まれるような座標の組み合わせの数
である。
A　＝　行数**２
B　＝　CMB(N*M-2 , K-2)である

同様の計算をY軸に関しても行えばよい。
"""
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
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())

ans = 0

#X軸の距離を考える
A = M*M
B = cmb(N*M-2,K-2,p)
for i in range(1,N):
    ans += ((i*i)-(i-1+0)*i//2)*A*B%p
    ans %= p

#Y軸の距離を考える
A = N*N
B = cmb(N*M-2,K-2,p)
for i in range(1,M):
    ans += ((i*i)-(i-1+0)*i//2)*A*B%p
    ans %= p

print(ans)

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7
class nCr():
    def __init__(self, n):
        self.n = n
        self.fa = [1] * (self.n + 1)
        self.fi = [1] * (self.n + 1)
        for i in range(1, self.n + 1):
            self.fa[i] = self.fa[i - 1] * i % mod
            self.fi[i] = pow(self.fa[i], mod - 2, mod)
    def comb(self, n, r):
        if n < r:return 0
        if n < 0 or r < 0:return 0
        return self.fa[n] * self.fi[r] % mod * self.fi[n - r] % mod
n, m, k = map(int, input().split())
ans = 0
c = nCr(n * m)
for i in range(n):
    ans += i * (n - i) * m * m
    ans %= mod
for i in range(m):
    ans += i * (m - i) * n * n
    ans %= mod
print(ans * c.comb(n * m - 2, k - 2) % mod)

Submission status: Accepted

Solution code:
# N, M から相異なる二点を取った時のマンハッタン距離の、二点の取り方についての総和を、
# _{N + M - 2} C _{K - 2} 倍したものが答え。


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

# コンビネーション前計算。
MOD = 10 ** 9 + 7
table_len = 2 * 10 ** 5 + 10

fac = [1, 1]
for i in range(2, table_len):
    fac.append(fac[-1] * i % MOD)

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

# マンハッタン距離の総和は、各距離の部分がカウントされるかを考えればよいので、
# (ex. 左半分と右半分にひとつずつなら、必ず二等分する線を横断する部分がある、みたいな)
# l + r = N に対し lM * rM = M^2 * lr の総和と、
# l + r = M に対し lN * rN = N^2 * lr の総和の和でよい。
# シグマ公式をつかえばO(1)にも出来そうだが、面倒なので省略。

# M^2は最後にまとめる
distsum1 = 0
for l in range(1, N):
    distsum1 += l * (N - l)
    distsum1 %= MOD
distsum1 *= pow(M, 2, MOD)
distsum1 %= MOD

# N^2は最後にまとめる
distsum2 = 0
for l in range(1, M):
    distsum2 += l * (M - l)
    distsum2 %= MOD
distsum2 *= pow(N, 2, MOD)
distsum2 %= MOD

print((distsum1 + distsum2) % MOD * fac[N * M - 2] % MOD * finv[K - 2] % MOD * finv[N * M - K] % MOD)

Submission status: Accepted

Solution code:
from itertools import combinations
import math
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
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())
ans = 0
mod = 10**9 +7
by = cmb(N*M-2,K-2,mod)

#まずは、X軸の総和を求める。
for i in range(N):
    for j in range(M):
        cnt = M-j-1
        add = (((j+1)+(M-1))*cnt//2 - j*cnt)*N%mod
        ans += add*by%mod
        ans %= mod

for i in range(M):
    for j in range(N):
        cnt = N-j-1
        add = (((j+1)+(N-1))*cnt//2 - j*cnt)*M%mod
        ans += add*by%mod
        ans %= mod


print(ans)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
# 10 ** 7 might cause MLE
fac = [-1] * (10**6+1)
inv = [-1] * (10**6+1)
finv = [-1] * (10**6+1)

fac[0] = fac[1] = 1
inv[1] = 1
finv[0] = finv[1] = 1

def initNCMMod(limit):
    for i in range(2, limit):
        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 NCMMod(n, k):
    if n < k:
        return 0
    if (n < 0 or k < 0):
        return 0
    return fac[n] * (finv[k] * finv[n-k] % mod) % mod
initNCMMod(10**6)

def checkf(R, C):
    ans = 0
    for r1 in range(R):
        for c1 in range(C):
            for r2 in range(R):
                for c2 in range(C):
                    ans += abs(r1-r2) + abs(c1-c2)
    return ans


def main():
    R, C, K = LI()
    def f(i):
        return (i * (i+1) // 2) % mod

    ans = 0
    for i in range(C):
        ans += f(C-i-1) * R * R % mod
        ans += f(i) * R * R % mod

    for i in range(R):
        ans += f(R-i-1) * C * C % mod
        ans += f(i) * C * C % mod
    ans *= inv[2]
    ans %= mod
    ans *= NCMMod(R*C-2, K-2)
    ans %= mod

    print(ans)

main()

Submission status: Accepted

Solution code:
class ModCalc:
    mod = 10**9 + 7

    def __init__(self, n):
        self.n = n
        self.inv = [1] * (self.n + 1)
        self.fac = [1] * (self.n + 1)
        self.finv = [1] * (self.n + 1)
        self.inv[0] = 0
        self.inv_table()

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

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

        return self.fac[n] * self.finv[r] % self.mod * self.finv[n-r] % self.mod

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

        return self.fac[n] * self.finv[n-r] % self.mod

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


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

mc = ModCalc(n*m)
mod = 10**9 + 7

ret = 0
for d in range(1, n):
    ret += d * (n - d) % mod * m % mod * m % mod * mc.comb(n * m - 2, k-2) % mod
    ret %= mod

for d in range(1, m):
    ret += d * (m - d) % mod * n % mod * n % mod * mc.comb(n * m - 2, k - 2) % mod
    ret %= mod
print(ret)

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


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

    COM_MAX = N * M

    fac, finv, inv = [0] * (COM_MAX + 1), [0] * (COM_MAX + 1), [0] * (COM_MAX + 1)
    fac[0] = fac[1] = finv[0] = finv[1] = inv[1] = 1

    for i in range(2, COM_MAX + 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

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

    def solve(n, m, k):
        ans = 0
        for d in range(1, n):
            ans = (ans + com(n * m - 2, k - 2) * (m ** 2) * (n - d) * d) % MOD

        return ans

    ans = (solve(N, M, K) + solve(M, N, K)) % MOD
    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

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

# N行, M列 i-j
# 1-1, 1-2, 1-3, 1-4, ... , 1-M
# 2-1, 2-2, 2-3, 2-4, ... , 2-M
# 3-1. 3-2. 3-3, 3-4, ... , 3-M
# ...
# N-1, N-2, N-3, N-4, ... , N-M

# K個の駒が上記の座表上に置かれた時の配置全種類のコストの総和を調べたい

factorial = [1 for i in range(N*M + 1)]
for i in range(1, N * M + 1):
	if i==1:
		factorial[i] = 1
	else:
		factorial[i] = factorial[i-1]*i % mod

def comb(n, k):
	return (factorial[n]*pow(factorial[n-k]*factorial[k], -1, mod)) % mod

xscore = 0
for i in range(1, N):
	xscore += i * (N-i)
xscore %= mod
xscore *= M**2 * comb(N*M-2, K-2)
xscore %= mod

yscore = 0
for i in range(1, M):
	yscore += i * (M-i)
yscore %= mod
yscore *= N**2 * comb(N*M-2, K-2)
yscore %= mod

print((xscore + yscore) % mod)

Submission status: Accepted

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

factorial=[1 for i in range(N*M+1)]
for i in range(1,N*M+1):
    if i==1:factorial[i]=1
    else:factorial[i] = factorial[i-1]*i % mod

def comb(n,k):
    return (factorial[n]*pow(factorial[n-k]*factorial[k], -1, mod))%mod
  
xscore = 0
for i in range(1,N):
  xscore += i * (N-i)
xscore %= mod
xscore *= M**2 * comb(N*M-2,K-2)
xscore %= mod

yscore = 0
for i in range(1,M):
  yscore += i * (M-i)
yscore %= mod
yscore *= N**2 * comb(N*M-2,K-2)
yscore %= mod

print((xscore + yscore) %mod)

Submission status: Accepted

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

M = [1]  # i!のmod
mul = 1
for i in range(1, l):
    mul = (mul * i) % mod
    M.append(mul)

def pow(x, y, mod):  # x**y の mod を返す関数
    ans = 1
    while y > 0:
        if y % 2 == 1:
            ans = (ans * x) % mod
        x = (x**2) % mod
        y //= 2
    return ans

def inv(x, mod):  # x の mod での逆元を返す関数
    return pow(x, mod-2, mod)

# print(inv(8,13))

MI = [0] * (l-1) +[inv(M[l-1], mod)]  # i!の逆元
for i in range(l-2, -1, -1):
    MI[i] = MI[i+1] * (i+1) % mod

def C(x, y):  # コンビネーション（組合せ）
    if y < 0 or y > x:
        return 0
    elif x > l:  # O(min(y, x-y))
        y = min(y, x-y)
        ans = 1
        for i in range(x, x-y, -1):
            ans = (ans * i) % mod
        return (ans * MI[y]) % mod
    else:  # O(1)
        ans = M[x]
        ans = (ans * MI[y]) % mod
        return (ans * MI[x-y]) % mod

def P(x, y):  # パーミュテーション（順列）
    if y < 0 or y > x:
        return 0
    elif x > l:  # O(min(y, x-y))
        y = min(y, x-y)
        ans = 1
        for i in range(x, x-y, -1):
            ans = (ans * i) % mod
        return ans % mod
    else:  # O(1)
        ans = M[x]
        return (ans * MI[x-y]) % mod

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

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