Description

Mivik’s keyboard has $m$ different keys, corresponding to $m$ different characters. Since Mivik cannot write articles, he randomly presses $n$ keys with equal probability, producing an article.

Mivik defines the complexity of an article as the number of all non-empty essentially different substrings in the article. We consider two strings essentially different if and only if their lengths are different, or they differ at any character position. For example, the complexity of the article abaa is 8, because it has 8 non-empty essentially different substrings: a, b, ab, ba, aa, aba, baa, abaa.

Now Mivik wants to know the expected complexity of this article. Since Mivik does not like strange-looking decimals, you only need to output the expected complexity modulo $10^9+7$.

Input Format

One line with two integers $n$ and $m$, as described above.

Output Format

One line with one integer, representing the answer modulo $10^9+7$.

2 2

500000006

3 3

5

3 4

250000007

Hint

Sample Explanation

Sample 1: Suppose the characters on the keyboard are a and b. Then there are four possible articles: aa, ab, ba, bb. Their complexities are 2, 3, 3, 2 respectively, so the answer is $\frac{2+3+3+2}{4}=\frac{5}{2}$, which modulo $10^9+7$ equals 500000006.

Constraints

For all data, $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): No additional constraints.

Translated by ChatGPT 5