Non-attacking Knights Placement

In this problem, you are given a chessboard of size (N \times M) and an integer (K). The task is to place (K) knights on the board such that no two knights attack each other. A knight placed at cell ((x, y)) can attack any cell at ((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)), or ((x-2, y-1)) if that cell is within the board.

You need to calculate the number of valid arrangements modulo (10^9+7).

inputFormat

The input consists of a single line with three space-separated integers: (N), (M), and (K), representing the number of rows, the number of columns, and the number of knights to place, respectively.

outputFormat

Output a single integer which is the number of valid placements of (K) knights on the board, modulo (10^9+7).

sample

1 1 1

1