U423505 [“科大国创杯”2024 年安徽省青少年信息学科普日-初中组] 计数

“科大国创杯”2024 年安徽省青少年信息学科普日-初中组第四题

小可可做了一个梦，梦里从左到右有 $n$ 个糖果，每种糖果有一个在 $\left [ 1,m\right ] $ 之间的颜色。 小可可每次会选择两个颜色相同的糖果，把它们以及它们之间的所有糖果吃掉。小可可记得对于梦里的糖果序列，存在一种方法把所有糖果吃完。 小可可醒来后忘记了梦中的糖果序列是什么，你能帮她求求在所有 $m^n$ 个可能的糖果序列中，有多少个糖果序列可能在小可可梦中（存在一种全部吃完的方式）吗？ 由于结果很大，你只要求出它除以 $10^9 + 7$ 得到的余数即可。

一行两个正整数 $n$ 和 $m$，含义与题面中相同。

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

### 样例 1 解释 有 4 个合法的糖果序列：$\left [ 1,1,1\right ]$，$\left [ 1,2,1\right ]$，$\left [ 2,1,2\right ]$，$\left [ 2,2,2\right ]$。 ### 数据规模与约定 对于 $10\%$ 的数据，$1 \le n \le 6，1 \le m \le 4$。 对于 $20\%$ 的数据，$1 \le n \le 6，1 \le m \le 1000$。 对于另 $30\%$ 的数据，$1 \le n \le 50，1 \le m \le 2$。 对于 $70\%$ 的数据，$1 \le n \le 100，1 \le m \le 100$。 对于 $80\%$ 的数据，$1 \le n \le 1000，1 \le m \le 1000$。 对于 $100\%$ 的数据，$1 \le n \le 3000，1 \le m \le 10^9$。