E - Cell Distance

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500

問題文

NM 列のマス目があり、上から i 行目、左から j 列目のマスを (i, j) で表します。

このうち K マスに駒を 1 つずつ置きます。

K 個の駒がそれぞれ (x_1, y_1), (x_2, y_2), ..., (x_K, y_K) に置かれているとき、この配置のコストは

\sum_{i=1}^{K-1} \sum_{j=i+1}^K (|x_i - x_j| + |y_i - y_j|)

と計算されます。

駒の全ての配置のコストの総和を計算してください。この値は非常に大きくなることがあるので、10^9+7 で割った余りを出力してください。

ただし、2 つの駒の配置が異なるとは、片方の配置では駒があるがもう一方では駒が無いようなマスが存在する場合を表します。

制約

  • 2 \leq N \times M \leq 2 \times 10^5
  • 2 \leq K \leq N \times M
  • 入力は全て整数である

入力

入力は以下の形式で標準入力から与えられる。

N M K

出力

駒の全ての配置のコストの総和を 10^9+7 で割った余りを出力せよ。


入力例 1

2 2 2

出力例 1

8

駒の配置としては、以下の 6 通りが考えられます。

  • ((1,1),(1,2)), コストは |1-1|+|1-2| = 1
  • ((1,1),(2,1)), コストは |1-2|+|1-1| = 1
  • ((1,1),(2,2)), コストは |1-2|+|1-2| = 2
  • ((1,2),(2,1)), コストは |1-2|+|2-1| = 2
  • ((1,2),(2,2)), コストは |1-2|+|2-2| = 1
  • ((2,1),(2,2)), コストは |2-2|+|1-2| = 1

これらの総和は 8 です。


入力例 2

4 5 4

出力例 2

87210

入力例 3

100 100 5000

出力例 3

817260251

総和を 10^9+7 で割った余りを出力することに注意してください。

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.