题目描述

$n$ 个点排成一列，需要给每个点一个颜色，颜色有 $m$ 种。请问有多少种方法，能使任意相邻两个点的颜色均不相同？

输入格式

两个整数：表示 $n$ 与 $m$

输出格式

单个整数：表示染色方案数模 $1,000,000,007$ 的余数。

3 2

2

样例解释 1

合法的染色方案有：{1,2,1} {2,1,2}

数据范围

• 对于 $30\%$ 的数据，$1 \leq n,m \leq 10$
• 对于 $60\%$ 的数据，$1 \leq n,m \leq 10000$
• 对于 $100\%$ 的数据，$1 \leq n \leq 10^{15}$
• $1 \leq m \leq 10^9$