ACSPJ20244 计数
题目描述
小可可做了一个梦，梦里从左到右有 n 个糖果，每种糖果有一个在 [1, m] 之间的颜 色。
小可可每次会选择两个颜色相同的糖果，把它们以及它们之间的所有糖果吃掉。小 可可记得对于梦里的糖果序列，存在一种方法把所有糖果吃完，
小可可醒来后忘记了梦中的糖果序列是什么，你能帮她求求在所有 m^n 个可能的糖 果序列中，有多少个糖果序列可能在小可可梦中（存在一种全部吃完的方式）吗？
由于结果很大，你只要求出它除以 10^9 + 7 得到的余数即可。
输入格式
一行两个正整数 n 和 m，含义与题面中相同。
输出格式
一行一个正整数，表示答案除以 10^9 + 7 得到的余数。
3 2
4
样例解释
有 4 个合法的糖果序列：[1, 1, 1]，[1, 2, 1]，[2, 1, 2]，[2, 2, 2]。
数据范围
对于 10% 的数据，1 ≤ n ≤ 6，1 ≤ m ≤ 4。
对于 20% 的数据，1 ≤ n ≤ 6，1 ≤ m ≤ 1000。
对于另 30% 的数据，1 ≤ n ≤ 50，1 ≤ m ≤ 2。
对于 70% 的数据，1 ≤ n ≤ 100，1 ≤ m ≤ 100。
对于 80% 的数据，1 ≤ n ≤ 1000，1 ≤ m ≤ 1000。
对于 100% 的数据，1 ≤ n ≤ 3000，1 ≤ m ≤ 10^9。