P8386 [PA 2021] Od deski do deski

Given $n$ and $m$, find the number of sequences of length $n$ that satisfy the following conditions: 1. Each element is between $[1, m]$. 2. One operation is defined as deleting an interval of length at least $2$ whose two endpoints are equal. The sequence must be able to be completely deleted using several operations. Output the answer modulo $10^9 + 7$.

The first line contains two positive integers $n$ and $m$.

Output one integer, which is the result modulo $10^9 + 7$.

### Sample Explanation The valid sequences are: $[1,1,1,1]$ $[1,1,2,1]$ $[1,1,2,2]$ $[1,2,1,1]$ $[1,2,2,1]$ $[2,1,1,2]$ $[2,1,2,2]$ $[2,2,1,1]$ $[2,2,1,2]$ $[2,2,2,2]$ ### Constraints $1 \le n \le 3000$，$1 \le m \le 10^9$。 Translated by ChatGPT 5