题目描述

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

已经学习了很多算法的小蓝觉得 “八皇后” 问题太简单了，意犹未尽。作为一个国际象棋迷，他想研究在N×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) 的余数。

1 2 1

2

4 4 3

276

3 20 12

914051446

提示

数据范围

对于所有评测用例，1≤N≤6，1≤M≤100，1≤K≤20。