AT_keyence2019_f Paper Cutting

有一张纵向长度为 $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 \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 翻译