Kings on a Chessboard

You have a chessboard with $x$ rows and $y$ columns, and $k$ identical kings. Place all $k$ kings on the board so that no two of them attack each other. Two kings attack each other when they stand on adjacent squares horizontally, vertically, or diagonally. A square holds at most one king.

Write a program that counts the arrangements of the $k$ kings. The count can be very large, so report it modulo 1,000,000,007.

The first line contains the number of test cases $T$. Each of the next $T$ lines contains three integers $x$, $y$, and $k$ separated by one space.

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

For each test case, print the number of arrangements modulo 1,000,000,007 on its own line, in the order the test cases are given.