题目描述

问题陈述

我们有一个大小为 $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$ 取模后输出。

当且仅当一个放置方式中存在一个方格包含一个棋子而另一个放置方式中不包含该棋子时，我们认为这两种放置方式是不同的。

约束条件

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

有六种可能的放置方式，如下所示：

• $((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$ 取模后输出。