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: Runtime Error

Solution code:
a, b, c = map(int,input().split())
e = [23] * 300000
e[-1] += 1
for i in range(100):
  i < 1000:
    continue
  w = e[3]
print(1)

Submission status: Runtime Error

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

for i in range(1, K - 1):
    C *= N * M - i - 1
    C //= i
    
for i in range(N):
    for j in range(M):
        ad = (N - i) * (M - j) * (i + j)
        if i != 0 and j != 0:
            ad *= 2
            ans += ad    
print(ans * C % MOD)
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef vector<ll> vl;
typedef pair<ll, ll> PP;
#define rep(i, n) for(ll i = 0; i < ll(n); i++)
template <class T> void corner(bool flg, T hoge) {
    if(flg) {
        cout << hoge << endl;
        exit(0);
    }
}
#define all(v) v.begin(), v.end()
#define inputv(v, n)                                                           \
    vl v;                                                                      \
    rep(i, n) {                                                                \
        ll x;                                                                  \
        cin >> x;                                                              \
        v.push_back(x);                                                        \
    }
const ll INF = 999999999999999;
const ll MOD = 1000000007;
ll a, b, c, d, e, f, p, t, x, y, z, q, m, n, r, h, k, w, l, ans = 0;
#include <cstdint>

template <std::uint_fast64_t Modulus> class modint {
    using u64 = std::uint_fast64_t;

  public:
    u64 a;

    constexpr modint(const u64 x = 0) noexcept : a(x % Modulus) {}
    constexpr u64 &value() noexcept { return a; }
    constexpr const u64 &value() const noexcept { return a; }
    constexpr modint operator+(const modint rhs) const noexcept {
        return modint(*this) += rhs;
    }
    constexpr modint operator-(const modint rhs) const noexcept {
        return modint(*this) -= rhs;
    }
    constexpr modint operator*(const modint rhs) const noexcept {
        return modint(*this) *= rhs;
    }
    constexpr modint operator/(const modint rhs) const noexcept {
        return modint(*this) /= rhs;
    }
    constexpr modint &operator+=(const modint rhs) noexcept {
        a += rhs.a;
        if(a >= Modulus) {
            a -= Modulus;
        }
        return *this;
    }
    constexpr modint &operator-=(const modint rhs) noexcept {
        if(a < rhs.a) {
            a += Modulus;
        }
        a -= rhs.a;
        return *this;
    }
    constexpr modint &operator*=(const modint rhs) noexcept {
        a = a * rhs.a % Modulus;
        return *this;
    }
    constexpr modint &operator/=(modint rhs) noexcept {
        u64 exp = Modulus - 2;
        while(exp) {
            if(exp % 2) {
                *this *= rhs;
            }
            rhs *= rhs;
            exp /= 2;
        }
        return *this;
    }
};

using mint = modint<MOD>;
int main() {
    cin >> n >> m >> k;
    vl v1, v2, v(200100, 0);
    vector<mint> kaijo(n * m + 1);

    kaijo[0] = 1;
    rep(i, n * m) { kaijo[i + 1] = kaijo[i] * (i + 1); }
    rep(i, n) { v1.push_back(n - i); }
    rep(j, m) { v2.push_back(m - j); }

    rep(i, n) {
        rep(j, m) {
            if(i * j == 0) {
                v[i + j] += v1[i] * v2[j];
            } else {
                v[i + j] += v1[i] * v2[j] * 2;
            }
            v[i+j]%=MOD;
        }
    }

    mint ans=0,x;
    x=kaijo[n*m-2]/(kaijo[n*m-k]*kaijo[k-2]);
    rep(i,m+n){
        ans+=x*(v[i]*i);
    }

    cout << ans.a << endl;
}

Submission status: Runtime Error

Solution code:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1LL<<60;
#define all(x) (x).begin(),(x).end()
#define REP(i,n) for(int i=0; i<(n);++i)
#define FOR(i,k,n) for(int i=(k);i<(n);++i)


const int MAX = 1000005;
const ll MOD = 1000000007;

ll fac[MAX], finv[MAX], inv[MAX];

void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

