L. Perimeter
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

There is a $$$n \times m$$$ grid of white cells. The following operation will be performed exactly $$$k$$$ times:

  • Select a cell from the $$$n \times m$$$ cells uniformly at random. If the cell is white, color it black; otherwise, do nothing.

Find the expected sum of the perimeters of all black connected components after all operations.

Formally, let $$$M = 10^9+7$$$. It can be shown that the exact answer can be expressed as an irreducible fraction $$$\frac{p}{q}$$$, where $$$p$$$ and $$$q$$$ are integers and $$$q \not \equiv 0 \pmod{M}$$$. Output the integer equal to $$$p \cdot q^{-1} \bmod M$$$. In other words, output such an integer $$$x$$$ that $$$0 \le x \lt M$$$ and $$$x \cdot q \equiv p \pmod{M}$$$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^5$$$). The description of the test cases follows.

The only line in each test case contains three integers $$$n$$$, $$$m$$$, and $$$k$$$ ($$$1 \le n,m \le 10^9, 1 \le k \le 10^{18}$$$).

Output

For each test case, output the expected sum of the perimeters of all black connected components after all operations.

Example
Input
5
1 2 2
2 2 2
4 4 10
11 45 14
114 514 1919810
Output
5
6
3724697
842233769
187309680