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:
import sys
input = sys.stdin.readline
N, M, K = map(int, input().split())
mod = 10 ** 9 + 7
class Factorial:
  def __init__(self, n, mod):
    self.f = [1]
    for i in range(1, n + 1):
      self.f.append(self.f[-1] * i % mod)
    self.i = [pow(self.f[-1], mod - 2, mod)]
    for i in range(1, n + 1)[: : -1]:
      self.i.append(self.i[-1] * i % mod)
    self.i.reverse()
  def factorial(self, i):
    return self.f[i]
  def ifactorial(self, i):
    return self.i[i]
  def combi(self, n, k):
    return self.f[n] * self.i[n - k] % mod * self.i[k] % mod

f = Factorial(N * M, mod)
t = f.combi(N * M - 2, K - 2)

res = 0
for d in range(1, M):
  x = N ** 2 % mod * (M - d) % mod
  res += x * d % mod
  res %= mod
  #print(x)
for d in range(1, N):
  y = M ** 2 % mod * (N - d) % mod
  res += y * d % mod
  res %= mod
#print(res, t)
print(res * t % mod)

Submission status: Accepted

Solution code:


class Cmber:
    def __init__(self,gensize,mod=10**9+7):
        self.mod = mod
        self.g1=[1,1]
        self.g2 = [1, 1] #逆元テーブル
        self.inverse = [0, 1] #逆元テーブル計算用テーブル
        self.getgen(gensize)
    def getgen(self,N):
        for i in range( 2, N + 1 ):
            self.g1.append( ( self.g1[-1] * i ) % self.mod )
            self.inverse.append( ( -self.inverse[self.mod % i] * (self.mod//i) ) % self.mod )
            self.g2.append( (self.g2[-1] * self.inverse[-1]) % self.mod )
 
    def cmb(self,n, r):
        if ( r<0 or r>n ):
            return 0
        r = min(r, n-r)
        return self.g1[n] * self.g2[r] * self.g2[n-r] % self.mod
 
    def cmb_very_high_n(self,n, r):
        if ( r<0 or r>n ):
            return 0
        g1=1
        r = min(r, n-r)
        for i in range(n-r+1,n+1):
            g1*=i
            g1%=self.mod
        return g1 * self.g2[r] % self.mod

    def multiple_cmb(self,vals):
        ans = self.g1[sum(vals)] % self.mod
        for i in vals:
            ans = (ans*self.g2[i])%self.mod
        return ans










def resolve():
    N,M,K = map(int,input().split())
    cmber = Cmber(N*M)
    score = 0
    for dist in range(1,N):
        cmb_of_2 = dist*(((((N-dist)*M)%cmber.mod)*M)% cmber.mod) % cmber.mod

        score = (score+(cmb_of_2*cmber.cmb(N*M-2,K-2))%cmber.mod)%cmber.mod
        
    for dist in range(1,M):
        cmb_of_2 = dist*(((((M-dist)*N)%cmber.mod)*N)% cmber.mod) % cmber.mod

        score = (score+(cmb_of_2*cmber.cmb(N*M-2,K-2))%cmber.mod)%cmber.mod

    print(score)

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
n,m,k=map(int,input().split())
mod=10**9+7
x=1
y=1
for i in range(1,k-1):
    y*=i
    y%=mod
for i in range(k-2):
    x*=n*m-2-i
    x%=mod
x*=pow(y,mod-2,mod)
x%=mod
def f(n,m):
    s=0
    for i in range(1,n):
        s+=i*(n-i)
        s%=mod
    return s*m*m%mod
print((f(n,m)+f(m,n))*x%mod)

Submission status: Accepted

Solution code:
n,m,k = map(int,input().split())
mod = 10**9+7
def combination(n,r,p):
    if n < r or r < 0:
        return 0
    r = min(n-r,r)
    
    fact = [1,1]
    factinv = [1,1]
    inv = [0,1]
    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)
    return fact[n]*factinv[r]*factinv[n-r]%p
temp = combination(n*m-2,k-2,mod)
ans = 0
for d in range(1,n):
    ans += d*((n-d)*(m**2))*temp
for d in range(1,m):
    ans += d*((m-d)*(n**2))*temp
print(ans%mod)

Submission status: Accepted

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

mod = 10**9+7 
fact = [1,1]
finv = [1,1]
inv = [0,1]
 
for i in range(2,n*m+1):
    fact.append((fact[-1]*i)%mod)
    inv.append((inv[mod%i]*(mod-mod//i))%mod)
    finv.append((finv[-1]*inv[-1])%mod)
 
def nCr(n,r,mod):
    if r > n:
        return 0
    else: 
        return fact[n]*finv[r]*finv[n-r]%mod    


ans = 0

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

Submission status: Accepted

Solution code:
##mod,nについての制約は自分でいかに記入する
mod=10**9+7
def find_power(n,mod):
    # 0!からn!までのびっくりを出してくれる関数(ただし、modで割った値に対してである）
    powlist=[0]*(n+1)
    powlist[0]=1
    powlist[1]=1
    for i in range(2,n+1):
        powlist[i]=powlist[i-1]*i%(mod)
    return powlist
 #あるかずxのn乗をmodで割ったあまりを返す関数pow_cal(x,n,mod)
def pow_cal(x,n,mod):
    if n==0:
         return 1
    elif n==1:
         return x%mod
    elif n>=2:
        if n%2==0:
             return (pow_cal(x,n//2,mod)**2)%mod
        else:
             return (x*pow_cal(x,n//2,mod)**2)%mod

def find_inv_power(n,mod):
    #0!からn!までの逆元を素数modで割ったあまりリストを作る関数
    c=1
    uselist=[0 for i in range(n+1)]
    for i in range(1,n+1):
        c*=i
        c%=mod
    first=pow_cal(c,mod-2,mod)
    uselist[n]=first
    for i in range(n,0,-1):
        uselist[i-1]=(uselist[i]*i)%(mod)
    return uselist
    
A=find_power(4*10**5,mod)
B=find_inv_power(4*10**5,mod)

def combi(n,r,mod):
    if n<r:
        return 0
    elif n>=r:
        return (A[n]*B[r]*B[n-r])%(mod)

    
M,N,K=map(int,input().split())
ans=M*N*(M+N)*(M*N-1)//6

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

Submission status: Accepted

Solution code:
# python 3.4.3
import sys
input = sys.stdin.readline

# -------------------------------------------------------------
# library
# -------------------------------------------------------------
class Combination:
    def __init__(self, n, mod):
        self.mod = mod
        self.fact = [1]*n
        self.finv = [1]*n
        self.inv  = [1]*n
        for i in range(2,n):
            self.fact[i] = (self.fact[i-1]*i) % self.mod
            self.inv[i]  = self.mod - self.inv[self.mod%i] * (self.mod//i)%self.mod
            self.finv[i] = self.finv[i-1] * self.inv[i] % self.mod
 
    def nCr(self, n, r):
        if n<r:
            return 0
        else:
            return self.fact[n] * (self.finv[r] * self.finv[n-r] % self.mod) % self.mod

mod = 10**9+7
Combination = Combination(200010, mod)

# -------------------------------------------------------------
# main
# -------------------------------------------------------------

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

ans = 0
for d in range(1,N):
    t = d * Combination.nCr(N*M-2, K-2)
    t %= mod
    t *= (N-d)*M*M
    t %= mod
    ans += t
    ans %= mod
for d in range(1,M):
    t = d * Combination.nCr(N*M-2, K-2)
    t %= mod
    t *= (M-d)*N*N
    t %= mod
    ans += t
    ans %= mod

print(ans)

Submission status: Accepted

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

def power(n, r, mod):
    if r == 0: return 1
    if r%2 == 0:
        return power(n*n % mod, r//2, mod) % mod
    if r%2 == 1:
        return n * power(n, r-1, mod) % mod

def comb(n, k, mod):
    a=framod(n, mod)
    b=framod(k, mod)
    c=framod(n-k, mod)
    return (a * power(b, mod-2, mod) * power(c, mod-2, mod)) % mod

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

ans = 0

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

ans *= comb(N*M-2 , K-2, 10**9+7)

print(int(ans % (10**9+7)))

Submission status: Accepted

Solution code:
# python 3.4.3
import sys
input = sys.stdin.readline

# -------------------------------------------------------------
# library
# -------------------------------------------------------------
class Combination:
    def __init__(self, n, mod):
        self.mod = mod
        self.fact = [1]*n
        self.finv = [1]*n
        self.inv  = [1]*n
        for i in range(2,n):
            self.fact[i] = (self.fact[i-1]*i) % self.mod
            self.inv[i]  = self.mod - self.inv[self.mod%i] * (self.mod//i)%self.mod
            self.finv[i] = self.finv[i-1] * self.inv[i] % self.mod
 
    def nCr(self, n, r):
        if n<r:
            return 0
        else:
            return self.fact[n] * (self.finv[r] * self.finv[n-r] % self.mod) % self.mod

mod = 10**9+7
Combination = Combination(200010, mod)

# -------------------------------------------------------------
# main
# -------------------------------------------------------------

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

ans = 0
for d in range(1,N):
    t = d * Combination.nCr(N*M-2, K-2)
    t %= mod
    t *= (N-d)*M*M
    t %= mod
    ans += t
    ans %= mod
for d in range(1,M):
    t = d * Combination.nCr(N*M-2, K-2)
    t %= mod
    t *= (M-d)*N*N
    t %= mod
    ans += t
    ans %= mod

print(ans)

Submission status: Accepted

Solution code:
# python 3.4.3
import sys
input = sys.stdin.readline

# -------------------------------------------------------------
# library
# -------------------------------------------------------------
def init_fact(n,mod):
    fact,finv,inv = [1]*n,[1]*n,[1]*n
    for i in range(2,n):
        fact[i] = (fact[i-1]*i) % mod
        inv[i]  = mod - inv[mod%i] * (mod//i)%mod
        finv[i] = finv[i-1] * inv[i] % mod
    return (fact,finv,inv)
 
def nCr(n,r,mod,fact,finv):
    if n<r:
        return 0
    else:
        return fact[n] * (finv[r] * finv[n-r] % mod) % mod

mod = 10**9+7
fact,finv,inv = init_fact(200010,mod)


# -------------------------------------------------------------
# main
# -------------------------------------------------------------

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

ans = 0
for d in range(1,N):
    t = d * nCr(N*M-2, K-2, mod, fact, finv)
    t %= mod
    t *= (N-d)*M*M
    t %= mod
    ans += t
    ans %= mod
for d in range(1,M):
    t = d * nCr(N*M-2, K-2, mod, fact, finv)
    t %= mod
    t *= (M-d)*N*N
    t %= mod
    ans += t
    ans %= mod

print(ans)

Submission status: Accepted

Solution code:
import math

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

facts = [1 for i in range(MAX)]
invs = [1 for i in range(MAX)]

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

for i in range(1,MAX):
    facts[i] = (facts[i-1] * i)% mod
    invs[i] = inv(facts[i])

def nCr(n,r):
	return facts[n] * invs[r] * invs[n-r] % mod

def main():
    ans = 0
    complement = nCr((N*M-2)%mod,(K-2)%mod)
    for i in range(1,N):
        ans += i * (N-i) * M**2
    for i in range(1,M):
        ans += i * (M-i) * N**2
    print((ans*complement) % mod)

main()

Submission status: Accepted

Solution code:
N, M, K = map(int, input().split())
import sys
mod = pow(10, 9) + 7
sys.setrecursionlimit(pow(10, 8))

def power(x, y):
    if   y == 0: return 1
    elif y == 1	 : return x % mod
    elif y % 2 == 0 : return power(x, y//2)**2 % mod
    else: return power(x, (y-1)//2)**2 * x % mod
    
def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

def div(a, b):
    return mul(a, power(b, mod-2))
def div2(a, b):
    return mul(a, modinv(b))

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

def cmb(n, r):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

NNN = (10**6)
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

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

def f(n, m):
    x = m*m%mod
    y = (n*n*(n-1)//2 - n*(n-1)*(2*n-1)//6) % mod
    return x*y%mod

print(mul(f(N, M) + f(M, N), cmb(N*M-2, K-2)))

Submission status: Accepted

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

mod = 10 ** 9 + 7
MAX = n * m

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

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


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


ans = 0
for i in range(n):
    for j in range(m):
        add = (n - i) * (m - j) * (i + j) % mod
        if i != 0 and j != 0:
            add *= 2
            add %= mod

        ans += add
        ans %= mod

ans *= comb(MAX - 2, k - 2)
ans %= mod
print(ans)

Submission status: Accepted

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


class ModInt:
    def __init__(self, num):
        self.num = num

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

    def __repr__(self):
        return "ModInt(num: {}, mod: {}".format(self.num, mod)

    def __add__(self, other):
        ret = self.num + other.num
        ret %= mod
        return ModInt(ret)

    def __sub__(self, other):
        ret = self.num - other.num
        ret %= mod
        return ModInt(ret)

    def __mul__(self, other):
        ret = self.num * other.num
        ret %= mod
        return ModInt(ret)

    def pow(self, times):
        pw = pow(self.num, times, mod)
        return ModInt(pw)

    def inverse(self):
        return ModInt(inv[self.num])

    def __truediv__(self, other):
        num = self * other.inverse()
        return ModInt(num)


def comb(n, k):
    return fact[n] * inv[n-k] * inv[k]


fact = [None] * (MAX + 1)
fact[0] = ModInt(1)
for i in range(1, MAX + 1):
    fact[i] = fact[i-1] * ModInt(i)

inv = [None] * (MAX + 1)
inv[MAX] = fact[MAX].pow(mod - 2)
for i in range(MAX, 0, -1):
    inv[i-1] = inv[i] * ModInt(i)

ans = ModInt(0)
for i in range(n):
    for j in range(m):
        add = ModInt(n - i) * ModInt(m - j) * ModInt(i + j)
        if i != 0 and j != 0:
            add *= ModInt(2)

        ans += add

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

Submission status: Accepted

Solution code:
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 #出力の制限
N = 2*10**5
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

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

def function(i,k):
    return -((k*(k+1)*(2*k+1))//3)+k*(k+1)*(N+i-M)+2*N*(k+1)*(M-i)

N,M,K=map(int,input().split())
if M>N:
    N,M=M,N
ans=0
for i in range(1,N+M-1):
    if M-1>=i:
        ans+=i*(function(i,i)-N*(M-i)-M*(N-i))
        ans=ans%mod
    if i>=M and N-1>=i:
        ans+=i*(function(i,i)-function(i,i-M)-M*(N-i))
        ans=ans%mod
    if i>=N:
        ans+=i*(function(i,N-1)-function(i,i-M))
        ans=ans%mod

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

Submission status: Accepted

Solution code:
# machigatta 
class cmbs(object):
    def __init__(self, mod):
        self.mod = mod
        self.g1 = [1, 1]
        self.g2 = [1, 1]
        self.inverse = [0, 1]
        for i in range(2, 10 ** 6 + 1):
            self.g1.append((self.g1[-1] * i) % mod)
            self.inverse.append((-self.inverse[mod % i] * (mod // i)) % mod)
            self.g2.append((self.g2[-1] * self.inverse[-1]) % mod)

    def cmb(self, n, r):
        if n > 10 ** 6:
            return self.cmbl(n, r)
        return self.cmbr(n, r)

    def cmbr(self, n, r):
        if r < 0 or r > n:
            return 0
        r = min(r, n - r)
        return self.g1[n] * self.g2[r] * self.g2[n-r] % self.mod

    def cmbl(self, n, r):
        t = 1
        r = min(r, n-r)
        for i in range(n - r + 1, n + 1):
            t = t * i % self.mod
        return t * self.g2[r] % self.mod

def main():
    N, M, K = map(int, input().split())
    mod = 10**9 + 7
    c = cmbs(mod)
    r = c.cmb((N*M)-2, K-2)
    r2 = 0
    for i in range(N):
        r2 += ((i + 1) * i + (N - i - 1) * (N-i))
    r2 *= pow(M, 2, mod)
    r2 %= mod
    r3 = 0
    for i in range(M):
        r3 += ((i + 1) * i + (M - i - 1) * (M-i))
    r3 *= pow(N, 2, mod)
    r3 %= mod
    r = r * (r2 + r3) * c.inverse[4]#// 2
    return r % mod
print(main())

Submission status: Accepted

Solution code:
class cmbs(object):
    def __init__(self, mod):
        self.mod = mod
        self.g1 = [1, 1]
        self.g2 = [1, 1]
        inverse = [0, 1]
        for i in range(2, 10 ** 6 + 1):
            self.g1.append((self.g1[-1] * i) % mod)
            inverse.append((-inverse[mod % i] * (mod // i)) % mod)
            self.g2.append((self.g2[-1] * inverse[-1]) % mod)

    def cmb(self, n, r):
        if n > 10 ** 6:
            return self.cmbl(n, r)
        return self.cmbr(n, r)

    def cmbr(self, n, r):
        if r < 0 or r > n:
            return 0
        r = min(r, n - r)
        return self.g1[n] * self.g2[r] * self.g2[n-r] % self.mod

    def cmbl(self, n, r):
        t = 1
        r = min(r, n-r)
        for i in range(n - r + 1, n + 1):
            t = t * i % self.mod
        return t * self.g2[r] % self.mod

def main():
    N, M, K = map(int, input().split())
    mod = 10**9 + 7
    c = cmbs(mod)
    r = c.cmb((N*M)-2, K-2)
    r2 = 0
    for i in range(N):
        r2 += i * (N - i)
        #r2 += ((i + 1) * i + (N - i - 1) * (N-i))//2
    r2 *= pow(M, 2, mod)
    r2 %= mod
    r3 = 0
    for i in range(M):
        r3 += i * (M-i)
        #r3 += ((i + 1) * i + (M - i - 1) * (M-i))//2
    r3 *= pow(N, 2, mod)
    r3 %= mod
    r = r * (r2 + r3) #// 2
    return r % mod
print(main())

Submission status: Accepted

Solution code:
from itertools import combinations

def solve(N, M, K):
    #A = [(n, m) for n in range(N) for m in range(M)]
    r = 0
    for x in range(N):
        r += x * (N - x) * M * M
    for y in range(M):
        r += y * (M - y) * N * N
    return r

def main():
    N, M, K = map(int, input().split())
    g1 = [1, 1]
    g2 = [1, 1]
    inverse = [0, 1]
    mod = 10 ** 9 + 7
    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)
    t = solve(N, M, 2)
    for k in range(2, K):
        t = t * (N * M - k) * inverse[k - 1] % mod
    print(t)

main()

Submission status: Accepted

Solution code:
"""

AtCoder Beginner Contest 127  E - Cell Distance


x,yは独立して考えられるので分ける。
差分の絶対値の和の問題は
ある項について、＋として働くのが何回か、－として働くのが何回か
を考えてその分を足してあげればいい

例1の 2 x 2で考えると、x=2,y=1のについて、
xが＋に働くのは、x=2より小さい、(x,y)=(1,1),(1,2)
xが±0なのは、xが同じ、(x,y)=(2,2)
xが－に働くのはなし（x=2までなので）
的な。



Kについて考えると、ある駒a,b間のコストが求められる回数は、nCr(N*M-2, K-2)
（全部でK個選ぶときにa,bを先に選んで、残りのN-2からK-2個選ぶから。）

N x Mのマスで、(ax,ay)の物のコストについて、
X：+ax*(ax - 1) * N - ax * (M - ax) * N = ax*N*(ax-1-M+ax) = ax*N*(2ax-1-M)
これがマスの高さの分だけある(ayが1~Nまで)&これがnCr(N*M-2, K-2)回
Yも同様
"""


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

MOD = 10**9+7
 
MAXN = N*M + 10
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 nCr(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


#X：+ax*(ax - 1) * N - ax * (M - ax) * N = ax*N*(ax-1-M+ax) = ax*N*(2ax-1-M)がN個＆nCr(N*M-2, K-2))回
ans = 0

for i in range(1,M+1):
    tmp = (((((i * N) % MOD) * (2*i - 1 - M)) % MOD) * N) % MOD
    
    #print("~~~", i*N, 2*i - 1 - M,tmp, nCr(N*M-2, K-2))

    tmp *= nCr(N*M-2, K-2)

    tmp %= MOD
    #print("pppp", tmp)
    ans += tmp

    ans %= MOD


for i in range(1,N+1):
    tmp = (((((i * M) % MOD) * (2*i - 1 - N)) % MOD) * M) % MOD

    tmp *= nCr(N*M-2, K-2)

    tmp %= MOD
    ans += tmp
    ans %= MOD


print(ans)

Submission status: Accepted

Solution code:

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

MOD = 10**9+7
 
MAXN = N*M + 10
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 nCr(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


#X：+ax*(ax - 1) * N - ax * (M - ax) * N = ax*N*(ax-1-M+ax) = ax*N*(2ax-1-M)
ans = 0

for i in range(1,M+1):
    tmp = (((((i * N) % MOD) * (2*i - 1 - M)) % MOD) * N) % MOD
    
    #print("~~~", i*N, 2*i - 1 - M,tmp, nCr(N*M-2, K-2))

    tmp *= nCr(N*M-2, K-2)

    tmp %= MOD
    #print("pppp", tmp)
    ans += tmp

    ans %= MOD


for i in range(1,N+1):
    tmp = (((((i * M) % MOD) * (2*i - 1 - N)) % MOD) * M) % MOD

    tmp *= nCr(N*M-2, K-2)

    tmp %= MOD
    ans += tmp
    ans %= MOD


print(ans)

Submission status: Accepted

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

MOD = 10**9+7
n = N*M-2
fac = [1]*(n+1)
rev = [1]*(n+1)
 
for i in range(1,n+1):
  fac[i] = i*fac[i-1]%MOD
  rev[i] = pow(fac[i], MOD-2, MOD)
 
comb = lambda a,b:(fac[a]*rev[a-b]*rev[b])%MOD

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

for d in range(M):
    ans += d*(M-d)*(N**2)*C
    ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
n,m,k=map(int,input().split())
M=10**9+7
c=1
a=0
for i in range(1,k-1):c=(c*(n*m-1-i)*pow(i,M-2,M))%M
for i in range(n):a=(a+i*(n-i)*(m**2)*c)%M
for i in range(m):a=(a+i*(m-i)*(n**2)*c)%M
print(a)

Submission status: Accepted

Solution code:
import numpy as np
import sys
sys.setrecursionlimit(10 ** 7)

# 数え上げ

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

MOD = 10 ** 9 + 7


def cumprod(arr, MOD):
    L = len(arr)
    Lsq = int(L**.5+1)
    arr = np.resize(arr, Lsq**2).reshape(Lsq, Lsq)
    for n in range(1, Lsq):
        arr[:, n] *= arr[:, n-1]
        arr[:, n] %= MOD
    for n in range(1, Lsq):
        arr[n] *= arr[n-1, -1]
        arr[n] %= MOD
    return arr.ravel()[:L]


def make_fact(U, MOD):
    x = np.arange(U, dtype=np.int64)
    x[0] = 1
    fact = cumprod(x, MOD)
    x = np.arange(U, 0, -1, dtype=np.int64)
    x[0] = pow(int(fact[-1]), MOD-2, MOD)
    fact_inv = cumprod(x, MOD)[::-1]
    return fact, fact_inv


U = N * M + 10
fact, fact_inv = make_fact(U, MOD)
fact, fact_inv = fact.tolist(), fact_inv.tolist()


def mod_comb_k(n, k, mod):
    return fact[n] * fact_inv[k] % mod * fact_inv[n - k] % mod


# X
for dx in range(1, N):
    pat = N - dx
    ans += dx * pat * M * M
    ans %= MOD

# Y
for dy in range(1, M):
    pat = M - dy
    ans += dy * pat * N * N
    ans %= MOD

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

print(ans)

Submission status: Accepted

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

def comb(n, r, mod=10**9+7):
  if n==0 and r==0:
    return 1
  else:
    a = b = 1
    A, B = n, r
    for i in range(r):
      a = a*A % mod
      b = b*B % mod
      A -= 1
      B -= 1
    return a * pow(b, mod-2, mod) % mod

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

Submission status: Accepted

Solution code:
class Factorial():
    def __init__(self,n,mod):
        self.mod = mod
        self.factorial = [0 for _ in range(n+1)]
        self.inv = [0 for _ in range(n+1)]
        self.factorial[0] = 1
        self.inv[0] = 1
        for i in range(n):
            self.factorial[i+1] = self.factorial[i]*(i+1)%mod
        self.inv[n] = pow(self.factorial[n],mod-2,mod)
        for i in range(n)[::-1]:
            self.inv[i] = self.inv[i+1]*(i+1)%mod
    def comb(self,m,k): #組み合わせ 0<=k<=m<=n 重複組み合わせはcomb(m+k-1,k)
        return self.factorial[m]*self.inv[k]*self.inv[m-k]%self.mod

from collections import deque

MOD = 1000000007

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

F = Factorial(N*M,MOD)

print(F.comb(N*M-2,K-2)*(N+M)*N*M*(N*M-1)//6%MOD)

Submission status: Accepted

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

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
MAX_N = 10**6 # N >= n
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

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

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



def calc(p, q, d):
    return d * (p - d) * (q ** 2)

ans = 0

for i in range(N):
    ans += calc(N, M, i)
for i in range(M):
    ans += calc(M, N, i)

ans %= mod

ans *= k

ans %= mod

print(ans)

Submission status: Accepted

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

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

    class Comb:
        def __init__(self, N):
            self.fac = [1] * (N+1)
            for i in range(2, N+1): self.fac[i] = self.fac[i-1] * i % MOD

        def pow(self, a, b):
            res = 1
            while b:
                if b & 1: res = res * a % MOD
                a = a**2 % MOD
                b >>= 1
            return res

        def comb(self, n, r):
            if r < 0 or r > n: return 0
            return (self.fac[n] * self.pow(self.fac[r], MOD-2)) % MOD * self.pow(self.fac[n-r], MOD-2) % MOD

        def permutation(self, n, r):
            if r == 0: return 1
            return self.fac[n] * self.pow(self.fac[n-r], MOD-2) % MOD

    comb = Comb(N*M-2)

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

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

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,M,K=map(int,input().split())
def cmb(x,y):
  X=1
  Y=1
  for i in range(1,y+1):
    X= X*(x+1-i)%MOD
    Y= Y*i%MOD
  return (X*pow(Y,MOD-2,MOD))%MOD
MOD=10**9+7
A=cmb(M*N-2, K-2)
ans=0
for d in range(1,N):
  ans+=d*(N-d)*M*M*A%MOD
for d in range(1,M):
  ans+=d*(M-d)*N*N*A%MOD
print(ans%MOD)

Submission status: Accepted

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

#############

mod = 10**9 + 7
max = n*m + 10
fac, finv, inv = [0]*max, [0]*max, [0]*max

def comInit(max):
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1

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

comInit(max)

# 二項係数の計算
def com(n,k):
    if(n < k):
        return 0
    if( n<0 | k < 0):
        return 0
    return fac[n] * (finv[k] * finv[n-k] % mod) % mod

#############

ans = n*n*(m-1)*m*(m+1)//6 + m*m*(n-1)*n*(n+1)//6
ans = ans % mod
ans = (com(n*m -2, k-2) * ans) % mod

print(ans)

Submission status: Accepted

Solution code:
def power(a, b):
	if b == 0:
		return 1
	elif b == 1:
		return a % 1000000007
	elif b % 2 == 0:
		return (power(a, b//2) ** 2) % 1000000007
	else:
		return (power(a, b//2) ** 2 * a) % 1000000007
 
def divide(a, b):
	return (a * power(b, 1000000005)) % 1000000007

fac_lim = 200000
fac = [None]*(fac_lim+1)
fac[0] = 1
for i in range(fac_lim):
    fac[i+1] = fac[i] * (i+1)
    fac[i+1] = fac[i + 1] % 1000000007

fac_inv = [None]*(fac_lim+1)
fac_inv[fac_lim] = power(fac[fac_lim], 1000000005)
for i in range(fac_lim, 0, -1):
    fac_inv[i-1] = (fac_inv[i] * i)  % 1000000007

def conv(a, b):
    return (fac[a] * fac_inv[a-b] * fac_inv[b]) % 1000000007

MOD = 1000000007
N, M, K = (int(i) for i in input().split())
midN = 0
midM = 0
if N > 1:
    for i in range(1,N):
        midN += i*(N-i)*2
        midN % MOD
    midN = divide(midN, N**2)
else:
    midN = 0
if M > 1:
    for i in range(1,M):
        midM += i*(M-i)*2
        midM % MOD
    midM = divide(midM, M**2)
else:
    midM = 0
kt = (midN+midM)*(N*M)
kt = divide(kt, N*M-1)
pt = conv(N*M, K)
ans = kt*pt % MOD
ans = ans*K*(K-1) % MOD
ans = divide(ans, 2)
print(ans%MOD)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
from collections import deque, Counter
def getN():
    return int(input())
def getList():
    return list(map(int, input().split()))
import math
INF = 10 ** 20
MOD = 10**9 + 7
def combmod(n, k, mod=MOD):
    if k == 0:
        return 1
    if k == 1:
        return n
    ret = 1
    for i in range(n - k + 1, n + 1):
        ret *= i
        ret %= mod

    for i in range(1, k + 1):
        ret *= pow(i, mod - 2, mod)
        ret %= mod

    return ret

def main():
    n, m, k = getList()
    ans = 0
    mul = combmod(n*m-2, k-2)
    for i in range(0, n):
        for j in range(0, m):
            tmp = (j+i) * (n-i) * (m-j) * mul
            if i != 0 and j != 0:
                tmp *= 2
            ans += tmp
            ans %= MOD
            # print(ans,mul)

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

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7


def prepare(n):
    global MOD
    modFacts = [0] * (n + 1)
    modFacts[0] = 1
    for i in range(n):
        modFacts[i + 1] = (modFacts[i] * (i + 1)) % MOD

    invs = [1] * (n + 1)
    invs[n] = pow(modFacts[n], MOD - 2, MOD)
    for i in range(n, 1, -1):
        invs[i - 1] = (invs[i] * i) % MOD

    return modFacts, invs


def modCombi(n, r):
    global MOD
    return (modFacts[n] * invs[n - r] * invs[r]) % MOD


N, M, K = map(int, input().split())
modFacts, invs = prepare(N * M)
var = modCombi(N * M - 2, K - 2)

ans = 0
if N < M:
    N, M = M, N
L = [0] * (N + 1)
for i in range(1, N + 1):
    L[i] = L[i - 1] + i
for x in range(1, N + 1):
    for y in range(1, M + 1):
        Sx = (M * (L[N - x] + L[x - 1])) % MOD
        Sy = (N * (L[M - y] + L[y - 1])) % MOD
        ans += (Sx + Sy) % MOD

print((ans * invs[2] * var) % MOD)

Submission status: Accepted

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

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

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


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


ans = 0
# Hについて
for d in range(1, H):
    ans += d * (H - d) * pow(W, 2, MOD) * nCr(H * W - 2, K - 2) % MOD
    ans %= MOD
# Wについて
for d in range(1, W):
    ans += d * (W - d) * pow(H, 2, MOD) * nCr(H * W - 2, K - 2) % MOD
    ans %= MOD

print(ans % MOD)