platelett 讲的题欸。
先考虑给定序列怎么做。
问题显然可以转化为能否将序列分成若干个子序列。令 \(f_i\) 表示前 \(i\) 个数是否能够删完。则有 \(f_i = f_j[a_i=a_j, f_j=1]\)。这样是 \(n^2\) 的，也无法扩展至所有数列的情况。
建立一个辅助数组 \(g\) 表示是否存值为 \(i\) 的数前的值都被删完。则有 \(f_i = g_{a_i}\)，\(g_{a_i} \mid=f_{i-1}\)。
设 \(h_{i}\) 表示长度为 \(i\) 的数列能被删完的方案数。但这样显然是无法转移的。
发现影响能否删完的 \(f\) 只有三个影响的地方 \((f_i, g_i)\)，这个 \(f\) 是可以在计算时直接用一个变量存下的，\(a_i\) 是不需要存的。\(g\) 是一个数组是不好存的。但是发现实际上 \(h\) 转移的时候只需要知道 \(g\) 有多少个地方是 \(1\)，这样就做完了。
定义 \(h_{i,j,0/1}\) 表示长度为 \(i\) 的数列中，\(g\) 中有 \(j\) 个 \(1\) 且序列合法 / 不合法的情况有多少种。转移方程是显然的了，即 \(h_{i,j,0}=(h_{i-1,j,0}+h_{i-1,j,1})\times j\)，\(h_{i,j,1} = h_{i-1,j,0} \times(m-j)+h_{i-1,j-1,1}\times (m-j+1)\)。
最后的答案就是 \(\sum h_{n,i,0}\)。
时空复杂度均为 \(\mathcal{O}(n^2)\)。
代码：
const int N = 3e3 + 10, mod = 1e9 + 7;
int add(int x, int y){ return (x + y) % mod; }
int n, m;
int f[N][N][2];
int main() {
cin >> n >> m;
f[1][1][0] = m;
for (int i = 2; i <= n; ++i) for (int j = 1; j <= n; ++j) {
f[i][j][0] = add(f[i - 1][j][0] * 1ll * (m - j) % mod, j ? f[i - 1][j - 1][1] * 1ll * (m - j + 1) % mod : 0),
f[i][j][1] = add(f[i - 1][j][0], f[i - 1][j][1]) * 1ll * j % mod;
}
int ans = 0;
for (int i = 1; i <= n; i++)
ans = add(ans, f[n][i][1]);
cout << add(ans, mod) << "\n";
return 0;
}