Background

Mivik aspires to be a great writer.

Problem Description

Mivik has a keyboard with \( m \) distinct keys, corresponding to \( m \) different characters. Since Mivik doesn't know how to write articles, he randomly presses \( n \) keys with equal probability, creating an article.

Mivik defines the complexity of an article as the number of all non-empty, distinct substrings. Two strings are considered distinct if they have different lengths or if any character in the strings differs. For example, the complexity of the article abaa is 8, as it has the following non-empty, distinct substrings: a, b, ab, ba, aa, aba, baa, abaa.

Mivik now wants to know the expected complexity of the article. Since Mivik dislikes irregular decimals, you only need to output the expected complexity modulo \( 10^9 + 7 \).

Input Format

A single line containing two integers \( n \) and \( m \), as described in the problem statement.

Output Format

A single integer representing the answer modulo \( 10^9 + 7 \).

Sample Input and Output

Sample Input #1

2 2

Sample Output #1

500000006

Sample Input #2

3 3

Sample Output #2

5

Sample Input #3

3 4

Sample Output #3

250000007

Notes

Sample Explanation

Sample 1: Assuming the characters on the keyboard are a and b, the possible articles are aa, ab, ba, bb, with complexities 2, 3, 3, and 2 respectively. Therefore, the answer is \(\frac{2+3+3+2}{4}=\frac{5}{2}\), which modulo \( 10^9 + 7 \) is 500000006.

Data Range

For all data, \( 1 \le n \le 20 \) and \( 1 \le m \le 5 \cdot 10^6 \).

Subtask 1 (10 pts): Satisfies \( 1 \le n, m \le 7 \).

Subtask 2 (20 pts): Satisfies \( 1 \le n \le 5 \).

Subtask 3 (20 pts): Satisfies \( 1 \le n \le 10 \).

Subtask 4 (50 pts): No special restrictions.

见题面 Input 部分

见题面 Output 部分