众所周知，“八皇后” 问题是求解在国际象棋棋盘上摆放 $8$ 个皇后，使得两两之间互不攻击的方案数。

已经学习了很多算法的小蓝觉得 “八皇后” 问题太简单了，意犹未尽。作为一个国际象棋迷，他想研究在 $N \times M$ 的棋盘上，摆放 $K$ 个马，使得两两之间互不攻击有多少种摆放方案。

由于方案数可能很大，只需计算答案除以 $1000000007$ (即 $10^9 + 7$) 的余数。

如下图所示，国际象棋中的马摆放在棋盘的方格内，走 “日” 字，位于 $(x, y)$ 格的马（第 $x$ 行第 $y$ 列）可以攻击 $(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)$ 共 $8$ 个格子。

输入格式

输入一行包含三个正整数 $N, M, K$，分别表示棋盘的行数、列数和马的个数。

输出格式

输出一个整数，表示摆放的方案数除以 $1000000007$ (即 $10^9 + 7$) 的余数。

数据范围

对于 $5\%$ 的评测用例，$K = 1$；
对于另外 $10\%$ 的评测用例，$K = 2$；
对于另外 $10\%$ 的评测用例，$N = 1$；
对于另外 $20\%$ 的评测用例，$N, M ≤ 6，K ≤ 5$；
对于另外 $25\%$ 的评测用例，$N ≤ 3，M ≤ 20，K ≤ 12$；
对于所有评测用例，$1 ≤ N ≤ 6，1 ≤ M ≤ 100，1 ≤ K ≤ 20$。

输入样例1：

1 2 1

输出样例1：

2

输入样例2：

4 4 3

输出样例2：

276

输入样例3：

3 20 12

输出样例3：

914051446