P1316 Mivik Writes a Book

Mivik wants to become a great writer.

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$.

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

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

### 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