时间限制： 3.0 秒

空间限制： 256 MB

问题描述

给出一个 $n \times m$ 的方格图，现在要用如下 $L$ 型的积木拼到这个图中，使得方格图正好被拼满，请问总共有多少种拼法。其中，方格图的每一个方格正好能放积木中的一块。积木可以任意旋转。

输入格式

从标准输入读入数据。

输入的第一行包含两个整数 $n,m$，表示方格图的大小。

输出格式

输出到标准输出。

输出一行，表示可以放的方案数，由于方案数可能很多，所以请输出方案数除以 $10^9 + 7$ 的余数。

6 2

4

样例说明

四种拼法如下图所示：

评测用例规模与约定

在评测时将使用 $10$ 个评测用例对你的程序进行评测。

评测用例 $1$ 和 $2$ 满足：$1 \le n \le 30,~m = 2$。

评测用例 $3$ 和 $4$ 满足：$1 \le n,~m \le 6$。

评测用例 $5$ 满足：$1 \le n \le 100,~1 \le m \le 6$。

评测用例 $6$ 和 $7$ 满足：$1 \le n \le 1000,~1 \le m \le 6$。

评测用例 $8$、$9$ 和 $10$ 满足：$1 \le n \le 10^{15},~1 \le m \le 7$。