int main(){
    int N, M, K; cin >> N >> M >> K;
    COMinit();
    ll cost = 0;
    REP(i,N)REP(j,M){
        cost += M*((i+1)*i/2+(N-i)*(N-i-1)/2) + N*((j+1)*j/2+(M-j)*(M-j-1)/2);
        cost %= MOD;
    }
    cost = (cost*500000004)%MOD;
    cost =(COM(N*M-2,K-2)*cost) %MOD;
    cout << cost << endl;
    return 0;
}

Submission status: Runtime Error

Solution code:
class combination():
    #素数のmod取るときのみ　速い
    def __init__(self, n, mod):
        self.n = n
        self.fac = [1] * (n + 1)
        self.inv = [1] * (n + 1)
        for j in range(1, n + 1):
            self.fac[j] = self.fac[j - 1] * j % mod

        self.inv[n] = pow(self.fac[n], mod - 2, mod)
        for j in range(n - 1, -1, -1):
            self.inv[j] = self.inv[j + 1] * (j + 1) % mod

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


import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
mod = 10**9 + 7
inf = float('inf')
ans = int(0)

N, M, K = LI()

cou = int(0)
#maxL = N + M -2
L = int(0)
#距離i+1の組み合わせ

#for i in range(maxL):
for j in range(N):
    L += (N - j - 1) * (M ** 2) * (j + 1)
    L %= mod
for j in range(M):
    L += (M - j - 1) * (N ** 2) * (j + 1)
    L %= mod
#    for j in range(i+2):
#        if i>1 and i+1>j>0:
#            L[i] += max((N-j)*(M-(1+i)+j),0)*(i+1)*2
#        else:
#            L[i] += max(((N - j) * (M - (1 + i) + j)), 0) * (i + 1)
C = combination(N*M-2,mod)
cou = C.comb(N*M-2,K-2)*L%mod

print(cou)

Submission status: Runtime Error

Solution code:
from itertools import prodcut
n,m,k = map(int, input().split())
a, b = list(range(n)), list(range(m))
l = product(a,b)

Submission status: Runtime Error

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

MOD = 1000000007  # type: int

def mfact():
    f = [1]
    for i in range(1, 20000):
        f.append(f[-1] * i % MOD)
    return f

def inv(x):
    res = 1
    k = MOD - 2
    y = x
    while (k):
        if(k % 2 == 1):
            res = (res * y) % MOD
        y = (y ** 2) % MOD
        k = k // 2
    return res

def comb(n, k, f):
    if n < k or n < 0 or k < 0:
        return 0
    a = f[n]
    b = f[n-k]
    c = f[k]
    bc = (b * c) % MOD
    return (a * inv(bc)) % MOD

def solve(N: int, M: int, K: int):
    ans = 0
    for i in range(N):
        for j in range(M):
            a = j * (j+1) // 2
            b = (M-1-j) * (M-1-j+1) // 2
            ans += (a+b) * i + M * (i*(i+1)//2) + a
            ans %= MOD
    f = mfact()
    ans *= comb(N*M-2, K-2, f)
    ans %= MOD
    print(ans)
    return


# Generated by 1.1.5 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: Runtime Error

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
mod = 10**9+7 #出力の制限
N = 10**5
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
def p(n,r):
    if ( r<0 or r>n ):
        return 0
    return g1[n] * g2[n-r] % mod

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 )
# a = cmb(n,r)


n,m,k = m()

sx = 0
sy = 0

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

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

Submission status: Runtime Error

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
mod = 10**9+7 #出力の制限
N = 10**5
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
def p(n,r):
    if ( r<0 or r>n ):
        return 0
    return g1[n] * g2[n-r] % mod

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 )
# a = cmb(n,r)


n,m,k = m()

sx = 0
sy = 0

for i in range(1,n):
    sx += (n-i) * (m**2) * cmb(n*m-2,k-2)

for i in range(1,m):
    sy += (m-i) * (n**2) * cmb(n*m-2,k-2)

print(sx+sy)

Submission status: Runtime Error

Solution code:
N,M,K=map(int,input().split())
MOD=10**9+7
def comb(n, k):
    m = 1
    if n < 2 * k:
        k = n - k
    for i in range(1, k + 1):
        m = m * (n - i + 1) / i    
    return m
