有两种乐高积木，其尺寸分别为 $1 \times 1 \times 1$ 和 $2 \times 1 \times 1$（分别为宽、高和深，如下图所示）。每种积木都有无限供应，且同种积木之间无法区分。

乐高积木总是竖直放置。侧面由相同的材料制成，除了尺寸外无法区分。

如果两块积木一块直接位于另一块上方，我们认为它们是锁定的。如果存在一个积木序列 $b_0, b_1, \dots, b_k$，使得对于所有 $1 \le i \le k$，积木 $b_{i-1}$ 和 $b_i$ 都是锁定的，则称积木 $b_0$ 和 $b_k$ 是连通的。如果一个积木排列中每一对积木都是连通的，我们称该排列是连通的。

你想要建造一个宽为 $w$、高为 $h$（深度为 1）的薄矩形墙，使得墙体没有空洞且其积木排列是连通的。例如，下图是一个宽为 4、高为 3 的乐高墙：

另一方面，以下 $4 \times 3$ 的乐高墙是不连通的，因此不符合要求：

建造一个没有空洞的连通墙有多少种方法？由于这个数字可能很大，请输出其对 $1\,000\,000\,007$ 取模的结果。

注意，乐高墙的镜像（旋转 180 度）版本被视为不同的墙，除非镜像后的墙与原墙看起来完全相同。

输入格式

输入包含一行，包含两个空格分隔的整数 $w$ 和 $h$ ($1 \le w \le 250\,000, 2 \le h \le 250\,000, w \times h \le 500\,000$)，分别表示墙的宽度和高度。

输出格式

输出一个整数，表示尺寸为 $w \times h$ 的无空洞连通乐高墙的数量，对 $1\,000\,000\,007$ 取模。

子任务

• 子任务 1 (14 分)：$w = 2$。
• 子任务 2 (12 分)：$h = 2$。
• 子任务 3 (18 分)：$w, h \le 100$。
• 子任务 4 (30 分)：$w \le 700$。
• 子任务 5 (20 分)：$h \le 700$。
• 子任务 6 (6 分)：无额外限制。

样例

样例输入 1

2 2

样例输出 1

3

样例输入 2

3 3

样例输出 2

12

样例输入 3

5 7

样例输出 3

1436232

说明

对于第一个样例，可以建造的三个连通的 $2 \times 2$ 墙如下：