1713 - 【基础】计数

小可可做了一个梦,梦里从左到右有 n 个糖果,每种糖果有一个在 [1, m] 之间的颜色。

小可可每次会选择两个颜色相同的糖果,把它们以及它们之间的所有糖果吃掉。小可可记得对于梦里的糖果序列,存在一种方法把所有糖果吃完。

小可可醒来后忘记了梦中的糖果序列是什么,你能帮她求求在所有 m^n 个可能的糖果序列中,有多少个糖果序列可能在小可可梦中(存在一种全部吃完的方式)吗?

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

输入

一行两个正整数 nm,含义与题面中相同。

输出

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

样例

输入

3 2

输出

4

提示

样例 1 解释

有 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。

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题