Read problem statements in [Hindi], [Bengali], [Mandarin Chinese], [Russian], and [Vietnamese] as well.

Consider all matrices with $N$ rows (numbered $1$ through $N$) and $M$ columns (numbered $1$ through $M$) containing only integers between $0$ and $K-1$ (inclusive). For each such matrix $A$, let's form a sequence $L_{1}, L_{2}, \ldots, L_{N+M}$:
For each $i$ ($1 ≤ i ≤ N$), $L_{i}$ is the maximum of all elements in the $i$-th row of $A$.
For each $i$ ($1 ≤ i ≤ M$), $L_{N+i}$ is the maximum of all elements in the $i$-th column of $A$.

Find the number of different sequences formed this way. Since this number may be very large, compute it modulo $10^{9} + 7$.

------ Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first and only line of each test case contains three space-separated integers $N$, $M$ and $K$.

------ Output ------
For each test case, print a single line containing one integer — the number of different sequences, modulo $10^{9} + 7$.

------ Constraints ------
$1 ≤ T ≤ 1,000$
$1 ≤ N ≤ 10^{5}$
$1 ≤ M ≤ 10^{5}$
$1 ≤ K ≤ 10^{9}$
the sum of $N$ over all test cases does not exceed $10^{5}$
the sum of $M$ over all test cases does not exceed $10^{5}$

------ Subtasks ------
Subtask #1 (10 points):
$1 ≤ K ≤ 50$
the sum of $N$ over all test cases does not exceed $50$
the sum of $M$ over all test cases does not exceed $50$

Subtask #2 (20 points):
$1 ≤ K ≤ 10^{5}$
the sum of $N$ over all test cases does not exceed $10^{5}$
the sum of $M$ over all test cases does not exceed $10^{5}$

Subtask #3 (20 points):
$1 ≤ K ≤ 10^{9}$
the sum of $N$ over all test cases does not exceed $200$
the sum of $M$ over all test cases does not exceed $200$

Subtask #4 (20 points):
$K$ is the same for all test cases
$1 ≤ K ≤ 10^{9}$
the sum of $N$ over all test cases does not exceed $10^{5}$
the sum of $M$ over all test cases does not exceed $10^{5}$

Subtask #5 (30 points):
$1 ≤ K ≤ 10^{9}$
the sum of $N$ over all test cases does not exceed $10^{5}$
the sum of $M$ over all test cases does not exceed $10^{5}$

----- Sample Input 1 ------
3

2 2 2

2 3 2

41 42 2
----- Sample Output 1 ------
10

22

903408624
----- explanation 1 ------
Example case 1:
There are $16$ possible matrices, listed below along with the sequences they generate. There are $10$ different sequences among them: $(0, 0, 0, 0)$, $(0, 1, 0, 1)$, $(0, 1, 1, 0)$, $(1, 0, 0, 1)$, $(1, 0, 1, 0)$, $(1, 1, 1, 0)$, $(1, 0, 1, 1)$, $(0, 1, 1, 1)$, $(1, 1, 0, 1)$ and $(1, 1, 1, 1)$.

[0, 0]
[0, 0] = (0, 0, 0, 0)

[0, 0]
[0, 1] = (0, 1, 0, 1)

[0, 0]
[1, 0] = (0, 1, 1, 0)

[0, 1]
[0, 0] = (1, 0, 0, 1)

[1, 0]
[0, 0] = (1, 0, 1, 0)

[1, 0]
[1, 0] = (1, 1, 1, 0)

[1, 1]
[0, 0] = (1, 0, 1, 1)

[0, 0]
[1, 1] = (0, 1, 1, 1)

[0, 1]
[0, 1] = (1, 1, 0, 1)

[1, 0]
[0, 1] = (1, 1, 1, 1)

[0, 1]
[1, 0] = (1, 1, 1, 1)

[1, 1]
[1, 0] = (1, 1, 1, 1)

[1, 1]
[0, 1] = (1, 1, 1, 1)

[1, 1]
[0, 1] = (1, 1, 1, 1)

[1, 0]
[1, 1] = (1, 1, 1, 1)

[1, 1]
[1, 1] = (1, 1, 1, 1)

Example case 2:
There are $22$ different sequences. One of them is $(1, 1, 0, 1, 1)$, generated e.g. by the matrix

[0, 1, 0]
[0, 0, 1]

Example case 3: Don't forget about modulo!

见题面

见题面