You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Paper Cutting

题目描述

有一个 $(H+1)\times(W+1)$ 的网格，网格中有 $H$ 条水平线和 $W$ 条竖直线。

你需要执行 $K$ 次操作，每次沿一条水平线或竖直线将网格切开。定义一次操作的权值为切割后网格被切分的块数。

定义一个操作序列的权值为$K$次操作的权值和。

求所有操作序列的权值之和，答案对$10^9+7$取模。

输入格式

一行三个整数 $H,W,K$ 。

输出格式

一个整数表示答案。

样例 #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$

样例解释 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$ 。