Problem Description

As everyone knows, the “Eight Queens” problem asks for the number of ways to place $8$ queens on a chessboard so that no two queens attack each other. Xiao Lan, who has learned many algorithms, thinks the “Eight Queens” problem is too easy and still wants more. As a chess fan, he wants to study the following: on an $N \times M$ board, how many ways are there to place $K$ knights so that no two knights attack each other. Since the number of ways can be very large, you only need to compute the answer modulo $1000000007$ (i.e., $10^{9}+7$).

As shown in the figure below, a knight in chess is placed inside a square and moves in an “L” shape. A knight located at square $(x, y)$ (row $x$, column $y$) can attack the $8$ squares $(x+1, y+2)$, $(x+1, y-2)$, $(x-1, y+2)$, $(x-1, y-2)$, $(x+2, y+1)$, $(x+2, y-1)$, $(x-2, y+1)$, $(x-2, y-1)$.

Input Format

Input one line containing three positive integers $N$, $M$, and $K$, representing the number of rows, the number of columns, and the number of knights.

Output Format

Output one integer, representing the number of valid placements modulo $1000000007$ (i.e., $10^{9}+7$).

1 2 1

2

4 4 3

276

3 20 12

914051446

Hint

For $5\%$ of the testdata, $K=1$.

For another $10\%$ of the testdata, $K=2$.

For another $10\%$ of the testdata, $N=1$.

For another $20\%$ of the testdata, $N, M \leq 6$, $K \leq 5$.

For another $25\%$ of the testdata, $N \leq 3$, $M \leq 20$, $K \leq 12$.

For all testdata, $1 \leq N \leq 6$, $1 \leq M \leq 100$, $1 \leq K \leq 20$.

Lanqiao Cup 2021 Second Round Provincial Contest, Group A Problem I (Group B Problem J).

Translated by ChatGPT 5