题目描述

给定 $n$ 个花瓣和 $1$ 个花蕊，共有 $m$ 种颜料。要求:

• 相邻的花瓣颜色不同;

• 每个花瓣和花蕊的颜色不同。

求满足条件的染色方案数，结果对 $10^9 + 7$ 取模。

这幅画中的花由 $5$ 个花瓣和中间的花蕊组成

输入格式

两个整数 $n$ 和 $m$。

输出格式

一个整数，表示方案数模 $10^9 + 7$ 的结果。

样例 1 输入

4 3

样例 1 输出

6

样例 1 解释

设三种颜色为红、黄、蓝。如图所示，一共六种方案。

样例 2 输入

3 4

样例 2 输出

24

数据范围

• $20\%$的数据保证$n≤2, m≤2$

• $60\%$的数据保证$n≤6, m≤6$

• $70\%$的数据保证$n≤1000, m≤1000$

• $80\%$ 的数据保证 $n ≤ 100000, m ≤ 100000$

• $90\%$的数据保证$n≤10^9, m≤10^9$

• $100\%$ 的数据保证 $n ≤ 10^{100000}$, $m ≤ 10^{100000}$