Problem Description

On Donald’s 13th birthday, his father gave him a set of LEGO bricks. In this set, there are $n$ bricks of the same size, and the color of the $i$-th brick is $i$. He wants to use these bricks to build a wall.

Donald will build his wall on a base where the LEGO bricks are arranged in a line. The base has $k$ positions where bricks can be placed. He places the bricks in the following way:

• First, he places the brick of color $1$ on any position on the base.
• For each brick of color $2$ to $n$, he always chooses a position adjacent to the previous brick, and places this brick on the top of the stack at that position.

He represents the wall with a sequence of length $k$: for position $i$, if there is no brick in that position, it is $0$; otherwise, it is the color of the topmost brick at that position.

How many different sequences are there? Output the answer modulo $10^9+7$.

Input Format

One line with two integers $n, k$, representing the number of bricks and the number of positions.

Output Format

One integer, the answer modulo $10^9+7$.

4 3

8

3 5

14

100 200

410783331

Hint

Sample Explanation #1

The possible sequences are: $(0, 3, 4), (2, 3, 4), (0, 4, 3), (1, 4, 3), (4, 3, 0), (4, 3, 2), (3, 4, 0), (3, 4, 1)$.

Sample Explanation #2

One possible sequence is $(0,3,2,0,0)$. The operations are:

• Place the brick numbered $1$ on the top of position $2$.
• Place the brick numbered $2$ on the top of position $3$.
• Place the brick numbered $3$ on the top of position $2$.

Constraints

For $100\%$ of the testdata, $2 \leq n, k \leq 5000$.

This problem uses bundled testcases.

Notes

The scoring of this problem follows the original COCI problem, with a full score of $110$.

Translated from COCI2023-2024 CONTEST #1 T4 Kocke.

Translated by ChatGPT 5