[PA2021] Od deski do deski
看似简单，实则考察的是选手的 DP 基本功，如果像我一样只会观察性质就做不出来这题。
性质：合法的序列一定是由若干个子串按照顺序拼起来的，其中每个子串的开头和结尾是一样的。
然后的想法就是设 \(f_i\) 表示子串 \(i\) 能一次消掉的方案数，然后就会一直算重没法做。
这种感觉就像当年 csp，就是做计数 dp 内味。
从头开始，考虑更好地描述一个序列是否合法，有一个 dp：设 \(f_i\) 表示 \([1, i]\) 是否合法，值域为 \([0,1]\)，然后可以枚举最后一段转移。
有没有什么办法可以忽略原序列的信息就转移这个东西呢？有！直接设 \(j\) 表示有 \(j\) 种数填进去就能使得 \(f_i\) 合法。这样我们就不用关心原序列的信息了。
考虑在此基础上可以设计原题的状态：\(f_{i,j,0/1}\) 表示长度为 \(i\) 的序列，有 \(j\) 种数填入后就变合法，当前是否合法的方案数，转移是平凡的。
const int N = 3010;
int n, m;
int f[N][N][2];
const int P = 1e9 + 7;
void add(int &x, int y) {
(x += y) >= P ? x -= P : 0;
}
int main() {
read(n, m);
f[0][0][1] = 1;
for(int i = 1; i <= n; ++i) {
for(int j = 0; j < i; ++j) {
add(f[i][j + 1][0], 1ll * f[i - 1][j][1] * (m - j) % P);
add(f[i][j][1], 1ll * f[i - 1][j][1] * j % P);
add(f[i][j][1], 1ll * f[i - 1][j][0] * j % P);
add(f[i][j][0], 1ll * f[i - 1][j][0] * (m - j) % P);
}
}
int ans = 0;
for(int i = 0; i <= n; ++i)
add(ans, f[n][i][1]);
printf("%d\n",ans);
}