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:
def com(n,r):
    if n-r<r:
        r=n-r
    re=1
    for i in range(n,n-r,-1):
        re*=i
    for i in range(1,r+1):
        re//=i
    return re

def f(n,m,k):
    md = 10 ** 9 + 7
    ans = 0
    for d in range(1, m):
        ans = (ans + d * (m - d) * n * n) % md
    for d in range(1, n):
        ans = (ans + d * (n - d) * m * m) % md
    ans = (ans * com(n * m - 2, k - 2)) % md
    print(ans)

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

Submission status: Time Limit Exceeded

Solution code:
from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

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

mod = 10 ** 9 + 7
ans= 0
NCK = cmb(N*M-2,K-2) % mod
M2 = M**2 * NCK
N2 = N**2 * NCK
for i in range(N-1):
    for j in range(i,N):
        ans += M2 * (j-i) 
        ans %= mod
        
for i in range(M-1):
    for j in range(i,M):
        ans += N2 * (j-i) 
        ans %= mod
        
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

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

mod = 10 ** 9 + 7
ans= 0
NCK = cmb(N*M-2,K-2) % mod

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

Submission status: Time Limit Exceeded

Solution code:
def com(n,r):
    if n-r<r:
        r=n-r
    re=1
    for i in range(n,n-r,-1):
        re*=i
    for i in range(1,r+1):
        re//=i
    return re

md=10**9+7
n,m,k=map(int,input().split())
ans=0
for d in range(1,m):
    ans=(ans+d*(m-d)*n*n)%md
for d in range(1,n):
    ans=(ans+d*(n-d)*m*m)%md
ans=(ans*com(n*m-2,k-2))%md
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def com(n,r):
    if n-r<r:
        r=n-r
    re=1
    for i in range(n,n-r,-1):
        re*=i
    for i in range(1,r+1):
        re//=i
    return re

md=10**9+7
n,m,k=map(int,input().split())
ans=0
for d in range(1,m):
    ans+=d*(m-d)*n*n
for d in range(1,n):
    ans+=d*(n-d)*m*m
ans=ans*com(n*m-2,k-2)
print(ans%md)

Submission status: Time Limit Exceeded

Solution code:
import sys
from itertools import combinations

def comb_mod(n, r, MOD=10**9+7):
    if n < 0 or r < 0 or n < r:
        return 0

    factrial = [1] * (n+1)
    for k in range(1, n+1):
        factrial[k] = (factrial[k-1] * k) % MOD

    fact_inv = [1] * (n+1)
    fact_inv[n] = pow(factrial[n], MOD - 2, MOD)
    for k in range(n-1, -1, -1):
        fact_inv[k] = (fact_inv[k+1] * (k+1)) % MOD

    return (factrial[n] * fact_inv[r] * fact_inv[n-r]) % MOD


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

Solution code:
###############################################################################

from sys import stdout
from bisect import bisect_left as binl
from copy import copy, deepcopy
from collections import defaultdict
import math


mod = 1


def intin():
    input_tuple = input().split()
    if len(input_tuple) <= 1:
        return int(input_tuple[0])
    return tuple(map(int, input_tuple))


def intina():
    return [int(i) for i in input().split()]


def intinl(count):
    return [intin() for _ in range(count)]


def modadd(x, y):
    global mod
    return (x + y) % mod


def modmlt(x, y):
    global mod
    return (x * y) % mod


def lcm(x, y):
    while y != 0:
        z = x % y
        x = y
        y = z
    return x


def combination(x, y):
    assert(x >= y)

    ret = math.factorial(x)
    ret = ret // (math.factorial(x - y) * math.factorial(y))

    return ret


