← 返回题目列表

AtCoder · abc127_e

E. 细胞距离

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

我们有一个正方形网格 N 行和 M 列。让 (i, j) 表示位于 i从顶部开始的第行和 j左起第 列。我们会选择 K 的方块并在每个方块上放一块。

如果我们将 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.

当且仅当有一个正方形包含其中一种排列中的棋子但不包含另一种排列中的棋子时,我们才认为棋子的两种排列不同。

约束

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