/ 
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 900 点
問題文
縦の長さが H+1，横の長さが W+1 の長方形の紙が机に置かれています．xy 座標系を，紙の四隅の座標がそれぞれ (0, 0), (W + 1, 0), (0, H + 1), (W + 1, H + 1) となるように定めます．
この紙は，直線 x = 1,2,...,W と直線 y = 1,2,...,H に沿って切ることができます．これらの H + W 本の直線から K 本を選び，それらの直線に沿って何らかの順序で一回ずつ紙を切断していくという長さ K の操作列を考えます．
紙の 1 回の切断のスコアを，その直後の時点で存在する紙の破片の個数とします．操作列のスコアは，K 回すべての切断のスコアの和です．
考えられる全ての長さ K の操作列のスコアの和を計算してください．この値は非常に大きくなることがあるので，10^9 + 7 で割った余りを出力してください．
制約
- 1 \leq H,W \leq 10^7
- 1 \leq K \leq H + W
- H, W, K は整数
入力
入力は以下の形式で標準入力から与えられる．
H W K
出力
スコアの和を 10^9 + 7 で割った余りを出力せよ．
入力例 1
2 1 2
出力例 1
34
直線 x = 1 に沿った切断を x_1，直線 y = 1 に沿った切断を y_1，直線 y = 2 に沿った切断を y_2 と表記します．考えられる 6 通りの操作列とそれぞれのスコアは次の通りです．
- 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
これらの和は 34 です．
入力例 2
30 40 50
出力例 2
616365902
スコアの和を 10^9 + 7 で割った余りを出力することを忘れないでください．
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.