Problem Description

Xiaoke had a dream where there were \( n \) candies arranged from left to right, each with a color represented by a positive integer in the range \([1, m]\).

Xiaoke would choose two candies of the same color and eat them along with all the candies in between.

Xiaoke remembers that for the sequence of candies in her dream, there was a way to eat all of them.

After waking up, Xiaoke forgot the sequence of candies in her dream. Can you help her determine how many out of the \( m^n \) possible sequences of candies could have been in her dream (i.e., there exists a way to eat all of them)?

Since the result might be very large, you only need to find the remainder when it is divided by \( 10^9 + 7 \).

Input Format

A single line containing two positive integers \( n \) and \( m \).

Output Format

A single line containing a non-negative integer, representing the answer modulo \( 10^9 + 7 \).

Sample Input and Output

Sample Input #1

3 2

Sample Output #1

4

Sample Input #2

6 3

Sample Output #2

405

Sample Input #3

30 2

Sample Output #3

73741759

Sample Input #4

100 100

Sample Output #4

566607183

Notes

Sample 1 Explanation

There are 4 valid candy sequences: \([1,1,1], [1,2,1], [2,1,2], [2,2,2]\).

Data Range

For 10% of the data, \( n \le 6 \), \( m \le 4 \).

For 20% of the data, \( n \le 6 \), \( m \le 100 \).

For another 30% of the data, \( n \le 50 \), \( m \le 2 \).

For 70% of the data, \( n, m \le 100 \).

For 80% of the data, \( n, m \le 1000 \).

For 100% of the data, \( 1 \le n \le 3000 \), \( 1 \le m \le 10^9 \).

见题面 Input 部分

见题面 Output 部分