{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"给定一个矩形棋盘。你需要在该棋盘上画出 **M** 条水平线和 **N** 条垂直线,这样整个棋盘将被分成 **(M+1) x (N+1)** 个格子。因此,将会有 **M+1** 行,每行恰好包含 **N+1** 个格子或列。第 **x\u003csup\u003eth\u003c/sup\u003e** 行的第 **y\u003csup\u003eth\u003c/sup\u003e** 个格子可以被称为 **cell(x, y)**。两个格子之间的距离是它们行差和列差的总和。因此,**cell(x\u003csub\u003e1\u003c/sub\u003e, y\u003csub\u003e1\u003c/sub\u003e)** 和 **cell(x\u003csub\u003e2\u003c/sub\u003e, y\u003csub\u003e2\u003c/sub\u003e)** 之间的距离是 \u003cp class\u003d\"center\"\u003e**|x\u003csub\u003e1\u003c/sub\u003e - x\u003csub\u003e2\u003c/sub\u003e| + |y\u003csub\u003e1\u003c/sub\u003e - y\u003csub\u003e2\u003c/sub\u003e|**\n\n例如,cell (2, 3) 和 cell (3, 2) 之间的距离是 |2 - 3| + |3 - 2| \u003d 1 + 1 \u003d 2。\n\n之后,你需要给棋盘上的每个格子上色。你将获得 **K** 种不同的颜色。为了让棋盘更加美丽,你必须确保没有两个颜色相同的格子之间的距离是奇数。例如,如果你用红色给格子 (3, 5) 上色,你就不能用红色给格子 (5, 8) 上色,因为它们之间的距离是 5,这是奇数。注意,你可以保留一些颜色不用,但不能让某些格子不上色。\n\n你需要确定使用这 **K** 种颜色给棋盘上色的方式有多少种。"}},{"title":"输入","value":{"format":"MD","content":"输入以一个整数 **T (\u0026le; 20000)** 开始,表示测试用例的数量。\n\n每个测试用例以一行包含三个整数 **M, N, K (0 \u0026le; M, N \u0026le; 19, 1 \u0026le; K \u0026le; 50)** 开始。"}},{"title":"输出","value":{"format":"MD","content":"对于每个测试用例,打印出测试用例编号和你可以给棋盘上色的方式数量。结果可能很大,因此以模 **1000000007** 的形式打印结果。"}},{"title":"示例","value":{"format":"MD","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e4\n0 0 1\n0 0 2\n5 5 2\n5 5 1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase 1: 1\nCase 2: 2\nCase 3: 2\nCase 4: 0\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}