为了庆祝十三岁生日，Donald 的父母送给他一套全新的乐高积木。这套积木中有 $n$ 个大小相同的立方体，其中第 $i$ 个立方体的颜色为 $i$。他决定用这些积木搭建一面墙。

Donald 将在一块有 $k$ 个位置的行状乐高底座上搭建墙。他按照以下方式放置积木：

• 首先，他将颜色为 1 的立方体放在底座上的任意位置。
• 对于从 2 到 $n$ 的每个立方体，他将其放置在与上一个放置的立方体相邻的位置。如果该位置不为空，他会将新立方体叠放在该位置所有已有积木的上方。

墙搭建完成后，Donald 在一张纸上写下了一个长度为 $k$ 的序列：序列的第 $i$ 个位置记录了第 $i$ 个位置上最顶层积木的颜色，如果该位置没有积木，则记录为 0。

他立刻想到，他能在纸上写出多少种不同的序列？如果两个序列在某个位置上的数值不同，则认为它们是不同的。经过一段时间的思考，他算出了答案，但他不确定是否正确，因此他请求你的帮助。

输入格式

输入仅一行，包含两个整数 $n$ 和 $k$ ($2 \le n, k \le 5000$)，分别表示积木的数量和底座的长度。

输出格式

输出仅一行，表示 Donald 问题的答案，对 $10^9 + 7$ 取模。

子任务

样例

输入 1

4 3

输出 1

8

说明 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

3 5

输出 2

14

说明 2

其中一种可能的序列是 (0, 3, 2, 0, 0)。Donald 可以通过以下方式实现：将第一个立方体放在第二个位置，第二个立方体放在第三个位置，第三个立方体放在第二个位置（叠在第一个立方体上方）。

输入 3

100 200

输出 3

410783331