题目描述

我们有一个 $N$ 行 $M$ 列的方格网格。用$(i,j)$表示方格网格中第之行从上到下、第j列从左到右的方格。我们将选择 $K$个方格，并在每个方格上放置一个物品。

如果我们将 $K$ 个物品放置在方格$(x_1,y_1),(x_2,y_2),… and(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$取模之后的结果。

如果两种物品的安排仅当且仅当有一个方格在一种安排中包含一个物品，而在另一种安排中不包含物品时，我们认为这两种安排是不同的。

输入

输入一行三个整数$N,M,K$

输出

输出所有可能安排的物品的花费之和，对$10^9+7$取模。

2 2 2

8

有六种可能的物品安排，如下： ((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.

4 5 4

87210

100 100 5000

817260251

提示

$2 \leq N \times M \leq 2 \times 10^5$

$2 \leq K \leq N \times M$