P9906 [COCI 2023/2024 #1] Kocke

在 Donald 的十三岁生日上，他的父亲给了他一套乐高积木。在这套积木中，有 $n$ 个大小相同的积木，且第 $i$ 个积木的颜色为 $i$ 。 他想要用这些积木搭一面墙。他想要把这 $n$ 个积木搭在有 $k$ 排成一行的位置的底座上，对积木 $1\sim n$ 依次进行以下操作： - 如果这个积木编号为 $1$，则可以放在任意位置。 - 否则选择一个上一个放置的积木相邻位置，在它的**顶端**放上这个积木。 他用一个长度为 $k$ 序列表示这面墙：对于第 $i$ 位，如果个位置没有积木，则是 $0$，否则是这个位置最顶端积木的颜色。 问一共有多少种不同的序列，对 $10^9+7$ 取模。

无

无

### 【样例解释#1】 可能的序列有：$(0, 3, 4), (2, 3, 4), (0, 4, 3), (1, 4, 3), (4, 3, 0), (4, 3, 2), (3, 4, 0), (3, 4, 1)$。 ### 【样例解释#2】 其中一种可能的序列是 $(0,3,2,0,0)$，它的操作步骤是： - 在第 $2$ 个位置顶端摆放编号为 $1$ 的积木。 - 在第 $3$ 个位置顶端摆放编号为 $2$ 的积木。 - 在第 $2$ 个位置顶端摆放编号为 $3$ 的积木。 - 在第 $3$ 个位置顶端摆放编号为 $4$ 的积木。 - 在第 $2$ 个位置顶端摆放编号为 $5$ 的积木。 ### 【数据范围】 对于 $100\%$ 的数据，$2\leq n,k\leq 5000$。 **本题采用捆绑测试。** | 子任务 | 特殊性质 | 分值 | | :----------: | :----------: | :----------: | | $1$ | $n,k\leq 18$ | $20$ | | $2$ | $n,k\leq 50$ | $30$ | | $3$ | $n,k\leq 500$ | $30$ | | $4$ | 无特殊性质 | $30$ | ### 【说明】 本题分值按 COCI 原题设置，满分 $110$。 题目译自 [COCI2022-2023](https://hsin.hr/coci/) [CONTEST #1](https://hsin.hr/coci/contest1_tasks.pdf) _**T4 Kocke**_。