第三届“恒生杯”程序设计大赛初赛 DAY1

From: 2012-10-27 09:00:00 To: 2012-10-27 13:00:00 Now: 2017-09-20 00:57:08 Status: Public

H - 方块游戏

Time Limit: 1s Memory Limit: 128MB

Submissions: 42 Solved: 21
Description
BG和ZZ一起玩一个游戏,游戏规则如下:
       游戏开始时画在一张纸上,纸上画有n*m个方块组成的格子,BG和ZZ轮流玩这个游戏,BG先开始。每一轮玩家都会在上一次的方框内框出一个小方框作为下一轮的方框,这个小方框的边和原先的方框的边不能够有交集。
       这个游戏没有赢家,BG和ZZ只是不断的缩小方框,直到游戏进行k轮。现求游戏有多少种方法。(即游戏从初始状态到进行k轮后的任意状态的路径数目)。
Input
输入包括多组数据,每组数据为一行,每行有3个整数n,m,k(其中1 ≤ n, m, k ≤ 1000)。
Output
每组数据输出一行,每行为一个整数ans,表示游戏的方法数量,由于数量可能很大,请输出答案对1000000007求余的结果。
Sample Input
3 3 1
4 4 1
6 7 2
Sample Output
1
9
75
Hint
Source