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!

Difficulty: VERY_HARD
Tags: Polynomials and generating functions

Combinatorics

Mathematics

Starter code:

Solutions:
import numpy as np
MOD = 10 ** 9 + 7
M2 = int(np.sqrt(MOD))

def mpow(x, k):
	x = x % MOD
	r = 1
	while k:
		if k & 1:
			r = r * x % MOD
		x = x * x % MOD
		k //= 2
	return r

def minv(x):
	return mpow(x, MOD - 2)
FACT = [1]
for i in range(1, 10 ** 6):
	FACT += [FACT[i - 1] * i % MOD]
FACT = np.array(FACT)
IFACT = minv(FACT)

def choose(n, k):
	return FACT[n] * IFACT[k] % MOD * IFACT[n - k] % MOD

def ifft(x):
	return np.array(np.round(np.real(np.fft.ifft(x))), dtype=np.int64) % MOD
fft = np.fft.fft

def pmult0(a, b):
	lr = len(a) + len(b) - 1
	ret = np.zeros(lr, dtype=np.int64)
	for i in range(len(a)):
		ret[i:i + len(b)] += b * a[i] % MOD
	return ret % MOD

def pmult(a, b):
	lr = len(a) + len(b) - 1
	if lr < 8:
		return pmult0(a, b)
	m = 1
	while m < lr:
		m *= 2
	(a0, a1, b0, b1) = (np.zeros(m), np.zeros(m), np.zeros(m), np.zeros(m))
	a0[:len(a)] = a % M2
	a1[:len(a)] = a // M2
	b0[:len(b)] = b % M2
	b1[:len(b)] = b // M2
	a0 = fft(a0)
	a1 = fft(a1)
	b0 = fft(b0)
	b1 = fft(b1)
	c0 = ifft(a0 * b0)
	c1 = ifft(a0 * b1 + b0 * a1)
	c2 = ifft(a1 * b1)
	ret = np.zeros(lr, dtype=np.int64)
	ret[:] += c0[:lr]
	ret[:] += c1[:lr] * (M2 % MOD) % MOD
	ret[:] += c2[:lr] * (M2 * M2 % MOD) % MOD
	return ret % MOD

def makeP2(a):
	n = 1
	while n < len(a):
		n *= 2
	if len(a) == n:
		return np.array(a)
	ret = np.zeros(n, dtype=np.int64)
	ret[:len(a)] = a
	return ret

def pinv(a):
	a = makeP2(a)
	n = len(a)
	if n == 1:
		return np.array([minv(a[0])], dtype=np.int64)
	(x, y) = (a[:n // 2], a[n // 2:])
	xi = pinv(x)
	ret = np.zeros(n, dtype=np.int64)
	ret[:len(xi)] = xi * 2
	y = pmult(pmult(xi, xi), a)[:n]
	ret[:len(y)] -= y
	return ret % MOD

def pdiv(a, b):
	return pmult(a, pinv(b))

def expgen(n, k=1):
	ret = np.zeros(n, dtype=np.int64)
	ret[0] = 1
	for i in range(1, n):
		ret[i] = ret[i - 1] * k % MOD
	return ret * IFACT[:n] % MOD
EEE = expgen(2 * 10 ** 5 + 3, -1)
BERNG = pinv(EEE[1:])

def sgen(n, k):
	a = MOD - expgen(n + 1, k)
	ret = pmult(a[1:], BERNG[:n])
	return ret

def extractVar(x, n):
	m = len(x)
	i = np.arange(n, m)
	ret = choose(i, n) * x[i] % MOD
	return ret

def solve(n, m, k):
	ss = sgen(n + m + 1, k) % MOD
	ret = (ss[n + m] * 2 * FACT[n + m] % MOD - mpow(k, n + m)) % MOD
	dd = FACT[n] * FACT[m] % MOD
	s0 = extractVar(ss, n)
	ret -= np.sum(EEE[m::-1] * s0[:m + 1] % MOD) % MOD * dd % MOD
	s0 = extractVar(ss, m)
	ret -= np.sum(EEE[n::-1] * s0[:n + 1] % MOD) % MOD * dd % MOD
	return ret % MOD
import sys
f = sys.stdin
t = int(f.readline())
for i in range(t):
	(a, b, k) = map(int, f.readline().split())
	print(solve(a, b, k))