Problem:


Score : 900 points

Problem Statement

There is a rectangular sheet of paper with height H+1 and width W+1. We introduce an xy-coordinate system so that the four corners of the sheet are (0, 0), (W + 1, 0), (0, H + 1) and (W + 1, H + 1).

This sheet can be cut along the lines x = 1,2,...,W and the lines y = 1,2,...,H. Consider a sequence of operations of length K where we choose K of these H + W lines and cut the sheet along those lines one by one in some order.

Let the score of a cut be the number of pieces of paper that exist just after the cut. The score of a sequence of operations is the sum of the scores of all of the K cuts.

Find the sum of the scores of all possible sequences of operations of length K. Since this value can be extremely large, print the number modulo 10^9 + 7.

Constraints

1 \leq H,W \leq 10^7

1 \leq K \leq H + W

H, W and K are integers.

Input

Input is given from Standard Input in the following format:

H W K

Output

Print the sum of the scores, modulo 10^9 + 7.

Sample Input 1

2 1 2

Sample Output 1

34

Let x_1, y_1 and y_2 denote the cuts along the lines x = 1, y = 1 and y = 2, respectively. The six possible sequences of operations and the score of each of them are as follows:

y_1, y_2: 2 + 3 = 5

y_2, y_1: 2 + 3 = 5

y_1, x_1: 2 + 4 = 6

y_2, x_1: 2 + 4 = 6

x_1, y_1: 2 + 4 = 6

x_1, y_2: 2 + 4 = 6

The sum of these is 34.

Sample Input 2

30 40 50

Sample Output 2

616365902

Be sure to print the sum modulo 10^9 + 7.



Sample input:
2 1 2


Sample output:
34

Submission status: Runtime Error

Solution code:
import sys
from itertools import permutations 
# import numpy as np

def calc(H,W,K):
    s = 0
    all_ele = [0] * H + [1] * W
    for perm in permutations(all_ele,K):
        s += each_calc(perm)
    return s

def each_calc(perm):
    s = 0
    nx = 1
    ny = 1
    for e in perm:
        if e==0:
            nx += 1
            s += nx*ny
            
        else:
            ny += 1
            s += ny*nx
    print(perm,s)
    
    return s
  
if __name__ == '__main__':
    H,W,K = sys.args[1:]

Submission status: Runtime Error

Solution code:
from math import factorial

mod = 10 ** 9 + 7
h, w, k = map(int, input().split())
s = h+w
p = factorial(s) // factorial(s-k)
a = 0
b = 0
for x in range(1,k+1):
  a += (k+1-x)
  b += (x-1)*(k+1-x)

e = k%mod + a%mod + ((b*h*w*2)/(s*(s-1)))%mod

print(int((e%mod*p%mod)%mod))

Submission status: Runtime Error

Solution code:
from math import factorial

mod = 10 ** 9 + 7
h, w, k = map(int, input().split())
s = h+w
p = factorial(s) // factorial(s-k)
a = 0
b = 0
for x in range(1,k+1):
  a += (k+1-x)
  b += (x-1)*(k+1-x)

e = k + a + ((b*h*w*2)/(s*(s-1)))

print(int((e*p)%mod))

Submission status: Runtime Error

Solution code:
import itertools
from scipy.special import comb
comb(4, 3, exact=True)

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


def calc(S_xy):
    x, y = 1, 1
    r = 0
    for S in S_xy:
        if S == 'x':
            x += 1
        else:
            y += 1
        r += x * y
    return r


pattern_xy = [['x'] * x + ['y'] * y  for y in range(H+1) for x in range(W+1) if x + y == K]

R = 0

for xy in pattern_xy:
    count_x = xy.count('x')
    count_y = K - count_x
    R += comb(W, count_x, exact=True) * comb(H, count_y, exact=True) * sum([calc(''.join(iter_xy)) for iter_xy in itertools.permutations(xy)])

print(R)

# NEED DP? no time...