def get_divisors(x):
    retlist = []
    for i in range(1, int(x**0.5) + 3):
        if x % i == 0:
            retlist.append(i)
            retlist.append(x // i)
    return retlist


def get_factors(x):
    retlist = []
    for i in range(2, int(x**0.5) + 3):
        while x % i == 0:
            retlist.append(i)
            x = x // i
    retlist.append(x)
    return retlist


def make_linklist(xylist):
    linklist = {}
    for a, b in xylist:
        linklist.setdefault(a, [])
        linklist.setdefault(b, [])
        linklist[a].append(b)
        linklist[b].append(a)
    return linklist


def calc_longest_distance(linklist, v=1):
    distance_list = {}
    distance_count = 0
    distance = 0
    vlist_previous = []
    vlist = [v]
    nodecount = len(linklist)

    while distance_count < nodecount:
        vlist_next = []
        for v in vlist:
            distance_list[v] = distance
            distance_count += 1
            vlist_next.extend(linklist[v])
        distance += 1
        vlist_to_del = vlist_previous
        vlist_previous = vlist
        vlist = list(set(vlist_next) - set(vlist_to_del))

    max_distance = -1
    max_v = None
    for v, distance in distance_list.items():
        if distance > max_distance:
            max_distance = distance
            max_v = v

    return (max_distance, max_v)


def calc_tree_diameter(linklist, v=1):
    _, u = calc_longest_distance(linklist, v)
    distance, _ = calc_longest_distance(linklist, u)
    return distance


class UnionFind:

    def __init__(self, n):
        self.parent = [i for i in range(n)]

    def root(self, i):
        if self.parent[i] == i:
            return i
        self.parent[i] = self.root(self.parent[i])
        return self.parent[i]

    def unite(self, i, j):
        rooti = self.root(i)
        rootj = self.root(j)
        if rooti == rootj:
            return
        if rooti < rootj:
            self.parent[rootj] = rooti
        else:
            self.parent[rooti] = rootj

    def same(self, i, j):
        return self.root(i) == self.root(j)


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


mod = 10**9 + 7


def main():
    n, m, k = intin()

    c = combination(n * m - 2, k - 2) % mod

    x_ans = ((n - 1) * n * (n + 1)) // 6
    x_ans = modmlt(x_ans, m)
    x_ans = modmlt(x_ans, m)
    x_ans = modmlt(x_ans, c)

    y_ans = ((m - 1) * m * (m + 1)) // 6
    y_ans = modmlt(y_ans, n)
    y_ans = modmlt(y_ans, n)
    y_ans = modmlt(y_ans, c)

    print(modadd(x_ans, y_ans))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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, exact=True))

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

Solution code:
from operator import mul
from functools import reduce

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



