题目描述

译自 COCI 2023/2024 Contest #1 T4「Kocke」

为了庆祝 Donald 的十三岁生日，他的父母给他买了一套全新的乐高积木。这套积木中有 $n$ 块大小相同的积木，第 $i$ 块的颜色为 $i$。Donald 决定使用这些积木来建一座墙。

Donald 将在排成一排的乐高积木的底座上建造他的墙，底座上有 $k$ 个可以放积木的地方。他按以下方式放置积木：

• 首先，他将颜色为 $1$ 的积木放在底座的任意一个位置上。
• 对于每个颜色从 $2$ 到 $n$ 的积木，他都会把它放在先前放置的积木的邻近位置。如果该位置不是空的，他就把新积木放在这个位置所有其他积木的上面。

在他建好墙后，Donald 会在纸上写下一个长为 $k$ 的序列：在这个序列的第 $i$ 个位置，他会写下在第 $i$ 个位置上最顶端的积木颜色，如果那个位置没有积木，则写 $0$。

他立刻问自己他可能在纸上写出多少种不同的序列。如果两个序列存在一个位置不同，则认为两个序列不同。在一些时间后，他能算出答案了，但他不确定结果是否正确，所以他请你帮帮他。

输入格式

仅一行两个整数 $n$ 和 $k\ (2\le n,k\le 5\ 000)$，分别为积木的数量和底座的长度。

输出格式

输出一行一个整数，表示 Donald 问题的答案，模 $10^9+7$。

4 3

8

所有可能的序列有：$(0, 3, 4), (2, 3, 4), (0, 4, 3), (1, 4, 3), (4, 3, 0), (4, 3, 2), (3, 4, 0), (3, 4, 1)$。

3 5

14

其中一个可能的序列为 $(0,3,2,0,0)$。Donald 可以先将第一块积木放在第二个位置，第二个积木放在第三个位置，然后第三个积木放在第二个位置（放在第一个积木的上面）来得到这个序列。

100 200

410783331

数据范围与提示

详细子任务附加限制及分值如下表所示。

子任务编号	附加限制	分值
$1$	$n,k\le 18$	$19$
$2$	$n,k\le 50$	$27$
$3$	$n,k\le 500$
$4$	无附加限制