32745번 - Two Squares 다국어

문제

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$.

입력

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.

출력

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

제한

힌트

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: