| [Home|Training|Problems|Contests|C Language] | [Login|Register] |
|
Problems Status Rank |
Problem 1292
Big grid
Time Limit: 1000ms
Memory Limit: 32768kb Description
Given 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? Input
The 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: 1<=n<=2 1<=m<=10000 1<=k<=100 Output
Output the correct answer % 1000000007 of each case.
Sample Input
2 1 2 2 2 2 3 Sample Output
2 18 |