/ 
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 500 点
問題文
N 行 M 列のマス目があり、上から 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.