U268804 2023BYOI T2-三铺地砖

BYOI指博雅信息奥林匹克竞赛。

有一间房间的地板可以分成$n\times m$ 个方块，需要使用两种类型的地砖将这间房屋铺满： - 第一种是 2×1 的长方形； - 第二种是 L 型的瓷砖，2×2 的方块上缺一个 1×1 的角落。 第二种如下： ``` 口 口口 ``` 求有多少种铺地砖的方案，使得房间都覆盖了地砖且没有重叠。由于答案很大，输出答案模 $10^9+7$ 的余数。

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

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

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