Background

Day 1 Problem B.

The statement is translated from EGOI2022 legowall.

Problem Description

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.

Input Format

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

Output Format

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

2 2

3

3 3

12

5 7

1436232

Hint

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