当前没有测试数据。

幸运的串

题目描述

$A$君喜欢收集特殊的字符串，特别是那些能给他带来幸运的串。

$A$君认为一个串是幸运串当且仅当这个串包含长度大于$1$的回文子串。

$A$君想知道对于长度恰好为$n$且字符集大小为$m$的所有字符串中（字符集中字符不一定都要用上），有多少个不同的幸运串呢？

最后的结果可能很大，$A$君只想知道答案对$10^{9}+7$取模后的值，请你帮助他。

输入格式

一行两个整数$n$，$m$。

输出格式

仅一个整数表示答案。

数据范围与提示

• 对于$30\%$的数据，$n$，$m \leq 7$；
• 对于$60\%$的数据，$n$，$m \leq 10^{7}$；
• 对于$100\%$的数据，$1 \leq n$，$m \leq 10^{18}$。

样例

3 3

21

4 4

208

1145141919810 1919810114514

411445926