Problem Description

As is well known, the "Eight Queens" problem involves placing 8 queens on a chessboard such that no two queens can attack each other. Having learned many algorithms, Xiao Lan finds the "Eight Queens" problem too simple and feels unsatisfied. As a chess enthusiast, he wants to study how many ways there are to place K knights on an N × M chessboard such that no two knights can attack each other. Since the number of solutions might be very large, you only need to calculate the answer modulo \(10^9 + 7\).

As shown in the figure below, a knight in chess is placed within a square on the board and moves in an "L" shape. A knight located at \((x, y)\) (in the x-th row and y-th column) can attack 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

A line containing three positive integers \(N\), \(M\), and \(K\), representing the number of rows, columns, and knights, respectively.

Output Format

Output a single integer, which is the number of ways to place the knights modulo \(10^9 + 7\).

Sample Input and Output

Sample Input #1

1 2 1

Sample Output #1

2

Sample Input #2

4 4 3

Sample Output #2

276

Sample Input #3

3 20 12

Sample Output #3

914051446

Notes

For 5% of the test cases, \(K = 1\);

For another 10% of the test cases, \(K = 2\);

For another 10% of the test cases, \(N = 1\);

For another 20% of the test cases, \(N, M \leq 6, K \leq 5\);

For another 25% of the test cases, \(N \leq 3, M \leq 20, K \leq 12\);

For all test cases, \(1 \leq N \leq 6, 1 \leq M \leq 100, 1 \leq K \leq 20\).

This problem is from the Lanqiao Cup 2021 Second Round of the Provincial Competition, Group A, Problem I (Group B, Problem J).

见题面 Input 部分

见题面 Output 部分