{"raw_statement":[{"iden":"statement","content":"众所周知， “八皇后” 问题是求解在国际象棋棋盘上摆放 $8$ 个皇后，使得两两之间互不攻击的方案数。已经学习了很多算法的小蓝觉得 “八皇后” 问题太简单了，意犹末尽。作为一个国际象棋迷，他想研究在 $N \\times M$ 的棋盘上，摆放 $K$ 个马，使得两两之间互不攻击有多少种摆放方案。由于方案数可能很大，只需计算答案除以 $1000000007$（即 $10^{9}+7$）的余数。\n\n如下图所示，国际象棋中的马摆放在棋盘的方格内，走 “日” 字, 位于 $(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\n![](https://luogu.oss-cn-hangzhou.aliyuncs.com/upload/vjudge_pic/lanqiao/2022_09_29_68f9131d5c14c1f27e68g-12.jpg)"},{"iden":"input","content":"输入一行包含三个正整数 $N, M, K$, 分别表示棋盘的行数、列数和马的个数。"},{"iden":"output","content":"输出一个整数，表示摆放的方案数除以 $1000000007$（即 $10^{9}+7$）的余数。"},{"iden":"note","content":"对于 $5 \\%$ 的评测用例, $K=1$;\n\n对于另外 $10 \\%$ 的评测用例, $K=2$;\n\n对于另外 $10 \\%$ 的评测用例, $N=1$;\n\n对于另外 $20 \\%$ 的评测用例, $N, M \\leq 6, K \\leq 5$;\n\n对于另外 $25 \\%$ 的评测用例, $N \\leq 3, M \\leq 20 ， K \\leq 12$;\n\n对于所有评测用例, $1 \\leq N \\leq 6,1 \\leq M \\leq 100,1 \\leq K \\leq 20$。 \n\n蓝桥杯 2021 第二轮省赛 A 组 I 题（B 组 J 题）。"}],"translated_statement":null,"sample_group":[["1 2 1","2"],["4 4 3","276"],["3 20 12","914051446"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}