地板砖
Time Limit: 1000 ms
Memory Limit: 65536 KiB
Problem Description
利用假期时间,豆豆找个了临时工,帮有钱人家贴地板砖,假设房子的形状为 N x M 的矩形,每个地板砖的大小为 1 x 1,且只有黑白两种颜色,这家人很奇怪,他们不喜欢房间中任何一个 2 x 2 的局部区域的 4 块地板砖的颜色一样。如果出现这种图案,豆豆就要重新贴,这当然难不倒豆豆,但爱学习的豆豆,想知道满足要求的贴法一共用多少种。
如下图所示:Figure 1.为满足要求的贴法,Figure 2.为不满足要求的贴法
Input
输入包含多组测试数据,对于每组测试数据:
输入只有两个正整数 N、M(N ≤ 500, M ≤ 5),分别代表房间的长度和宽度。
Output
对于每组测试数据,输出满足要求的贴法总数,由于答案可能很大,所以需要对10007取余。
Sample Input
2 2 3 3
Sample Output
14 322
Hint
Source
“师创杯”山东理工大学第五届ACM程序设计竞赛