题目描述

在 Donald 的十三岁生日上，他的父亲给了他一套乐高积木。在这套积木中，有 $n$ 个大小相同的积木，且第 $i$ 个积木的颜色为 $i$ 。

他想要用这些积木搭一面墙。他想要把这 $n$ 个积木搭在有 $k$ 排成一行的位置的底座上，对积木 $1\sim n$ 依次进行以下操作：

• 如果这个积木编号为 $1$，则可以放在任意位置。
• 否则选择一个上一个放置的积木相邻位置，在它的顶端放上这个积木。

他用一个长度为 $k$ 序列表示这面墙：对于第 $i$ 位，如果个位置没有积木，则是 $0$，否则是这个位置最顶端积木的颜色。

问一共有多少种不同的序列，对 $10^9+7$ 取模。

输入格式

一行两个整数 $n,k$ 表示积木数量和位置数量。

输出格式

一个整数表示问题答案对 $10^9+7$ 取模的结果。

4 3

8

3 5

14

100 200

410783331

提示

【样例解释#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$。

本题采用捆绑测试。

【说明】

本题分值按 COCI 原题设置，满分 $110$。

题目译自 COCI2022-2023 CONTEST #1 T4 Kocke。