测试数据来自 system/1025

作业已超过截止时间，您无法递交本题目。

时间限制：1秒　　内存限制：256M

---

【问题描述】

　　小H有 \(n\) 只气球，他把气球排成一排。初始时气球都是白色，现在小H想用 \(m\) 种颜色给气球涂色（每个球必须涂上 \(m\) 种颜色之一），如果相邻的气球的颜色相同，这 2 个气球会发生消消乐，小H希望你求出会发生消消乐的涂色方法有多少种。注意：最后答案对 \(10^9+7\) 取模。

【输入格式】

　　输入两个整数 \(n,m\)。

【输出格式】

　　输出一行表示答案。

【输入输出样例1】

　Input

3 4

　Output

28

【输入输出样例2】

　Input

10 4

　Output

969844

【数据限制】

　　\(30\%\) 的数据满足：\(n≤10,m≤5\)
　　\(100\%\) 的数据满足：\(n≤10^{12} ,m≤10^8\)

【来源】

　　Mr.he