该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

有 n 块积木排成一排，小爱需要给每块积木染色，颜色有 m 种，请问有多少种方法，能使相邻两块积木的颜色均不相同？

Format

Input

输入两个正整数n,m

Output

输出满足条件的方案数模10^9+7的结果

Samples

3 2

2

Limitation

对于 30% 的数据，1≤n,m≤10 对于 60% 的数据，1≤n,m≤1e4

对于 100% 的数据，1≤n≤1e15 ,1≤m≤1e9