George has a beautiful grid of w columns and h rows. He plans to color each cell of the grid using one of k different available colors. There are some rules he plans
to follow:
* The top-most row must contain at least one cell of each of the k colors.<br>
* Every pair of cells of the same color must be connected. Two cells are connected if there is a path between them that consists of cells that share a common edge and are of the same color.<p>
Find the number of different valid ways to color the top-most row. Two ways to color the top-most row are different if and only if at least one of the cells in the top-most row has a different color. For each different coloring of the top-most row, there may be many valid ways to color the rest of the grid, but we will only count that coloring exactly once. Since the result may be very big, return the number of ways modulo 1000000007.
The first line contain an integer T, denoting the number of testcases.
Each testcase contain three number w,h,k separated by exact one space in a line.
For each testcase, you have print a line contain the answer.
T<=20
1 <= w, h, k <= 300
2 4 1 2 4 3 2
6 12
Migrated from old NTUJ.
TCO 11
| No. | Testdata Range | Score |
|---|