Cell Distance

题目描述

我们有一个由 $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$ 取模后的结果。 我们仅当且仅当存在某个格子在一个排列中有棋子而在另一个排列中没有棋子时，才认为这两个排列不同。

输入格式

输入自标准输入，格式如下： $N$ $M$ $K$

输出格式

输出所有可能排列的代价之和，对 $10^9+7$ 取模。

2 2 2

8

4 5 4

87210

100 100 5000

817260251

提示

$2 \leq N \times M \leq 2 \times 10^5$ $2 \leq K \leq N \times M$ 输入中的所有数值均为整数。共有六种可能的棋子放置方案，如下所示：

$((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$。
注意输出对 $10^9+7$ 取模的结果。

标签: AtCoder|abc127E

来源

AtCoder|abc127E