for i in range(1,N):
  ans_x+=(i*(N-i))
for i in range(1,M):
  ans_y+=(i*(M-i))
ans_x*=M**2
ans_y*=X**2
print(conb(NM-2,K-2)*(ans_x+ans_y)%MOD)

Submission status: Runtime Error

Solution code:
from math import factorial


mod = 10**9+7
n, m, k = list(map(int, input().split()))
# 　ある配置を固定した時、その2つの配置でmanhattan距離が計算される回数は、他の組み合わせ数。
combination = mod_combination(n*m-2, k-2)

def dfs(arg_one, arg_two, mod):
    arg_squrared = ((arg_one%mod)**2)%mod
    return sum([((i%mod)*(arg_two-i)%mod)%mod*arg_squrared for i in range(1, arg_two)])



def mod_combination(n, r, mod=10**9+7):
    fact = 1
    for i in range(n-r+1, n+1):
        fact = fact * i % mod
    divisor = 1
    for j in range(1, r+1):
        divisor = divisor * j % mod
    return int(fact/divisor)


print(((dfs(m, n, mod) + dfs(n, m, mod))*combination)%mod)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

from scipy.misc import comb

def man_comb(_N, _K):
    if _K > (_N/2):
        return comb(_N, _N - _K, exact=True)
    else:
        return comb(_N, _K, exact=True)

MAX = 10**9 + 7

def mod_inv(i, mod):
    return pow(i, mod-2, mod)

def combination(_N, _K):
    if _K > (_N/2):
        _K = _N - _K
    up = 1
    low = 1
    for i in range (_K):
        up = up * (_N - i) % MAX
        low = low * (i + 1) % MAX
    ret = up * mod_inv(low, MAX) % MAX
    return ret

def solve():
    N, M, K = [int(_) for _ in raw_input().split()]
    disSum = M*N* (M*(N+1)*(N-1) + N*(M+1)*(M-1)) // 6
    ret = disSum * combination(M*N-2, K-2) % MAX
    print ret

def cum_sum(N):
    return N * (N+1) // 2

def solve2():
    N, M, K = [int(_) for _ in raw_input().split()]
    sumx = 0
    for xi in range(1, N+1):
        sumx = (sumx + cum_sum(N) - (N + 1 - xi) * xi)
    sumx = (sumx * M * M) // 2 %MAX
    sumy = 0
    for yi in range(1, M+1):
        sumy = (sumy + cum_sum(M) - (M + 1 - yi) * yi)
    sumy = (sumy * N * N) // 2 %MAX
    ret = (sumx + sumy) * combination(M*N-2, K-2) % MAX
    print ret

if __name__ == '__main__':
    solve2()

Submission status: Runtime Error

