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

There is an $$$n$$$ by $$$m$$$ grid of white squares. You want to place a $$$k$$$ by $$$k$$$ red square and a $$$k$$$ by $$$k$$$ blue square on this grid such that they do not overlap. For example, here is a valid solution for $$$n=6$$$, $$$m=8$$$, $$$k=3$$$:

How many ways are there to do this? Two ways are considered different if at least one square is a different color in each.

Since the answer may be large, output it modulo $$$10^9+7$$$.

Input

The first line of the input contains a single integer $$$t$$$ ($$$1 \le t \le 10^5$$$) — the number of test cases. The description of the test cases follows.

Each test case consists of a single line containing three integers $$$n$$$, $$$m$$$, and $$$k$$$ ($$$1 \le n, m \le 10^9$$$, $$$1 \le k \le \min(n, m)$$$) — the number of rows and columns in the grid, and the side length of the squares, respectively.

Output

For each test case, print a single integer — the number of ways to place both squares in the grid, taken modulo $$$10^9+7$$$.

Example
Input
6
1 2 1
4 3 3
3 4 2
10 10 3
13 9 4
1000000000 1000000000 12345678
Output
2
0
8
2940
1860
547313402
Note

The solutions for the first test case are:

In the second test case, there is no way to fit both squares inside the rectangle.

The solutions for the third test case are: