Kings Again

Last year's problem with kings was too easy, so I made it more difficult. Determine the number of ways in which k kings can be placed on an n × m chessboard without attacking each other. Two kings attack each other if they are on adjacent cells horizontally, vertically, or diagonally.

Input Specification

The first line of the input contains t, the number of test cases to follow (1 ≤ t ≤ 15 000). Each test case is described by the values of n, m, and k, in this order, separated by spaces (1 ≤ n ≤ m ≤ 15, 1 ≤ k ≤ 100).

Output Specification

For each test case, you must output a single line, the number of ways modulo 10⁹ + 7.

Sample Input

1. 3
2. 1 4 2
3. 3 3 4
4. 4 4 4

download as text file

Output for Sample Input

1. 3
2. 1
3. 79

download as text file