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

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

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

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

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

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

对于 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$。

4

有 4 个合法的糖果序列：[1,1,1]，[1,2,1]，[2,1,2]，[2,2,2]。