Lego Wall Sequences

On Donald’s 13th birthday, his father gave him a set of LEGO bricks. The set contains n bricks of identical size, where the i-th brick has color i (represented by the number i). Donald wants to build a wall on a base that has k positions arranged in a row. He places the bricks one by one (brick 1 to brick n) according to the following rules:

• If the brick’s number is 1, he may place it in any of the k positions.
• For each subsequent brick (with number i > 1), he chooses one of the bricks already placed, and then places the new brick on the top of the brick in a position adjacent to that chosen brick. More precisely, if the chosen brick lies at position j, he may put brick i on top of the brick at position j-1 or j+1, provided that the chosen adjacent position exists (i.e. within the range 1 to k).

The final wall is represented by a sequence of length k. For the i-th position, if no brick was ever placed in that position, its value is 0; otherwise, its value is the color of the brick on the top (i.e. the last brick placed in that position). Two walls are considered different if their final sequences differ.

For example, consider the case when n = 3 and k = 3. One possible process is as follows:

1. Place brick 1 at position 2.
2. Brick 2 must be placed adjacent to brick 1. Donald chooses the left neighbor (position 1) and places brick 2 there.
3. For brick 3, he has several choices. For instance, he could choose the brick at position 2 and place brick 3 on its right (position 3), thus expanding the wall; or he might choose the brick at position 1 and stack brick 3 on top of the brick at position 2. (Notice that when a brick is placed on an already occupied position it is stacked on top, overwriting the previous top brick’s color in the final view.)

Determine the number of different final sequences that can be obtained by following the above process. Since the answer can be large, output it modulo \(10^9+7\).

Note: In all formulas below, use LaTeX formatting for any mathematical expressions. For example, write $n$, $k$, and $10^9+7$ as shown.

inputFormat

The input consists of a single line with two integers: n and k ($1\le n\le 10$, $1\le k\le 10$).

Here, n is the number of bricks and k is the number of positions available on the base.

outputFormat

Output a single integer, which is the number of different final wall sequences that can be obtained, modulo \(10^9+7\).

sample

1 2

2