You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Problem Description

题目描述

在码头，请你帮工人堆放集装箱。

共 $n$ 个位置排成一排，有 $m$ 个大小相同的集装箱，集装箱可以在这 $n$ 个位置被堆放，为保证货物安全，集装箱的堆放必须遵循以下规范：

1. 每个位置至少有一个集装箱。
2. 集装箱只能放在地上或者某集装箱的正上方，高度无限制。
3. 为了防止积水，这一排集装箱不能存在凹陷，即对于任意一列集装箱，其左右两列的高度不能同时大于它。

请你计算出一共有多少种不同的堆放方案（两种堆放方案的集装箱位置不完全重合，则认为是不同的堆放方案），使得 $m$ 个集装箱恰好放满了 $n$ 个位置，答案对 $10^9+7$ 取模。

输入格式

输入包含一行，两个整数 $n$, $m$ ( $1 \leq n \leq m \leq 5000$ )。

• $n$ 代表要堆放的集装箱的列数（宽度）。
• $m$ 代表集装箱的数量。

输出格式

输出一个整数，表示使得 $m$ 个集装箱恰好放满了 $n$ 个位置的堆放方案数，答案对 $10^9+7$ 取模。

输入输出样例 #1

输入 #1

3 4

输出 #1

3

输入输出样例 #2

输入 #2

3 7

输出 #2

12

说明/提示

对于第一个样例，底部排满的情况下，只多出了一个集装箱，这个集装箱可以堆放在任意一个集装箱上，所以共有三种情况。

数据范围

$1 \leq n,m \leq 5000$。

Output Format

Sample