Two Squares

시간 제한2초메모리 제한1024 MB

요약

n×m 격자에 빨간 k×k 정사각형과 파란 k×k 정사각형을 겹치지 않게 놓는 순서 있는 경우의 수를 10^9+7로 나눈 나머지로 구한다.

난이도: 보통10점 중 5점
유형: 수학, 조합론, 구현
정답자: 아직 제출이 없습니다

문제

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:

예제1

예제 1

입력

6
1 2 1
4 3 3
3 4 2
10 10 3
13 9 4
1000000000 1000000000 12345678

예상 출력