def n_C_r(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

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

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

print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
###############################################################################

from sys import stdout
from bisect import bisect_left as binl
from copy import copy, deepcopy
from collections import defaultdict
import math


mod = 1


def intin():
    input_tuple = input().split()
    if len(input_tuple) <= 1:
        return int(input_tuple[0])
    return tuple(map(int, input_tuple))


def intina():
    return [int(i) for i in input().split()]


def intinl(count):
    return [intin() for _ in range(count)]


def modadd(x, y):
    global mod
    return (x + y) % mod


def modmlt(x, y):
    global mod
    return (x * y) % mod


def lcm(x, y):
    while y != 0:
        z = x % y
        x = y
        y = z
    return x


def combination(x, y):
    assert(x >= y)

    ret = math.factorial(x)
    ret = ret // math.factorial(x - y)
    ret = ret // math.factorial(y)

    return ret


def get_divisors(x):
    retlist = []
    for i in range(1, int(x**0.5) + 3):
        if x % i == 0:
            retlist.append(i)
            retlist.append(x // i)
    return retlist


def get_factors(x):
    retlist = []
    for i in range(2, int(x**0.5) + 3):
        while x % i == 0:
            retlist.append(i)
            x = x // i
    retlist.append(x)
    return retlist


def make_linklist(xylist):
    linklist = {}
    for a, b in xylist:
        linklist.setdefault(a, [])
        linklist.setdefault(b, [])
        linklist[a].append(b)
        linklist[b].append(a)
    return linklist


def calc_longest_distance(linklist, v=1):
    distance_list = {}
    distance_count = 0
    distance = 0
    vlist_previous = []
    vlist = [v]
    nodecount = len(linklist)

    while distance_count < nodecount:
        vlist_next = []
        for v in vlist:
            distance_list[v] = distance
            distance_count += 1
            vlist_next.extend(linklist[v])
        distance += 1
        vlist_to_del = vlist_previous
        vlist_previous = vlist
        vlist = list(set(vlist_next) - set(vlist_to_del))

    max_distance = -1
    max_v = None
    for v, distance in distance_list.items():
        if distance > max_distance:
            max_distance = distance
            max_v = v

    return (max_distance, max_v)


def calc_tree_diameter(linklist, v=1):
    _, u = calc_longest_distance(linklist, v)
    distance, _ = calc_longest_distance(linklist, u)
    return distance


class UnionFind:

    def __init__(self, n):
        self.parent = [i for i in range(n)]

    def root(self, i):
        if self.parent[i] == i:
            return i
        self.parent[i] = self.root(self.parent[i])
        return self.parent[i]

    def unite(self, i, j):
        rooti = self.root(i)
        rootj = self.root(j)
        if rooti == rootj:
            return
        if rooti < rootj:
            self.parent[rootj] = rooti
        else:
            self.parent[rooti] = rootj

    def same(self, i, j):
        return self.root(i) == self.root(j)


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


mod = 10**9 + 7


def main():
    n, m, k = intin()

    c = combination(n * m - 2, k - 2) % mod

    x_ans = ((n - 1) * n * (n + 1)) // 6
    x_ans = modmlt(x_ans, m)
    x_ans = modmlt(x_ans, m)
    x_ans = modmlt(x_ans, c)

    y_ans = ((m - 1) * m * (m + 1)) // 6
    y_ans = modmlt(y_ans, n)
    y_ans = modmlt(y_ans, n)
    y_ans = modmlt(y_ans, c)

    print(modadd(x_ans, y_ans))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

def comb(n, r) :
    if n - r < 0 or r < 0 :
        return 0
    
    r = min(n-r, r)

    a, b = 1, 1
    for i in range(r) :
        a *= n - i
        b *= i + 1

    return a // b

res = 0

for i in range(1, N + 1) :
    for j in range(1, M + 1) :
        if i > 1 and j > 1 :
            res += 2 * (N + 1 - i) * (M + 1 - j) * (i + j - 2)
        else :
            res += (N + 1 - i) * (M + 1 - j) * (i + j - 2)

res *= comb(N * M - 2, K - 2)

print(res % MOD)

Submission status: Time Limit Exceeded

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

def comb(n, r) :
    if n - r < 0 or r < 0 :
        return 0
    
    r = min(n-r, r)

    a, b = 1, 1
    for i in range(r) :
        a *= (n - i) % MOD
        b *= (i + 1) % MOD

    return (a // b) % MOD

res = 0

for i in range(1, N + 1) :
    for j in range(1, M + 1) :
        if i > 1 and j > 1 :
            res += 2 * (N + 1 - i) * (M + 1 - j) * (i + j - 2)
        else :
            res += (N + 1 - i) * (M + 1 - j) * (i + j - 2)

res *= comb(N * M - 2, K - 2)

print(res % MOD)

Submission status: Time Limit Exceeded

Solution code:
###############################################################################

from sys import stdout
from bisect import bisect_left as binl
from copy import copy, deepcopy
from collections import defaultdict
import math


mod = 1


def intin():
    input_tuple = input().split()
    if len(input_tuple) <= 1:
        return int(input_tuple[0])
    return tuple(map(int, input_tuple))


def intina():
    return [int(i) for i in input().split()]


def intinl(count):
    return [intin() for _ in range(count)]


def modadd(x, y):
    global mod
    return (x + y) % mod


def modmlt(x, y):
    global mod
    return (x * y) % mod


def lcm(x, y):
    while y != 0:
        z = x % y
        x = y
        y = z
    return x


def combination(x, y):
    assert(x >= y)

    ret = math.factorial(x)
    ret = ret // math.factorial(x - y)
    ret = ret // math.factorial(y)

    return ret


def get_divisors(x):
    retlist = []
    for i in range(1, int(x**0.5) + 3):
        if x % i == 0:
            retlist.append(i)
            retlist.append(x // i)
    return retlist


def get_factors(x):
    retlist = []
    for i in range(2, int(x**0.5) + 3):
        while x % i == 0:
            retlist.append(i)
            x = x // i
    retlist.append(x)
    return retlist


def make_linklist(xylist):
    linklist = {}
    for a, b in xylist:
        linklist.setdefault(a, [])
        linklist.setdefault(b, [])
        linklist[a].append(b)
        linklist[b].append(a)
    return linklist


def calc_longest_distance(linklist, v=1):
    distance_list = {}
    distance_count = 0
    distance = 0
    vlist_previous = []
    vlist = [v]
    nodecount = len(linklist)

    while distance_count < nodecount:
        vlist_next = []
        for v in vlist:
            distance_list[v] = distance
            distance_count += 1
            vlist_next.extend(linklist[v])
        distance += 1
        vlist_to_del = vlist_previous
        vlist_previous = vlist
        vlist = list(set(vlist_next) - set(vlist_to_del))

    max_distance = -1
    max_v = None
    for v, distance in distance_list.items():
        if distance > max_distance:
            max_distance = distance
            max_v = v

    return (max_distance, max_v)


def calc_tree_diameter(linklist, v=1):
    _, u = calc_longest_distance(linklist, v)
    distance, _ = calc_longest_distance(linklist, u)
    return distance


class UnionFind:

    def __init__(self, n):
        self.parent = [i for i in range(n)]

    def root(self, i):
        if self.parent[i] == i:
            return i
        self.parent[i] = self.root(self.parent[i])
        return self.parent[i]

    def unite(self, i, j):
        rooti = self.root(i)
        rootj = self.root(j)
        if rooti == rootj:
            return
        if rooti < rootj:
            self.parent[rootj] = rooti
        else:
            self.parent[rooti] = rootj

    def same(self, i, j):
        return self.root(i) == self.root(j)


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


mod = 10**9 + 7


def main():
    n, m, k = intin()

    x_ans = 0
    c = combination(n * m - 2, k - 2) % mod

    for d in range(1, n):
        ans = d
        ans = modmlt(ans, n - d)
        ans = modmlt(ans, m)
        ans = modmlt(ans, m)
        ans = modmlt(ans, c)

        x_ans = (x_ans + ans) % mod

    y_ans = 0

    for d in range(1, m):
        ans = d
        ans = modmlt(ans, m - d)
        ans = modmlt(ans, n)
        ans = modmlt(ans, n)
        ans = modmlt(ans, c)

        y_ans = (y_ans + ans) % mod

    print(modadd(x_ans, y_ans))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
#import numpy as np
from scipy.misc 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: Time Limit Exceeded

Solution code:
###############################################################################

from sys import stdout
from bisect import bisect_left as binl
from copy import copy, deepcopy
from collections import defaultdict
import math


mod = 1


def intin():
    input_tuple = input().split()
    if len(input_tuple) <= 1:
        return int(input_tuple[0])
    return tuple(map(int, input_tuple))


def intina():
    return [int(i) for i in input().split()]


def intinl(count):
    return [intin() for _ in range(count)]


def modadd(x, y):
    global mod
    return (x + y) % mod


def modmlt(x, y):
    global mod
    return (x * y) % mod


def lcm(x, y):
    while y != 0:
        z = x % y
        x = y
        y = z
    return x


def combination(x, y):
    assert(x >= y)

    ret = math.factorial(x)
    ret = ret // math.factorial(x - y)
    ret = ret // math.factorial(y)

    return ret


def get_divisors(x):
    retlist = []
    for i in range(1, int(x**0.5) + 3):
        if x % i == 0:
            retlist.append(i)
            retlist.append(x // i)
    return retlist


def get_factors(x):
    retlist = []
    for i in range(2, int(x**0.5) + 3):
        while x % i == 0:
            retlist.append(i)
            x = x // i
    retlist.append(x)
    return retlist


def make_linklist(xylist):
    linklist = {}
    for a, b in xylist:
        linklist.setdefault(a, [])
        linklist.setdefault(b, [])
        linklist[a].append(b)
        linklist[b].append(a)
    return linklist


def calc_longest_distance(linklist, v=1):
    distance_list = {}
    distance_count = 0
    distance = 0
    vlist_previous = []
    vlist = [v]
    nodecount = len(linklist)

    while distance_count < nodecount:
        vlist_next = []
        for v in vlist:
            distance_list[v] = distance
            distance_count += 1
            vlist_next.extend(linklist[v])
        distance += 1
        vlist_to_del = vlist_previous
        vlist_previous = vlist
        vlist = list(set(vlist_next) - set(vlist_to_del))

    max_distance = -1
    max_v = None
    for v, distance in distance_list.items():
        if distance > max_distance:
            max_distance = distance
            max_v = v

    return (max_distance, max_v)


def calc_tree_diameter(linklist, v=1):
    _, u = calc_longest_distance(linklist, v)
    distance, _ = calc_longest_distance(linklist, u)
    return distance


class UnionFind:

    def __init__(self, n):
        self.parent = [i for i in range(n)]

    def root(self, i):
        if self.parent[i] == i:
            return i
        self.parent[i] = self.root(self.parent[i])
        return self.parent[i]

    def unite(self, i, j):
        rooti = self.root(i)
        rootj = self.root(j)
        if rooti == rootj:
            return
        if rooti < rootj:
            self.parent[rootj] = rooti
        else:
            self.parent[rooti] = rootj

    def same(self, i, j):
        return self.root(i) == self.root(j)


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


mod = 10**9 + 7


def main():
    n, m, k = intin()

    x_ans = 0
    c = combination(n * m - 2, k - 2)

    for d in range(1, n):
        ans = d
        ans *= n - d
        ans *= m
        ans *= m
        ans *= c

        x_ans = (x_ans + ans) % mod

    y_ans = 0

    for d in range(1, m):
        ans = d
        ans *= m - d
        ans *= n
        ans *= n
        ans *= c

        y_ans = (y_ans + ans) % mod

    print(modadd(x_ans, y_ans))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

Solution code:
###############################################################################

from sys import stdout
from bisect import bisect_left as binl
from copy import copy, deepcopy
from collections import defaultdict


mod = 1


def intin():
    input_tuple = input().split()
    if len(input_tuple) <= 1:
        return int(input_tuple[0])
    return tuple(map(int, input_tuple))


def intina():
    return [int(i) for i in input().split()]


def intinl(count):
    return [intin() for _ in range(count)]


def modadd(x, y):
    global mod
    return (x + y) % mod


def modmlt(x, y):
    global mod
    return (x * y) % mod


def lcm(x, y):
    while y != 0:
        z = x % y
        x = y
        y = z
    return x


def combination(x, y):
    assert(x >= y)

    if y > x // 2:
        y = x - y

    ret = 1

    for i in range(0, y):
        j = x - i
        i = i + 1

        ret = ret * j
        ret = ret // i

    return ret


def get_divisors(x):
    retlist = []
    for i in range(1, int(x**0.5) + 3):
        if x % i == 0:
            retlist.append(i)
            retlist.append(x // i)
    return retlist


def get_factors(x):
    retlist = []
    for i in range(2, int(x**0.5) + 3):
        while x % i == 0:
            retlist.append(i)
            x = x // i
    retlist.append(x)
    return retlist


def make_linklist(xylist):
    linklist = {}
    for a, b in xylist:
        linklist.setdefault(a, [])
        linklist.setdefault(b, [])
        linklist[a].append(b)
        linklist[b].append(a)
    return linklist


def calc_longest_distance(linklist, v=1):
    distance_list = {}
    distance_count = 0
    distance = 0
    vlist_previous = []
    vlist = [v]
    nodecount = len(linklist)

    while distance_count < nodecount:
        vlist_next = []
        for v in vlist:
            distance_list[v] = distance
            distance_count += 1
            vlist_next.extend(linklist[v])
        distance += 1
        vlist_to_del = vlist_previous
        vlist_previous = vlist
        vlist = list(set(vlist_next) - set(vlist_to_del))

    max_distance = -1
    max_v = None
    for v, distance in distance_list.items():
        if distance > max_distance:
            max_distance = distance
            max_v = v

    return (max_distance, max_v)


def calc_tree_diameter(linklist, v=1):
    _, u = calc_longest_distance(linklist, v)
    distance, _ = calc_longest_distance(linklist, u)
    return distance


class UnionFind:

    def __init__(self, n):
        self.parent = [i for i in range(n)]

    def root(self, i):
        if self.parent[i] == i:
            return i
        self.parent[i] = self.root(self.parent[i])
        return self.parent[i]

    def unite(self, i, j):
        rooti = self.root(i)
        rootj = self.root(j)
        if rooti == rootj:
            return
        if rooti < rootj:
            self.parent[rootj] = rooti
        else:
            self.parent[rooti] = rootj

    def same(self, i, j):
        return self.root(i) == self.root(j)


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


mod = 10**9 + 7


def main():
    n, m, k = intin()

    x_ans = 0
    c = combination(n * m - 2, k - 2)

    for d in range(1, n):
        ans = d
        ans *= n - d
        ans *= m
        ans *= m
        ans *= c

        x_ans = (x_ans + ans) % mod

    y_ans = 0

    for d in range(1, m):
        ans = d
        ans *= m - d
        ans *= n
        ans *= n
        ans *= c

        y_ans = (y_ans + ans) % mod

    print(modadd(x_ans, y_ans))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
class Combination:

    def __init__(self, n, MOD):
        self.fact = [1]
        for i in range(1, n + 1):
            self.fact.append(self.fact[-1] * i % MOD)
        self.inv_fact = [pow(self.fact[i] ,MOD - 2 ,MOD) for i in range(n + 1)]
        self.MOD = MOD

    def factorial(self, k):
        '''k!を求める'''
        return self.fact[k]

    def inverse_factorial(self, k):
        '''k!の逆元を求める'''
        return self.inv_fact[k]

    def combination(self, k, r):
        '''kCrを求める'''
        return (self.fact[k] * self.inv_fact[k - r] * self.inv_fact[r]) % self.MOD
      
h, w, k = map(int, input().split())
MOD = 10**9 + 7
comb = Combination(h*w, MOD)

kumi = comb.combination(h*w - 2, k - 2)
ans = 0

for i in range(h):
    for j in range(i, h):
        diff_h = abs(i - j)
        ans += diff_h * kumi * w * w
        ans %= MOD

for i in range(w):
    for j in range(i, w):
        diff_w = abs(i - j)
        ans += diff_w * kumi * h * h
        ans %= MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
inpl = lambda: list(map(int,input().split()))
N, M ,K = inpl()
MOD = 10**9+7
factor = 1
# MN-2 C K-2 = MN-2 C MN-K = MN-2 C L
L = min(K-2,M*N-K)
for i in range(M*N-L-1,M*N-1):
    factor *= i
for i in range(1,L+1):
    factor //= i
factor %= MOD
ans = ((M*(N-1)*(N+1) + N*(M-1)*(M+1))*M*N //6 * factor) % MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
N,M,K = map(int,input().split())
pat =(math.factorial(N*M-2) // (math.factorial(K-2)*math.factorial(N*M-K)))%(10**9+7)
ans_x,ans_y = 0,0
for i in range(M):
    ans_x =(ans_x + i*(M-i))%(10**9+7)
for i in range(N):
    ans_y =(ans_y + i*(N-i))%(10**9+7)
ans_x = (ans_x*(N**2))%(10**9+7)
ans_y = (ans_y*(M**2))%(10**9+7)
ans = (ans_x+ans_y)%(10**9+7)
ans = (ans*pat)%(10**9+7)
print(ans)

Submission status: Time Limit Exceeded

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

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

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

print(ans)

Submission status: Time Limit Exceeded

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)

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

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:

"""
xi,xjのペアにおいて、このペアは何通り出てくるか
sum(全通り)sum(i)sum(j){|xi-xj|+|yi-yj|}
和なので、どんな順序でもいい

sum(i)sum(j)sum(全通り){|xi-xj|}
sum(i)sum(j)sum(全通り){|yi-yj|}

あるi,jで固定して、sum(全通り){|xi-xj|}を求めるヤツ
固定したi,jが現れる回数は、

pat = NM-2_C_K-2 こいつはどこでも一緒

pat*sum(i)sum(j){|xi-xj|}を計算する
すべてのi,j(i>j)ペアにおいて、xi,xjの和は
sum(i=1,N){i*(N-i)}
"""
from math import factorial

N,M,K = map(int,input().split())
mod = 10**9+7
fa = 1
num = N*M - 2
# 固定したときの通り数
cut = min(K-2, N*M-K)
# このfor文は少ないほうが良い
for i in range(num,1,-1):
    if num-i == cut:
        break
    fa *= i
pat = fa//factorial(cut)

# print(pat)
# xi-xj
n_x = M**2*((N-1)*N*(N+1))//6
n_y = N**2*((M-1)*M*(M+1))//6
print(pat*(n_x+n_y)%mod)

Submission status: Time Limit Exceeded

Solution code:

"""
xi,xjのペアにおいて、このペアは何通り出てくるか
sum(全通り)sum(i)sum(j){|xi-xj|+|yi-yj|}
和なので、どんな順序でもいい

sum(i)sum(j)sum(全通り){|xi-xj|}
sum(i)sum(j)sum(全通り){|yi-yj|}

あるi,jで固定して、sum(全通り){|xi-xj|}を求めるヤツ
固定したi,jが現れる回数は、

pat = NM-2_C_K-2 こいつはどこでも一緒

pat*sum(i)sum(j){|xi-xj|}を計算する
すべてのi,j(i>j)ペアにおいて、xi,xjの和は
sum(i=1,N){i*(N-i)}
"""
from math import factorial

N,M,K = map(int,input().split())
mod = 10**9+7
fa = 1
num = N*M - 2
# 固定したときの通り数
for i in range(num,1,-1):
    if num-i == K-2:
        break
    fa *= i
pat = fa//factorial(K-2)
# xi-xj
n_x = M**2*((N-1)*N*(N+1))//6
n_y = N**2*((M-1)*M*(M+1))//6
print(pat*(n_x+n_y)%mod)