构造（hard）

Tags:

Description

$hard$ 和 $easy$ 相比只有数据范围不同。

要求构造一个序列，满足：

1.长度为$n$

2.序列中的每个数字$1<=a_i<=m$

3.对于序列的任意位置$i$满足$a_i<=a_{i+1}$

问一共能构造多少个这样的序列。（答案取模$1000000007$）

Input

两个整数$n,m$。$(1<=n<=5000,1<=m<=5000)$

Output

输出一行一个整数，即最多能构造的序列数。

Samples

Hint

对于样例满足的序列有$4$个：

$[1,1,1]$,$[1,1,2]$,$[1,2,2]$,$[2,2,2]$。

注意使用 long long

(a + b) % m = (a % m + b % m) % m

(a * b) % m = ((a %m) * (b % m)) % m

Author