P10375 [AHOI2024 Junior / USTC Guochuang Cup Junior 2024] Counting

**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): ** **Unofficial testdata download: **

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

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

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

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