Block stacking

Count structures built on one 1x1xw base block using unlimited 1x1x1, 1x1x2, and 1x1x3 blocks with height at most h, where long blocks need both ends supported.

Hard8Dynamic programmingCombinatoricsImplementationNo attempts yetTime limit2sMemory limit512 MB

Problem

Yeongseon can use as many blocks of size 1×1×11 \times 1 \times 1, 1×1×21 \times 1 \times 2, and 1×1×31 \times 1 \times 3 as she wants. She also has one block of size 1×1×w1 \times 1 \times w, which is called the base block.

Yeongseon builds a structure from one base block and the other blocks. Every block must be connected to the base block, and no block can be placed at a non-integer position. A long block (1×1×21 \times 1 \times 2 or 1×1×31 \times 1 \times 3) must have both of its ends resting on other blocks. For a 1×1×31 \times 1 \times 3 block, the cell under its middle part may be empty.

The picture on the left is a valid structure. The picture on the right cannot be built.

The height of a structure is the number of layers stacked on top of the base block. The structure with no block at all has height 00, and it counts as one structure.

Given the length ww of the base block and the height limit hh, write a program that counts the structures of height at most hh that can be built from one base block and an unlimited number of the other blocks.

The picture below shows all 84 structures for w=3w = 3 and h=2h = 2.

Input

The first line contains ww and hh, separated by a space. (1w,h101 \le w, h \le 10)

Output

Print the number of structures modulo 10000000071000000007 on the first line.