← 返回题目列表

Codeforces · 128/C

C. 矩形游戏

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

在此任务中,安娜和玛丽亚玩以下游戏。最初,他们有一张方格纸,上面画了一个 n × m 的矩形(只有边框,没有填充)。安娜和玛丽亚轮流移动,安娜开始。在每次移动过程中,应该在最后绘制的矩形内绘制一个新的小矩形(沿着网格线)。新的矩形应该与前一个矩形没有共同点。请注意,当我们绘制矩形时,我们总是只绘制边框,而不会填充矩形。

没有人赢得比赛——安娜和玛丽亚只是玩,直到他们总共完成了 k 步。数一下这个游戏有多少种不同的玩法。

输入

第一行也是唯一一行包含三个整数:n、m、k (1 ≤ n、m、k ≤ 1000)。

输出

打印单个数字 — 玩游戏的方式数。由于该数字可能非常大,因此打印该值模 1000000007 (109 + 7)。

示例

输入 #1

3 3 1

输出 #1

1

输入 #2

4 4 1

输出 #2

9

输入 #3

6 7 2

输出 #3

75

注意

两种游戏方式如果最终画面不同则视为不同。换句话说,如果一种方式包含一个矩形,而另一种方式不包含该矩形。

在第一个示例中,安娜执行了她的第一个也是唯一一个动作,她只有一个可能的行动计划 - 在给定的 3 × 3 正方形内插入一个 1 × 1 正方形。

在第二个示例中,Anna 有多达 9 种变体:4 种绘制 1 × 1 正方形的方法,2 种垂直插入 1 × 2 矩形的方法,另外 2 种水平插入的方法,还有一种方法是插入 2 × 2 正方形。