HZNUOJ

构造(hard)

Tags:
Time Limit:  1 s      Memory Limit:   50 MB
Submission:128     AC:22     Score:100.00

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

input
3 2
output
4

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

ZHANG, Kaili