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$，输入均为整数。