← 返回题目列表

AtCoder · keyence2019_f

F. 剪纸

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

分数: 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.