P9318 [EGOI 2022] Lego Wall / 乐高墙

Day 1 Problem B. 题面译自 [EGOI2022 legowall](https://stats.egoi.org/media/task_description/2022_legowall_en.pdf)。 [](https://creativecommons.org/licenses/by-sa/3.0/)

有两种乐高积木，大小分别为 $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$ 取模的结果。

**样例 $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$ 分）：无特殊限制。