Migrated from Lutece 716 Kings on a Chessboard

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

You are given a chessboard of size $x \times y$ and $k$ identical kings, and are asked to place all the kings on the board such that no two kings can attack each other. Two kings can attack each other if they are horizontally, vertically or diagonally adjacent.

Write a computer program that calculates the number of possible arrangements of the $k$ kings on the given chessboard. Since the number of feasible arrangements may be large, reduce the number modulo $1,000,000,007$.

Input

The first line of the input consists of a single integer $T$, the number of test cases. Each of the following $T$ lines consists of 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$

Output

For each test case, output the number of possibilities modulo $1,000,000,007$.

Samples

4
8 8 1
7 7 16
7 7 7
3 7 15

64
1
2484382
0

Resources

IDI Open 2013 Programming Contest