Background

The testdata for this problem is not official.

Official testdata (that can be uploaded here) is being collected.

Official testdata (that cannot be uploaded here): https://www.luogu.com.cn/training/499869

Unofficial testdata download: https://scg3.piaoztsdy.cn/training/69bce235a7cf509104565c83

Problem Description

Xiao Keke had a dream. In the dream, there are $n$ candies from left to right. Each candy has a color, represented by a positive integer in $[1, m]$.

Each time, Xiao Keke chooses two candies with the same color, and eats them as well as all candies between them.

Xiao Keke remembers that for the candy sequence in the dream, there exists a way to eat all candies.

After waking up, Xiao Keke forgot what the candy sequence in the dream was. Can you help her count, among all $m^n$ possible candy sequences, how many sequences could have appeared in her dream (that is, there exists a way to eat them all)?

Since the answer may be very large, you only need to output it modulo $10^9+7$.

Input Format

One line with two positive integers $n, m$.

Output Format

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

3 2

4

6 3

405

30 2

73741759

100 100

566607183

Hint

Explanation for Sample 1

There are $4$ valid candy sequences in total: $[1,1,1]$, $[1,2,1]$, $[2,1,2]$, $[2,2,2]$.

Constraints

For $10\%$ of the testdata, $n \le 6$, $m \le 4$.

For $20\%$ of the testdata, $n \le 6$, $m \le 100$.

For another $30\%$ of the testdata, $n \le 50$, $m \le 2$.

For $70\%$ of the testdata, $n, m \le 100$.

For $80\%$ of the testdata, $n, m \le 1000$.

For $100\%$ of the testdata, $1 \le n \le 3000$, $1 \le m \le 10^9$.

Translated by ChatGPT 5