[Login|Register]
Problems

Status

Rank

Problem 1300
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
University of Science and Technology of China
Online Judge for ACM/ICPC
Processed in 1.4ms with 1 query(s).