问题描述

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

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

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

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

输入

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

输出

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

样例 1

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

d_1.in  d_1.out

d_2.in  d_2.out

d_3.in  d_3.out

d_4.in  d_4.out