Expected Complexity of a Random Article

Mivik has a keyboard with m different keys, each corresponding to a distinct character. Since he cannot write articles, he randomly and uniformly presses keys exactly n times to produce an article.

The complexity of an article is defined as the number of non‐empty substrings which are essentially different. Two substrings are said to be essentially different if either their lengths differ or there exists a position at which their characters differ. For example, the article abaa has complexity 8 because its non‐empty essentially different substrings are: a, b, ab, ba, aa, aba, baa, and abaa.

Mivik now wonders what the expected complexity of his article is. In other words, if he types a random article of length n (with each key pressed uniformly at random from the m keys), what is the expected number of different non‐empty substrings in it? Since Mivik dislikes odd decimals, you are required to output the expected complexity modulo \(10^9+7\).

Note on the approach: One may observe that the number of distinct substrings of a given article can be written as the sum over all possible non‐empty candidate substrings (of lengths \(1\) to \(n\)) of the indicator that the candidate appears in the article. By linearity of expectation the answer is

[ E = \sum_{l=1}^{n} \Biggl(;m^l \cdot \Bigl(1 - \Bigl(1-\frac{1}{m^l}\Bigr)^{(n-l+1)}\Bigr)\Biggr), \mod (10^9+7). ]

This formula is exact for those candidate substrings that do not overlap with themselves (which is true for almost all candidates when \(m>1\)). In the special case when \(m=1\) the answer is simply \(n\) (since the article is just a repetition of one character and its distinct substrings are a, aa, …, up to length \(n\)).

inputFormat

The input consists of two space‐separated integers m and n, where m is the number of distinct keys on the keyboard and n is the number of key presses.

Constraints:

• \(1 \le m \le 10^9\)
• \(1 \le n \le 10^5\)

outputFormat

Output one integer, the expected complexity of the article modulo \(10^9+7\).

sample

2 4

706250000