地板砖

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程序设计竞赛