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

题目描述

有 $N$ 天需要用餐，每天可以从 $M$ 种套餐中选择一种。请问有多少种配餐方法，能使任意相邻两天所配套餐不同？

由于答案可能很大，输出方案数模 $1,000,000,007$ 的余数。

输入格式

两个整数：表示 $N$ 与 $M$。

输出格式

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

3 2

2

样例解释

合法的方案有：${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}$