P9318 [EGOI 2022] Lego Wall / Lego Wall.

Day 1 Problem B. The statement is translated from [EGOI2022 legowall](https://stats.egoi.org/media/task_description/2022_legowall_en.pdf). [](https://creativecommons.org/licenses/by-sa/3.0/)

There are two types of Lego bricks, with sizes $1\times 1\times 1$ and $2\times 1\times 1$ (width, height, length). You have an unlimited number of both types, and all bricks of the same type are indistinguishable.  A brick is always used in the correct orientation. The faces on all sides are made of the same material, and there is no difference other than the size. We say that two bricks are **locked** if and only if one brick is directly above the other. We say that two bricks $b_0$ and $b_k$ are **connected** if and only if there exists a sequence of bricks $b_0,b_1,\ldots,b_k$ such that every pair of adjacent bricks $b_{i-1}$ and $b_i$ are locked. We say that a set of bricks is **connected** if and only if every pair of bricks in the set is connected. You want to build a Lego wall of size $w\times h\times 1$ such that the wall **has no holes** and is **connected**. Below is an example of a $4\times 3\times 1$ Lego wall:  On the other hand, the following $4\times 3\times 1$ Lego wall is not connected, so it is not acceptable:  How many different ways are there to build a Lego wall that **has no holes** and is **connected**? The answer may be very large; output it modulo $10^9+7$. Note that a mirrored version of a Lego wall (rotated by $180^\circ$) is considered different from the original, unless they look exactly the same.

One line with two integers $w,h$ — the width and height of the Lego wall.

One line with one integer, the number of ways modulo $10^9+7$.

**Explanation for Sample $1$** The three valid constructions are shown below:  --- **Constraints** For all testdata, $1\le w\le 2.5\times 10^5$, $2\le h\le 2.5\times 10^5$, and $w\times h\le 5\times 10^5$. - Subtask 1 ($14$ points): $w=2$. - Subtask 2 ($12$ points): $h=2$. - Subtask 3 ($18$ points): $w,h\le 100$. - Subtask 4 ($30$ points): $w\le 700$. - Subtask 5 ($20$ points): $h\le 700$. - Subtask 6 ($6$ points): no additional constraints. Translated by ChatGPT 5