P9906 [COCI 2023/2024 #1] Kocke

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$.

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

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

### 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.** | Subtask | Special Property | Score | | :----------: | :----------: | :----------: | | $1$ | $n, k \leq 18$ | $20$ | | $2$ | $n, k \leq 50$ | $30$ | | $3$ | $n, k \leq 500$ | $30$ | | $4$ | No special property | $30$ | ### Notes The scoring of this problem follows the original COCI problem, with a full score of $110$. Translated from [COCI2023-2024](https://hsin.hr/coci/archive/2023_2024/) [CONTEST #1](https://hsin.hr/coci/archive/2023_2024/contest1_tasks.pdf) _**T4 Kocke**_. Translated by ChatGPT 5