格点距离总和

题目描述

有一个 $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$ 的余数。

这里，两种棋子布局不同，是指存在一个格子在其中一种布局中放有棋子、而在另一种布局中没有棋子。

输入格式

输入按以下格式从标准输入给出：

$N$ $M$ $K$

输出格式

输出所有棋子布局的花费总和除以 $10^9+7$ 的余数。

样例

2 2 2

8

棋子布局有以下 $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$。

4 5 4

87210

100 100 5000

817260251

注意输出总和除以 $10^9+7$ 的余数。

数据范围

• $2 \le N \times M \le 2 \times 10^5$
• $2 \le K \le N \times M$
• 输入均为整数