第2题 棋盘有一个R行C列的棋盘，共有R×C个单元格子，每个单元格子都要放一个棋子，棋子只有黑色或者白色。如果两个单元格子有公共边，那么称为相邻的格子。如果一个棋盘满足所有相邻格子的棋子都是不同颜色，

第2题 棋盘fRs100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
有一个R行C列的棋盘，共有R×C个单元格子，每个单元格子都要放一个棋子，棋子只有黑色或者白色。fRs100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
如果两个单元格子有公共边，那么称为相邻的格子。fRs100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
如果一个棋盘满足所有相邻格子的棋子都是不同颜色，那么就称为“优美”棋盘;否则称为“普通”棋盘。fRs100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
把棋盘上的一个黑色棋子变成一个白色棋子，需要耗费1个能量。fRs100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
同理，把棋盘上的一个白色棋子变成一个黑色棋子，也需要耗费1个能量。fRs100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
如果把一个“普通”棋盘变成“优美”棋盘，至少需要消耗D能量，那么该“普通”棋盘的代价就是D。fRs100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
下面的“普通”棋盘的代价就是2，因为至少要消耗2个能量，才能变成“优美”棋盘fRs100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
WBWBWfRs100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
BWBWBfRs100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
BBWWWfRs100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
BWBWBfRs100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
容易发现，代价是D的“普通”棋盘，可能有很多种。fRs100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
求：总共有多少种不同的代价是D的“普通”棋盘？模1000000007。fRs100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
输入格式fRs100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
一行，3个整数，R,C,D。1<=R,C<=100, 0<=D<=100。fRs100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
【提示】fRs100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
60%的数据，1<=R,C,D<=10。fRs100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
输出格式fRs100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
一个整数。fRs100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
输入/输出例子1fRs100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
输入：fRs100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
2 2 1fRs100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
输出：fRs100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
8fRs100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
输入/输出例子2fRs100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
输入：fRs100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
9 4 15fRs100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
输出：fRs100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
135805043fRs100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库