{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"You are given a rectangular board. You are asked to draw **M** horizontal lines and **N** vertical lines in that board, so that the whole board will be divided into **(M+1) x (N+1)** cells. So, there will be **M+1** rows each of which will exactly contain **N+1** cells or columns. The **y\u003csup\u003eth\u003c/sup\u003e** cell of **x\u003csup\u003eth\u003c/sup\u003e** row can be called as **cell(x, y)**. The distance between two cells is the summation of row difference and column difference of those two cells. So, the distance between **cell(x\u003csub\u003e1\u003c/sub\u003e, y\u003csub\u003e1\u003c/sub\u003e)** and **cell(x\u003csub\u003e2\u003c/sub\u003e, y\u003csub\u003e2\u003c/sub\u003e)** is \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\nFor example, the distance between cell (2, 3) and cell (3, 2) is |2 - 3| + |3 - 2| \u003d 1 + 1 \u003d 2.\n\nAfter that you have to color every cell of the board. For that you are given **K** different colors. To make the board more beautiful you have to make sure that no two cells having the same color can have odd distance between them. For example, if you color cell (3, 5) with red, you cannot color cell (5, 8) with red, as the distance between them is 5, which is odd. Note that you can keep some color unused, but you can\u0027t keep some cell uncolored.\n\nYou have to determine how many ways to color the board using those **K** colors."}},{"title":"Input","value":{"format":"MD","content":"Input starts with an integer **T (\u0026le; 20000)**, denoting the number of test cases.\n\nEach case starts with a line containing three integers **M, N, K (0 \u0026le; M, N \u0026le; 19, 1 \u0026le; K \u0026le; 50)**."}},{"title":"Output","value":{"format":"MD","content":"For each case, print the case number and the number of ways you can color the board. The result can be large, so print the result modulo **1000000007**."}},{"title":"Sample","value":{"format":"HTML","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\n"}}]}