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.

Input Format

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 Format

Output T lines, one for each test case containing the number of ways modulo 10^{9}+7.

Constraints

1 <= T <= 10^{5}

1 <= N,M <= 8

1 <= K <= 10^{9}

Sample Input

3
3 3 2
3 4 3
1 1 1

Sample Output

2
1122
1

Explanation

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
Timelimits for this challenge can be seen here

见题面

见题面