체스판 위의 킹

$x$행 $y$열짜리 체스판과 서로 구분되지 않는 킹 $k$개가 있다. 킹 $k$개를 모두 체스판에 올려놓되, 어떤 두 킹도 서로를 공격하지 못하도록 놓아야 한다. 두 킹은 가로, 세로, 대각선 중 어느 방향으로든 맞닿은 칸에 있으면 서로를 공격한다. 한 칸에는 킹을 최대 하나만 놓을 수 있다.

킹 $k$개를 놓는 방법의 수를 구하는 프로그램을 작성하시오. 그 수가 매우 커질 수 있으므로 1,000,000,007로 나눈 나머지를 구한다.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 이어지는 $T$개의 줄에는 각각 세 정수 $x$, $y$, $k$가 공백 하나를 사이에 두고 주어진다.

• $0 < T \le 50$
• $2 \le x, y \le 15$
• $1 \le k \le x \times y$

각 테스트 케이스마다 킹 $k$개를 놓는 방법의 수를 1,000,000,007로 나눈 나머지를 입력 순서대로 한 줄에 하나씩 출력한다.