题目描述

有一个 $R$ 行 $C$ 列的棋盘，共有 $R \times C$ 个单元格子，每个单元格子都要放一个棋子，棋子只有黑色或者白色。如果两个单元格子有公共边，那么称为相邻的格子。

如果一个棋盘满足所有相邻格子的棋子都是不同颜色，那么就称为“优美”棋盘;否则称为“普通”棋盘。把棋盘上的一个黑色棋子变成一个白色棋子，需要耗费 $1$ 个能量。同理，把棋盘上的一个白色棋子变成一个黑色棋子，也需要耗费 $1$ 个能量。如果把一个“普通”棋盘变成“优美”棋盘，至少需要消耗 $D$ 能量，那么该“普通”棋盘的代价就是 $D$。

下面的“普通”棋盘的代价就是 $2$ ，因为至少要消耗 $2$ 个能量，才能变成“优美”棋盘

WBWBW
BWBWB
BBWWW
BWBWB

容易发现，代价是 $D$ 的“普通”棋盘，可能有很多种。

求：总共有多少种不同的代价是 $D$ 的“普通”棋盘？模 $1000000007$。

输入格式

一行，$3$ 个整数，$R,C,D$ ( $1 \le R,C \le 100$, $0 \le D \le 100$ )。

提示

60% 的数据 $1 \le R,C,D \le 10$ 。

输出格式

一个整数。

样例

2 2 1

8

9 4 15

135805043