Time Limit: 1000ms
Memory Limit: 32768kb
DescriptionGiven a big grid with size n*m. Assuming you have k colors. You can paint a small grid with one color of k. What's more, no same color exists between neighbor small grids (neighbor: one common edge between two girds).
Can you count all the legal painting methods?
InputThe input consists of multiple test cases.
The first line, an integer T (1<=T<=100), indicates the number of the cases. Each test case of the following T lines contains three numbers: n, m, k:
OutputOutput the correct answer % 1000000007 of each case.
2 1 2 2 2 2 3