두 정사각형

$n$행 $m$열로 이루어진 흰색 칸의 격자가 있다. 이 격자에 한 변의 길이가 $k$인 빨간색 정사각형 하나와 한 변의 길이가 $k$인 파란색 정사각형 하나를 서로 겹치지 않게 놓으려 한다. 예를 들어 $n=6$, $m=8$, $k=3$인 경우 아래 그림처럼 놓을 수 있다.

이렇게 두 정사각형을 놓는 방법은 몇 가지인가? 두 방법은 적어도 한 칸의 색이 다르면 서로 다른 방법으로 본다.

답이 클 수 있으므로 $10^9+7$로 나눈 나머지를 출력한다.

첫째 줄에 테스트 케이스의 개수 $t$ ($1 \le t \le 10^5$)가 주어진다.

각 테스트 케이스는 한 줄로 이루어져 있으며, 격자의 행 수 $n$, 열 수 $m$, 정사각형의 한 변의 길이 $k$가 공백으로 구분되어 주어진다 ($1 \le n, m \le 10^9$, $1 \le k \le \min(n, m)$).

각 테스트 케이스마다 두 정사각형을 격자에 놓는 방법의 수를 $10^9+7$로 나눈 나머지를 한 줄에 출력한다.

첫 번째 테스트 케이스의 놓는 방법은 다음과 같다.

두 번째 테스트 케이스에서는 두 정사각형을 직사각형 안에 모두 넣을 방법이 없다.

세 번째 테스트 케이스의 놓는 방법은 다음과 같다.