题目描述

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 mod $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.

我们有一个行数为 $N$ 列数为 $M$ 的正方形网格。让 $(i, j)$ 表示从上往下第 $i$ 行，从左往上第 $j$ 列的方格。我们将选择其中的 $K$ 个方格，并在每个方格上放一颗棋子。

如果我们将 $K$ 颗棋子分别放在 $(x_1, y_1)$ 、 $(x_2, y_2)$ 、......和 $(x_K, y_K)$ 个方格上，那么这种布局的_cost_计算如下：

$\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$ 。

样例 #1

样例输入 #1

2 2 2

样例输出 #1

8

样例 #2

样例输入 #2

4 5 4

样例输出 #2

87210

样例 #3

样例输入 #3

100 100 5000

样例输出 #3

817260251

说明

数据规模与约定

• $2 \leq N \times M \leq 2 \times 10^5$
• $2 \leq K \leq N \times M$
• All values in input are integers.

样例 $1$ 解释

这些乐曲有以下六种可能的排列方式：

• $((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$ 。

样例 $3$ 解释

请务必打印和的模数 $10^9+7$ 。