Solution code:
import sys
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def II(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
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 SI(): return input()
YN = lambda b: print('YES') if b else print('NO')
yn = lambda b: print('Yes') if b else print('No')

from scipy.special import comb

def main():
    N, M, K = LI()

    rows = M*M*sum([d * (N-d) for d in range(1, N)])
    cols = N*N*sum([d * (M-d) for d in range(1, M)])
    ans = (rows + cols) * comb(M*N-2, K-2, exact=True) % MOD

    print(ans)

main()

Submission status: Runtime Error

Solution code:
def combination(_N, _K):
    if _K > (_N/2):
        _K = _N - _K
    up = 1
    low = 1
    for i in range (_K):
        up *= (_N - i)
        low *= (i + 1)
    ret = up /low
    if ret >= MAX:
        ret %= MAX
    return ret

def solve():
    N, M, K = [int(_) for _ in raw_input().split()]
    disSum = M*N* (M*(N+1)*(N-1) + N*(M+1)*(M-1)) / 6
    if disSum >= MAX:
        disSum %= MAX
    ret = disSum * combination(M*N-2, K-2)
    if ret >= MAX:
        ret %= MAX
    print ret

if __name__ == '__main__':
    solve()

Submission status: Runtime Error

Solution code:

N, M = map(int, input().split())
in_hand = list(map(int, input().split()))
in_hand.sort()

for line in range(M):
    change_count, change_number = map(int, input().split())
    in_hand.sort()
    for i in range(change_count):
        if in_hand[i] < change_number:
            in_hand[i] = change_number
        else:
            break

print(sum(in_hand))

Submission status: Runtime Error

Solution code:
import sys
import itertools


fin = sys.stdin.readline
N, M, K = [int(elem) for elem in fin().split()]

# すべてのマス目
all_cell = list(itertools.product(list(range(1, N+1)), list(range(1, M+1))))
all_combi = list(itertools.combinations(all_cell, K))
all_sum = 0

for each_combi in tqdm(all_combi):
    x_list = [x[0] for x in each_combi]
    y_list = [x[1] for x in each_combi]

    x_combi = list(itertools.combinations(x_list, 2))
    y_combi = list(itertools.combinations(y_list, 2))

    x_dif_list = [abs(x[0] - x[1]) for x in x_combi]
    y_dif_list = [abs(y[0] - y[1]) for y in y_combi]

    all_sum += sum(x_dif_list) + sum(y_dif_list)

print(all_sum % (10**9 + 7))

Submission status: Runtime Error

Solution code:
from scipy.special import comb

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

C = comb(N*M-2, K-2)
print(int(C))

A = int(0)
for d in range(N):
    a = (N-d)*(M**2)

    A += int(d*a)

B = int(0)
for d in range(M):
    b = (M-d)*(N**2)
    B += int(d*b)

ans = int((A+B)*C)
print(ans)

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std;

void MOD(vector<bool> &mod) {
	int n = 1000000005;
	for (int i = 0;i < 30;i++) {
		if (n % 2==1)
			mod[i] = true;
		else
			mod[i] = false;
		n /= 2;
	}
}

long long rev(long long n,vector<bool> mod) {
	//~10e9+5
	vector <long long> da(30,n);
	long long ans=1;
	if (mod[0])
		ans = n;
	for (int i = 1;i < 30;i++) {
		da[i] = (long long)(da[i - 1] * da[i - 1]) % 1000000007;
		if (mod[i])
			ans = (ans * da[i]) % 1000000007;
	}
	return ans;
}

long long kaijo(long long n) {
	if (n < 1)
		return 1;
	else
		return (n*kaijo(n - 1)) % 1000000007;
}

long long COMB(long long n, long long k,vector<bool> mod) {
	long long ans = (rev(kaijo(k),mod)*rev(kaijo(n - k),mod)) % 1000000007;
	return (kaijo(n)*ans) % 1000000007;
}

int main() {
	long long n, m, k;
	cin >> n >> m >> k;
	vector<bool> mod(30);
	MOD(mod);
	long long ans = 0;
	//n*m-2Ck-2*m*m*(n-i)
	long long pat = (m*m) % 1000000007;
	long long comb = COMB(n*m - 2, k - 2,mod);
	for (int i = 1;i < n;i++) {
		int x = ((n - i)*pat) % 1000000007;
		x = (x*comb) % 1000000007;
		x = (x*i) % 1000000007;
		ans += (ans + x) % 1000000007;
	}
	pat = (n*n) % 1000000007;
	for (int i = 1;i < m;i++) {
		int x = ((m - i)*pat) % 1000000007;
		x = (x*comb) % 1000000007;
		x = (x*i) % 1000000007;
		ans = (ans + x) % 1000000007;
	}
	cout << ans << endl;
}

Submission status: Runtime Error

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

MOD = 1000000007  # type: int

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

N = 10**5
g1 = [1, 1]
g2 = [1, 1]
inv = [0, 1]

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

def solve(N: int, M: int, K: int):
    ans = 0
    for i in range(1, M):
        ans += i * N**2 * (M-i)
        ans %= MOD
    for i in range(1, N):
        ans += i * M**2 * (N-i)
        ans %= MOD
    ans *= cmb(N*M-2, K-2, MOD)
    ans %= MOD
    print(ans)
    return


# 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: Runtime Error

Solution code:
n,m,k = map(int, input().split())
mod = 10**9+7
def cc(a,b):
  b = min(b,a-b)
  tot = 1
  for i in range(1,b+1):
    tot = (tot*(a-i+1)//i)%mod
  return tot
xans = 0
yans = 0
for i in range(1,n):
  xans+=i*(n-i)*m**2
  xans%=mod
for j in range(1,m):
  yans+=i*(m-i)*n**2
  yans%=mod
print((xans+yans)*cc(n*m-2,k-2)%mod)

Submission status: Runtime Error

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


S = 0

def stick(n):
    return n * (n+1) // 2

def calc(w, h):
    L = w * (w-1) // 2
    R = L + w * (h-1)
    return (L + R) * h // 2

for i in range(n):
    for j in range(m):
        S += calc(i+1, j+1)
        S += calc(i+1, m-j)
        S += calc(n-i, j+1)
        S += calc(n-i, m-j)
        S -= stick(i)
        S -= stick(j)
        S -= stick(n-i-1)
        S -= stick(m-j-1)
        S %= MOD
if S % 2 == 0:S //= 2
else: S = (S + MOD) // 2
S %= MOD
if S < 0:S += MOD
def fact(x):
    if x == 0:return 1
    else: return x * fact(x-1) % MOD

def rev(x):
    return pow(x, MOD-2, MOD)

def nCk(n, k):
    return fact(n) * rev(fact(k)) % MOD * rev(fact(n-k)) % MOD

print(S * nCk(n+m-2, k-2) % MOD)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10 ** 5)


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 II(): return int(sys.stdin.readline())
def SI(): return input()

m = 1E9+7

N, M, K = LI()
def com(a, b):# N*M-2, K-2
    b = min(b, a-b)
    if b==0:
        return 1;
    c = 1
    for i in range(1, b+1):
        c *= (a-i+1)//i
        # c %= m
    return c

ans1 = com(N*M-2, K-2) % m

ans2 = (N**2 * M * (M-1) * (M+1) // 6) % m
ans2 += (M**2 * N * (N-1) * (N+1) // 6) % m

print( int((ans1*ans2)%m) )

Submission status: Runtime Error

Solution code:
n,m,k = map(int, input().split())
mod = 10**9+7
def cc(a,b):
  b = min(b,a-b)
  tot = 1
  for i in range(1,b+1):
    tot = (tot*(a-i+1)//i)%mod
    return tot
xans = 0
yans = 0
for i in range(1,n):
  xans+=i*(n-i)*m**2
  xans%=mod
for j in range(1,m):
  yans+=i*(m-i)*n**2
  yans%=mod
print((xans+yans)*cc(n*m-2,k-2)%mod)

Submission status: Runtime Error

Solution code:
import heapq

N, M = map(int, input().split())
A = list(map(int, input().split()))
BC = [list(map(int, input().split())) for i in range(M)]

if N == 1:
    print(max(A[0], BC[0][1]))
    quit()

heapq.heapify(A)
for b, c in BC:
    a = A[0]
    if a >= c:
        continue
    else:
        curPopped = 0
        while curPopped < b:
            a = heapq.heappop(A)
            if a >= c:
                heapq.heappush(A, a)
                break
            curPopped += 1
        for i in range(curPopped):
            heapq.heappush(A, c)

print(sum(A))

Submission status: Runtime Error

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 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


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

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

    ans = 0

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

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

    ans = ans % MOD
    print(ans)


if __name__ == '__main__':
    main()
# 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 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


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

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

    ans = 0

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

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

    ans = ans % MOD
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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))
for i in range(1, m):
    ans += (comb * n * n * (i)) * (m - i))) % inf
    ans = ans % inf
