AT_kupc2013_j タイル置き
题目描述
在一个 $h \times w$ 的棋盘上放置 $n$ 个 $1 \times 2$ 的骨牌，有多少种放法？答案对 $10^9+7$ 取模后输出。
备注：
- 骨牌不可重叠，可以旋转；
- 所有骨牌不做区别；
- 骨牌旋转 $180°$后与原来相同，不做区分。
输入格式
一行三个整数 $h,w,n$。
输出格式
将方案总数对 $10^9+7$ 取模后输出。
### 输入输出样例
| 样例编号 | 输入 | 输出 |
| :-----------: | :-----------: | :-----------: |
| $1$ | `2 2 1` | `4` |
| $2$ | `2 2 2` | `2` |
| $3$ | `2 2 3` | `0` |
| $4$ | `1000000000 1000000000 5` | `68450176` |
说明/提示
#### 数据规模与约定
$1 \le h,w \le 10^9$，$1 \le n \le 5$，输入均为整数。