分数: 900 点
问题陈述
有一张长方形的纸,高度 H+1 和宽度 W+1。我们介绍一个 xy- 坐标系,使纸张的四个角为 (0, 0), (W + 1, 0), (0, H + 1) 和 (W + 1, H + 1).
这张纸可以沿着线切割 x = 1,2,...,W 和行 y = 1,2,...,H。考虑长度的操作序列 K 我们选择的地方 K 其中 H + W 线并沿着这些线按某种顺序一张一张地切割纸张。
令切割分数为切割后存在的纸张数量。一系列操作的分数是所有操作的分数之和 K 削减。
求所有可能的长度操作序列的分数总和 K。由于该值可能非常大,因此打印数字模 10^9 + 7.
约束
- 1 \leq H,W \leq 10^7
- 1 \leq K \leq H + W
- H, W 和 K 是整数。
输入
输入由标准输入按以下格式给出:
H W K
输出
打印分数的总和,取模 10^9 + 7.
示例输入 1
2 1 2
示例输出 1
34
让 x_1, y_1 和 y_2 表示沿线切割 分别为 x = 1, y = 1 和 y = 2。六种可能的操作序列以及每种操作的得分如下:
- 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
30 40 50
示例输出 2
616365902
请务必打印模数总和 10^9 + 7.