3635: B 君的吸引
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：0
解决：
题目描述
B 君希望用一个 n × m 的矩形，非常正常地密铺整个平面。
然后 B 君开始用 1 × 2 的小矩形，来铺整个平面。
为了美观起见，要求每个 n × m 内的 1 × 2 的小矩形的形状是一样的。
用 1 × 2 的小矩形密铺整个平面的时候，如果两个方案通过平移是相等
的，我们认为这两个方案本质相同。
输入 n, m，求方案数，结果对 1000000007 取模。
如果你看不懂上面的题目，我们不形式化的给出如下定义。
首先为了让大家能够理解，我们要将 n × m 的矩形填入「上下左右」四
种汉字，其中上下和左右均为成对出现，「上」表示这个格子是一个 2 × 1
的小矩形的上半部分，当然这一块的下边就是「下」，表示小矩形的下半部
分。
左右
左右
上面是一个最简单的铺设方案，就是两个 1 × 2 的叠加在一起。不要被表面
的现象所迷惑，上面方案和下面的方案是本质相同的。
右左
右左
「右」表示他是一个 1 × 2 的块的右半部分，因为 n × m 密铺了整个平
面，「右」的左侧，是另一个和这个全等的块，所以「右」的左侧，即为整
个块的最右一列，为「左」。
样例中四种不同的方案，分别是
右左
右左
和
上上
下下
和
右左
左右
和
上下
下上
输入
一行两个整数 n, m
输出
一行一个数表示答案。
样例输入 复制
2 2样例输出 复制
4提示
【数据规模与约定】
对于 100% 的数据，满足 1 ≤ n ≤ 10, 1 ≤ m ≤ 10^9。
对于 50% 的数据，满足 1 ≤ m ≤ 100000。
对于 50% 的数据，满足 1 ≤ n ≤ 4。
以上两部分 50% 是相互独立的。