for i in range(1, n):
    ans += (comb * m * m * (i) * (n - i)) % inf
    ans = ans % inf
ans = ans % inf
print(ans)

Submission status: Runtime Error

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)
for i in range(1, m):
    ans += (comb * n * n * (i)) * (m - i))) % inf
    ans = ans % inf
for i in range(1, n):
    ans += (comb * m * m * (i) * (n - i)) % inf
    ans = ans % inf
ans = ans % inf
print(ans)

Submission status: Runtime Error

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

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

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


ans = 0
for x in range(1,M):
    ans += x*(M-x)*n2*cmb(nm-2,K-2,mod)
    ans %= mod

for y in range(1,N):
    ans += y*(N-y)*m2*cmb(nm-2,K-2,mod)
    ans %= mod

print(int(ans))

Submission status: Runtime Error

Solution code:
import sys
from itertools import combinations
try:
    from scipy.special import comb
except ImportError:
    from scipy.misc import comb

def main():
    input = sys.stdin.readline
    MOD = 10**9 + 7
    N, M, K = map(int, input().split())
    # The number of times that pieces are located on certain two tiles.
    num = int(comb(N*M-2, K-2))

    ans = 0
    # Column-wise distance
    for a, b in combinations(range(M), 2):
        ans += abs(a - b) * N**2 * num
        ans %= MOD

    # Row-wise distance
    for a, b in combinations(range(N), 2):
        ans += abs(a - b) * M**2 * num
        ans %= MOD

    return ans


