题目描述

有一间房间的地板可以分成 $n\times m$ 个方块，需要使用两种类型的地砖将这间房屋铺满：

• 第一种是 $2\times 1$ 的长方形；
• 第二种是 L 型的瓷砖，$2\times 2$ 的方块上缺一个 $1\times 1$ 的角。

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

输入格式

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

输出格式

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

2 5

24

1 7

0

样例解释 2

没有方案可以铺满房间

数据范围

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