题目背景

Mivik 想当大作家。

题目描述

Mivik 的键盘上有 $m$ 个不同的按键，对应着 $m$ 个不同的字符。由于 Mivik 不会写文章，所以他只好等概率随机乱按了 $n$ 个键，打出了一篇文章。

Mivik 定义一篇文章的复杂度是这篇文章所有非空本质不同子串的数目。我们认为两个字符串本质不同当且仅当它们的长度不同或者它们有任意一位上的字符不同。例如，文章 abaa 的复杂度是 8，因为它一共有 a、b、ab、ba、aa、aba、baa、abaa 这 8 个非空的本质不同子串。

Mivik 现在想知道，这篇文章期望的复杂度是多少。由于 Mivik 不喜欢奇形怪状的小数，你只需要输出期望的复杂度对 $10^9+7$ 取模后的值。

输入格式

一行两个整数 $n$ 和 $m$，意义见题目描述。

输出格式

一行一个整数，代表答案对 $10^9+7$ 取模后的值。

2 2

500000006

3 3

5

3 4

250000007

提示

样例解释

样例一：假设键盘上的字符分别为 a 和 b，那么可能打出来的文章一共有 aa、ab、ba、bb 四种，它们的复杂度分别为 2、3、3、2，因此答案为 $\frac{2+3+3+2}{4}=\frac{5}{2}$，对 $10^9+7$ 取模后得到 500000006。

数据范围

对于全部数据，有 $1\le n\le 20$，$1\le m\le 5\cdot 10^6$。

Subtask 1 (10 pts)：满足 $1\le n, m\le 7$。

Subtask 2 (20 pts)：满足 $1\le n\le 5$。

Subtask 3 (20 pts)：满足 $1\le n\le 10$。

Subtask 4 (50 pts)：无特殊限制。