if __name__ == '__main__':
    print(main())

Submission status: Runtime Error

Solution code:
import sys
#import numpy as np
from scipy.special import comb

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in ss]
ss2nnn = lambda ss: [s2nn(s) for s in ss]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline().rstrip() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

def main():
    N, M, K = i2nn()
    L = max(M, N)
    dp = [0] * L
    for i in range(1, L):
        dp[i] = dp[i-1] + i
    n = 0
    for i in range(N):
        n += (dp[i] + dp[N-1-i]) * M * M
    for i in range(M):
        n += (dp[i] + dp[M-1-i]) * N * N
    n = int(n / 2)
    r = comb(N*M-2, K-2, exact=True)
    n = n * r % (int(1e+9)+7)
    print(n)

main()

Submission status: Runtime Error

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

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

def mCn(m,n):
    return math.factorial(m)//(math.factorial(n)*math.factorial(m-n)) % mod
#modに対応して高速なコンビネーションが求められる
# 階乗 & 逆元計算
n = 10**5
factorial = [1]
inverse = [1]
for i in range(1, n+2):
    factorial.append(factorial[-1] * i % mod)
    inverse.append(pow(factorial[-1], mod-2, mod))

def combinations_count(n,r):
    if n-r < 0:
        return 0
    return factorial[n]*inverse[r]*inverse[n-r]%mod


ans = 0
for i in range(1,M):
    ans += (M-i)*N**2*i*(combinations_count(M*N-2,K-2))
    if ans > mod:
        ans = ans % mod

for i in range(1,N):
    ans += (N-i)*M**2*i*(combinations_count(M*N-2,K-2))
    if ans > mod:
        ans = ans % mod

print(ans)

Submission status: Runtime Error

Solution code:
def power_mod(a,b,mod=10**9+7):
    i,temp,box=0,b,[]
    while(2**i<=b):
        i+=1
    for j in range(i-1,-1,-1):
        box=[[j,temp//2**j]]+box
        temp-=2**j*(temp//2**j)
    box[0].append(a)
    ans=box[0][1]*a%mod
    for j in range(1,i):
        box[j].append(box[j-1][2]**2%mod)
        if box[j][1]==1:
            ans=(ans*box[j][2])%mod
    return ans
def n_func(n,mod=10**9+7):
    ans=1
    for i in range(1,n+1):
        ans=(ans*i)%mod
    return ans
def nPr(n,r,mod=10**9+7):
    ans=n_func(n-r,mod)
    ans=power_mod(ans,mod-2,mod)
    return ans*n_func(n,mod)%mod
def nCr(n,r,mod=10**9+7):
    ans=n_func(n-r,mod)*n_func(r,mod)%mod
    ans=power_mod(ans,mod-2,mod)
    return ans*n_func(n,mod)%mod

N,M,K=map(int,input().split())
keisuu=nCr(N*M-2,K-2)

sum_=0
for i in range(N):
    a=min(abs(i),abs(N-i-1))
    b=max(abs(i),abs(N-i-1))
    sum_+=(M**2)*((a*(a+1)//2)+(b*(b+1)//2))
for i in range(M):
    a=min(abs(i),abs(M-i-1))
    b=max(abs(i),abs(M-i-1))
    sum_+=(N**2)*((a*(a+1)//2)+(b*(b+1)//2))
print((keisuu * (sum_//2))%mod)