26115번 - Lego Wall 서브태스크다국어

There are two kinds of lego bricks, characterized by their dimensions: 1 × 1 × 1 and 2 × 1 × 1 (width, height and depth, respectively, as shown below). You have an infinite supply of each of them, and within each kind, they are indistinguishable.

A lego brick is always used in upright position. The faces on the sides are made from identical material and are indistinguishable, except their dimensions.

We consider two lego bricks to be locked if one is directly above the other. Two bricks b₀ and b_k are said to be connected if there is a sequence of bricks b₀, b₁, …, b_k such that bricks b_i−1 and b_i are locked for all i such that 1 ≤ i ≤ k. We consider an arrangement of bricks connected if each pair of bricks within this arrangement is connected.

You would like to build a thin rectangular wall with width w and height h (and depth 1) such that the wall contains no holes and its brick arrangement is connected. As an example, below is a such a lego wall of width 4 and height 3:

On the other hand, the following 4 × 3 lego wall is not connected, and therefore is not desired:

How many ways of building a connected wall with no holes are there? Since this number may be large, output it modulo 1 000 000 007.

Note that the mirrored (180-degree rotated) version of a lego wall is considered to be a different wall, unless the mirrored wall looks identical to the original wall.

The input consists of a single line containing two space separated integers w and h (1 ≤ w ≤ 250 000, 2 ≤ h ≤ 250 000, w × h ≤ 500 000) – the width and the height of the wall, respectively.

Output a single integer – the number of hole-free connected lego walls of dimensions w × h, modulo 1 000 000 007.