该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

经典的"八皇后"问题研究的是在国际象棋棋盘上放置8个互不攻击的皇后。本题将其扩展为在N×M的棋盘上放置K个互不攻击的马的问题。

问题描述

给定一个N行M列的棋盘，计算放置K个马且它们互不攻击的方案数。由于结果可能很大，请输出答案对10^9+7取模的结果。

马的攻击范围

位于坐标(x,y)的马可以攻击以下8个位置：

• (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)

输入格式

输入包含三个用空格分隔的整数：

N M K

分别表示棋盘的行数、列数和要放置的马的数量。

输出格式

输出一个整数，表示方案数对10^9+7取模的结果。

数据范围

输入输出样例

样例1

输入：

1 2 1

输出：

2

解释：在1×2的棋盘上放置1个马有2种方式。

样例2

输入：

4 4 3

输出：

276

样例3

输入：

3 20 12

输出：

914051446

算法提示

1. 考虑使用状态压缩动态规划
2. 需要记录前两行的放置状态
3. 注意处理大数取模运算
4. 时间复杂度优化是关键

注意事项

• 马的位置不能互相攻击
• 结果需要对10^9+7取模
• 棋盘行列编号从1开始

题目来源：第十二届蓝桥杯省赛第二场C++ A组/B组