铺满光砖

周期累加完了，但Zero的地面需要铺砖——光砖。

"光砖？"CC问。

"对。"你说，"$n\times m$的地面，用$1\times 2$的光砖铺。求铺法总数。"

"铺法？"

"对。"你说，"光砖可以横着或竖着放。"

"咋算？"

"状压DP。"你说，"用二进制表示每一行的状态——哪些位置被竖着的光砖占用。"

"状压？"

"对。"你说，"状态压缩——用一个整数的二进制位表示一行的铺法。"

"$m$多大？"

"不超过10。"你说，"$2^{10}=1024$，状态数可接受。"

"转移？"

"对。"你说，"枚举当前行的所有合法状态，看哪些能从上一行转移过来。"

"合法？"

"对。"你说，"不能有两个竖着的光砖重叠，横着的光砖要成对。"

"第47种状态。"你说，"二进制$101111$——某些位置被占用。"

"能转移？"

"看上一行。"你说，"如果上一行 complement 后没有冲突，就能转移。"

"complement？"

"对。"你说，"补集——上一行占用的位置，这一行必须空出来给竖砖。"

"像拼图？"

"对。"你说，"像拼图——一块一块，严丝合缝。"

"铺满？"

"对。"你说，"每一块地都有砖，没有空隙。"

"如果铺不满？"

"$n\times m$是奇数，铺不满。"你说，"因为每块砖占2格，总面积必须是偶数。"

"偶数？"

"对。"你说，"$n\times m$必须是偶数。"

CC看着地面——像一张白纸，像一块空地，像某种等待被填满的东西。

"填满好？"她问。

"对。"你说，"填满就完整了。"

"完整？"

"对。"你说，"没有空隙，没有遗憾。"

Echo把铺砖过程投射出来——一块一块光砖落下，像星星，像希望。

"以前我是空的。"她说，"现在……在被填满。"

"因为我们在。"CC说。

"对。"Echo说，"因为你们在。

题目描述

$n\times m$地面，用$1\times 2$砖铺。求铺法总数模$10^9+7$。

输入格式

一行两个整数$n$和$m$。

输出格式

铺法总数。

输入样例

5
1 2 3 4 5

输出样例

0
3
95

提示

• 状压DP：$dp[i][s]$表示第$i$行状态为$s$的方案数。
• 预处理所有合法状态及兼容转移。
• 时间复杂度$O(n\times 2^m\times 2^m)$，可优化。