E - 网格距离

分数：500 分

问题描述

我们有一个 $N$ 行 $M$ 列的方格网格。用$(i, j)$表示方格网格中第 $i$ 行从上到下、第 $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$ 取模之后的结果。

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

约束条件

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

输出：

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

示例 2

输入：

4 5 4

输出：

87210

示例 3

输入：

100 100 5000

输出：

817260251

确保输出结果对 $10^9+7$ 求模。