Problem Background

Day 1 Problem B.

This problem is translated from EGOI2022 legowall.

Problem Description

There are two types of Lego bricks, sized $1\times 1\times 1$ and $2\times 1\times 1$ (width, height, length). You have an unlimited supply of both types, and all bricks of each type are indistinguishable from each other.

A brick is always used in the correct orientation. The four sides are made of the same material, indistinguishable except for size.

We say two bricks are locked if one is directly above the other. We say two bricks $b_0$ and $b_k$ are connected if there exists a sequence of bricks $b_0, b_1, \ldots, b_k$ such that any two adjacent bricks $b_{i-1}$ and $b_i$ are locked. A group of bricks is connected if every pair of bricks within the group is connected.

You want to build a Lego wall of size $w\times h\times 1$ such that the wall is hole-free and connected. Here 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 and is therefore not desired:

How many ways are there to build a hole-free and connected Lego wall? The answer may be very large, so output it modulo $10^9+7$.

Note that a mirrored version of a Lego wall (rotated $180^\circ$) is considered different from the original unless they look identical.

Input Format

A single line containing two integers $w, h$ — the width and height of the Lego wall.

Output Format

A single line containing an integer, the number of ways to build the Lego wall modulo $10^9+7$.

Sample Input and Output

Sample Input #1

2 2

Sample Output #1

3

Sample Input #2

3 3

Sample Output #2

12

Sample Input #3

5 7

Sample Output #3

1436232

Notes

Sample 1 Explanation

The three possible solutions are shown in the figure below:

Data Range

For all data, $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$.

• 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.

见题面 Input 部分

见题面 Output 部分