Calculate the number of ways to color an N * M grid using K colors. Adjacent squares in the grid should have different colors. Squares are considered adjacent if they share an edge.
The first line contains an integer T denoting the number of test-cases.
The next T lines contains integers N, M and K separated by a single space.
Output T lines, one for each test case containing the number of ways modulo 109+7.
1 <= T <= 105
1 <= N,M <= 8
1 <= K <= 109
3 3 2
3 4 3
1 1 1
For the first case, there are two ways to color the grid. The colorings are in a chessboard pattern with either color at the top right square.
Timelimits for this challenge can be seen here