Problem Description

On Donald's thirteenth birthday, his father gifted him a set of LEGO bricks. In this set, there are $n$ identical-sized bricks, and the color of the $i$-th brick is $i$.

Donald wants to build a wall using these bricks. He plans to place these $n$ bricks on a base with $k$ positions arranged in a row. For each brick from $1$ to $n$, he performs the following operations:

• If the brick number is $1$, it can be placed at any position.
• Otherwise, choose a position adjacent to the previously placed brick and place this brick on top of it.

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

Determine the number of different sequences possible, modulo $10^9+7$.

Input Format

A single line containing two integers $n$ and $k$, representing the number of bricks and the number of positions, respectively.

Output Format

An integer representing the answer to the problem modulo $10^9+7$.

Sample Input and Output

Sample Input #1

4 3

Sample Output #1

8

Sample Input #2

3 5

Sample Output #2

14

Sample Input #3

100 200

Sample Output #3

410783331

Notes/Hints

Sample Explanation #1

Possible sequences include: $(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 steps to achieve this sequence are:

• Place the brick numbered $1$ on top of the second position.
• Place the brick numbered $2$ on top of the third position.
• Place the brick numbered $3$ on top of the second position.
• Place the brick numbered $4$ on top of the third position.
• Place the brick numbered $5$ on top of the second position.

Data Range

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

This problem uses batched testing.

Notes

The points for this problem are set according to the original COCI contest, with a maximum of $110$ points.

The problem is translated from COCI2022-2023 CONTEST #1 T4 Kocke.

见题面 Input 部分

见题面 Output 部分