[ABC127E] Cell Distance
题意翻译
### 题目描述
有一个 $n \times m$ 的矩形,你会从中选出 $k$ 个坐标为整数的位置 $(x_1,y_1),(x_2,y_2)\dots(x_{k},y_{k})$ 。
你定义一个选出 $k$ 个位置的方案的权值为$\textstyle \sum_{i=1}^{k-1}\sum_{j=i+1}^{k}(|x_{i}-x_{j}|+|y_{i}-y_{j}|)$
你需要求出,所有可能的选出 $k$ 个位置的方案的权值之和,答案对 $1000000007$ 取模
### 输入格式
一行三个整数 $n,m,k$
### 输出格式
一行一个整数,表示答案
### 数据范围与提示
$2 \le k \le n \times m \le 200000$
题目描述
[problemUrl]: https://atcoder.jp/contests/abc127/tasks/abc127_e
$ 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 $ つの駒の配置が異なるとは、片方の配置では駒があるがもう一方では駒が無いようなマスが存在する場合を表します。
输入输出格式
输入格式
入力は以下の形式で標準入力から与えられる。
> $ N $ $ M $ $ K $
输出格式
駒の全ての配置のコストの総和を $ 10^9+7 $ で割った余りを出力せよ。
输入输出样例
输入样例 #1
2 2 2
输出样例 #1
8
输入样例 #2
4 5 4
输出样例 #2
87210
输入样例 #3
100 100 5000
输出样例 #3
817260251
说明
### 制約
- $ 2\ \leq\ N\ \times\ M\ \leq\ 2\ \times\ 10^5 $
- $ 2\ \leq\ K\ \leq\ N\ \times\ M $
- 入力は全て整数である
### Sample Explanation 1
駒の配置としては、以下の $ 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 $ です。
### Sample Explanation 3
総和を $ 10^9+7 $ で割った余りを出力することに注意してください。