三铺地砖

题目描述

有一间房间的地板可以分成 $n\times m$ 个单元，可以用两种不同类型的地砖将这间房屋的单元全部覆盖：

• 第一种地砖是 $2\times 1$ 的长方形，同时覆盖两个相邻的单元；
• 第二种地砖是 L 型的瓷砖，覆盖一个中心单元，且覆盖中心单元同行的邻居单元及同列的邻居单元。

求有多少种铺地砖的方案，使得房间都覆盖了地砖且没有重叠。由于答案很大，输出模 $10^9+7$ 的余数。

输入格式

单独一行：两个整数 $n$ 与 $m$。

输出格式

单个整数：表示方案数模 $10^9+7$ 的余数。

样例输入 #1

2 5

样例输出 #1

24

样例输入 #2

1 7

样例输出 #2

0

样例说明 #2

没有方案可以铺满房间。

数据范围

• 对于 30% 的数据，$1\le n,m\le 6$；
• 对于 60% 的数据，$1\le n,m\le 10$；
• 对于 100% 的数据，$1\le n,m\le 18$。

注：本题因搬运超时进入难题降级模式，仅提供题面与样例测试数据，未附标程（std.cpp）与题解（solution.md）。