[AHOI2024 初中组] 计数
题目描述
小可可做了一个梦,梦里从左到右有 $n$ 个糖果,每种糖果有一个颜色,用 $[1, m]$ 之间的一个正整数表示。
小可可每次会选择两个颜色相同的糖果,把它们以及它们之间的所有糖果吃掉。
小可可记得,对于梦里的糖果序列,存在一种方法把所有糖果吃完。
小可可醒来后忘记了梦中的糖果序列是什么,你能帮她求求在所有 $m^n$ 个可能的糖果序列中,有多少个糖果序列可能在小可可梦中(即存在一种全部吃完的方式)吗?
由于结果可能很大,你只要求出它除以 $10^9+7$ 得到的余数即可。
输入输出格式
输入格式
一行两个正整数 $n,m$。
输出格式
一行一个非负整数,表示答案除以 $10^9+7$ 得到的余数。
输入输出样例
输入样例 #1
3 2
输出样例 #1
4
输入样例 #2
6 3
输出样例 #2
405
输入样例 #3
30 2
输出样例 #3
73741759
输入样例 #4
100 100
输出样例 #4
566607183
说明
### 样例 1 解释
一共有 $4$ 个合法的糖果序列:$[1,1,1],[1,2,1],[2,1,2],[2,2,2]$。
### 数据范围
对于 $10\%$ 的数据,$1 \le n \le 6$,$1 \le m \le 4$。
对于 $20\%$ 的数据,$1 \le n \le 6$,$1 \le m \le 100$。
对于另外 $30\%$ 的数据,$1 \le n \le 50$,$1 \le m \le 2$。
对于 $70\%$ 的数据,$1 \le n,m \le 100$。
对于 $80\%$ 的数据,$1 \le n,m \le 1000$。
对于 $100\%$ 的数据,$1 \le n \le 3000$,$1 \le m \le 10^9$。