题目描述

有一张纵向长度为 $H+1$、横向长度为 $W+1$ 的长方形纸张放在桌子上。我们定义 $xy$ 坐标系，使得纸张的四个角的坐标分别为 $(0, 0)$、$(W+1, 0)$、$(0, H+1)$、$(W+1, H+1)$。

这张纸可以沿着直线 $x=1,2,\ldots,W$ 和直线 $y=1,2,\ldots,H$ 进行切割。从这 $H+W$ 条直线中选择 $K$ 条，按照某种顺序依次沿这些直线切割纸张，形成一个长度为 $K$ 的操作序列。

每次切割的得分定义为切割后此时存在的纸片数量。操作序列的得分为 $K$ 次切割得分的总和。

请计算所有可能的长度为 $K$ 的操作序列的得分之和。由于答案可能非常大，请输出其对 $10^9+7$ 取模的结果。

输入格式

输入通过标准输入按以下格式给出。

$H$ $W$ $K$

输出格式

请输出所有可能的操作序列得分之和对 $10^9+7$ 取模的结果。

输入输出样例 #1

输入 #1

2 1 2

输出 #1

34

输入输出样例 #2

输入 #2

30 40 50

输出 #2

616365902

说明/提示

限制条件

• $1 \leq H, W \leq 10^7$
• $1 \leq K \leq H+W$
• $H, W, K$ 均为整数

样例解释 1

将沿直线 $x=1$ 的切割记为 $x_1$，沿直线 $y=1$ 的切割记为 $y_1$，沿直线 $y=2$ 的切割记为 $y_2$。所有 $6$ 种可能的操作序列及其得分如下：

• $y_1, y_2$：$2+3=5$
• $y_2, y_1$：$2+3=5$
• $y_1, x_1$：$2+4=6$
• $y_2, x_1$：$2+4=6$
• $x_1, y_1$：$2+4=6$
• $x_1, y_2$：$2+4=6$

这些得分的总和为 $34$。

样例解释 2

不要忘记输出得分之和对 $10^9+7$ 取模的结果。

由 ChatGPT 4.1 翻译