Block stacking

Time limit2sMemory limit512 MB

Summary

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.

Level: Hard8 of 10
Topics: Dynamic programming, Combinatorics, Implementation
Solved: No attempts yet

Problem

Yeongseon can use as many blocks of size $1 \times 1 \times 1$ , $1 \times 1 \times 2$ , and $1 \times 1 \times 3$ as she wants. She also has one block of size $1 \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 \times 1 \times 2$ or $1 \times 1 \times 3$ ) must have both of its ends resting on other blocks. For a $1 \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 $0$ , and it counts as one structure.

Given the length $w$ of the base block and the height limit $h$ , write a program that counts the structures of height at most $h$ 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 = 3$ and $h = 2$ .

Input

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

Output

Print the number of structures modulo $1000000007$ on the first line.

Examples5

Example 1
Input
```
1 3
```
Expected output
```
4
```
Example 2
Input
```
3 1
```
Expected output
```
13
```
Example 3
Input
```
3 2
```
Expected output
```
84
```
Example 4
Input
```
4 9
```
Expected output
```
132976888
```
Example 5
Input
```
5 5
```
Expected output
```
11676046
```