题目背景

Day 1 Problem B.

题面译自 EGOI2022 legowall。

题目描述

有两种乐高积木，大小分别为 $1\times 1\times 1$ 和 $2\times 1\times 1$（宽、高、长）。两种积木你都有无限个，每种积木的所有积木块没有任何区别。

一个积木块总是以正确的方向使用。四周的面是用同一种材料制成的，除了大小以外没有区别。

我们称两个积木块锁死，当且仅当一个块在另一个块的正上方。称两个积木块 $b_0$ 和 $b_k$ 连通，当且仅当存在一个积木块序列 $b_0,b_1,\ldots,b_k$，使得任意相邻积木块 $b_{i-1}$ 和 $b_i$ 锁死。我们称一组积木块连通，当且仅当组内的每一对积木块都连通。

你希望搭建一个大小为 $w\times h\times 1$ 的积木墙，使得这面墙没有洞且连通。以下是 $4\times 3\times 1$ 的积木墙的例子：

另一方面，下面的 $4\times 3\times 1$ 的积木墙不连通，因此不被需要：

有多少种搭建没有洞且连通的积木墙的方案呢？答案可能很大，请输出它对 $10^9+7$ 取模的结果。

注意一个积木墙的镜像版本（旋转 $180^\circ$）和原来的版本被认为不同，除非他们看起来一模一样。

输入格式

一行，两个整数 $w,h$——积木墙的宽度和高度。

输出格式

一行，一个整数，表示方案数对 $10^9+7$ 取模的结果。

2 2

3

3 3

12

5 7

1436232

提示

样例 $1$ 解释

三种方案如图所示：

---

数据范围

对于全部数据，$1\le w\le 2.5\times 10^5$，$2\le h\le 2.5\times 10^5$，$w\times h\le 5\times 10^5$。

• 子任务一（$14$ 分）：$w=2$。
• 子任务二（$12$ 分）：$h=2$。
• 子任务三（$18$ 分）：$w,h\le 100$。
• 子任务四（$30$ 分）：$w\le 700$。
• 子任务五（$20$ 分）：$h\le 700$。
• 子任务六（$6$ 分）：无特殊限制。