题目描述

有一个R行C列的棋盘，共有R×C个单元格子，每个单元格子都要放一个棋子，棋子只有黑色或者白色。

如果两个单元格子有公共边，那么称为相邻的格子。

如果一个棋盘满足所有相邻格子的棋子都是不同颜色，那么就称为“优美”棋盘;否则称为“普通”棋盘。

把棋盘上的一个黑色棋子变成一个白色棋子，需要耗费1个能量。

同理，把棋盘上的一个白色棋子变成一个黑色棋子，也需要耗费1个能量。

如果把一个“普通”棋盘变成“优美”棋盘，至少需要消耗D能量，那么该“普通”棋盘的代价就是D。

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

WBWBW

BWBWB

BBWWW

BWBWB

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

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

输入格式

一行，3个整数，R,C,D。1<=R,C<=100, 0<=D<=100。

【提示】

60%的数据，1<=R,C,D<=10。

输出格式

一个整数。

输入/输出例子1

输入：

2 2 1

输出：

8

输入/输出例子2

输入：

9 4 15

输出：

135805043