3111: lucky
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：37
解决：14
题目描述
A君喜欢收集特殊的字符串，特別是那些能给他带来幸运的串。 A君认为一个串是幸运串当且仅当这个串包含长度大于1的回文子串。 A君想知道对于长度恰好为n且字符集大小为m的所有字符串中（字符集中字符不一定都要用 上)，有多少个不同的幸运串呢？ 最后的结果可能很大，A君只想知道答案对10^9 + 7取模后的值，请你帮助他
输入
仅一行两个整数n,m，表示字符串长度和字符集大小
输出
仅一行一个整数表示答案。
样例输入 复制
3 3 样例输出 复制
21提示
in
4 4
out
208
30% n, m <=7
60% n, m<= 10^7
100% n, m <= 10^18