题目描述

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

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

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

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

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

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

---

输入格式

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

---

输出格式

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

---

样例 1

输入

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)$。

---

样例 2

输入

3 5

输出

14

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

---

样例 3

输入

100 200

输出

410783331

---

数据范围与提示

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

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