11163번 - Kings on a Chessboard 다국어

You are given a chessboard of size x × 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.

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 ≤ 50
• 2 ≤ x, y ≤ 15
• 1 ≤ k ≤ x · y

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