[R46G]贪吃鬼 - 代码源竞赛平台

时空限制

1S/512M

题目描述

你酷爱甜食，但你的妈妈害怕你糖度太高，所以不让你吃糖。因此你只能在梦里吃糖。

你的梦里从左到右有 $n$ 个糖果，每种糖果有一个在 $[1,m]$ 之间的颜色。你每次操作会选择两个颜色相同的糖果，把它们以及它们之间的所有糖果都吃掉。你记得对于梦里的糖果序列，存在一种方法能够把所有糖果吃完。

你醒来后忘记了梦中的糖果序列是什么，所以你想知道有多少个糖果序列可能在你梦中。

由于结果很大，你只要求出它除以 $10^9+7$ 得到的余数即可。

格式

输入格式

第一行包含两个正整数 $n$ 和 $m$，具体含义见题目描述。

输出格式

一行一个正整数，表示答案除以 $10^9+7$ 得到的余数。

样例

样例输入 #1

3 2

样例输出 #1

4

样例解释 #1

合法的序列有 $\{1, 1, 1\}, \{1, 2, 1\}, \{2, 1, 2\}, \{2, 2, 2\}$。 在这些情况下，第一个和最后一个糖果颜色相同，可以直接选择这两个糖果，从而一次性吃掉区间 $[1, 3]$ 内的所有糖果。

样例输入 #2

10 4

样例输出 #2

638860

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

子任务编号	分数	$n\le$	$m\le$
$1$	$30$	$50$	$2$
$2$	$70$	$3000$	$10^9$

对于 $100\%$ 的数据，$2 \le n \le 3000$，$1 \le m \le 10^9$。