题目描述

众所周知， “八皇后” 问题是求解在国际象棋棋盘上摆放 $8$ 个皇后，使得两两之间互不攻击的方案数。已经学习了很多算法的小蓝觉得 “八皇后” 问题太简单了，意犹末尽。作为一个国际象棋迷，他想研究在 $N \times M$ 的棋盘上，摆放 $K$ 个马，使得两两之间互不攻击有多少种摆放方案。由于方案数可能很大，只需计算答案除以 $1000000007$ (即 $\left.10^{9}+7\right)$ 的余数。

如下图所示，国际象棋中的马摆放在棋盘的方格内，走 “日” 字, 位于 $(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\left(\right.$ 即 $\left.10^{9}+7\right)$ 的余数。

1 2 1

2

4 4 3

276

3 20 12

914051446

提示

对于 $5 \%$ 的评测用例, $K=1$;

对于另外 $10 \%$ 的评测用例, $K=2$;

对于另外 $10 \%$ 的评测用例, $N=1$;

对于另外 $20 \%$ 的评测用例, $N, M \leq 6, K \leq 5$;

对于另外 $25 \%$ 的评测用例, $N \leq 3, M \leq 20 ， K \leq 12$;

对于所有评测用例, $1 \leq N \leq 6,1 \leq M \leq 100,1 \leq K \leq 20$。

蓝桥杯 2021 第二轮省赛 A 组 I 题（B 组 J 题）。