前缀和优化 dp，把一个 k-X-1-Y 拆成两部分做的。求调。

#include <bits/stdc++.h>
using namespace std;
const int N = 3e3 + 5;
int n, k, p, ans, dp[3][2][N];
int pres[3][2][N], prei[3][2][N]; 
int g3(int x) { return (x % 3 + 3) % 3; }
int g2(int x) { return (x % 2 + 2) % 2; }
void solve() {
	cin >> n >> k >> p; dp[0][0][0] = 1;
	for(int i = 1;i <= n + 1; ++i) {
		
		for(int j = 0;j <= 1; ++j) {
			pres[g3(i - 1)][j][0] = dp[g3(i - 1)][j][0];
			for(int X = 1;X <= k; ++X) 
				pres[g3(i - 1)][j][X] = (dp[g3(i - 1)][j][X] + pres[g3(i - 1)][j][X - 1]) % p, 
			prei[g3(i - 1)][j][X] = (dp[g3(i - 1)][j][X] * X % p + prei[g3(i - 1)][j][X - 1]) % p; 
		}
			
		for(int j = 0;j <= 1; ++j) {
			for(int X = 0;X <= k; ++X) {
				int Ymax = k - X - 1; // Z > X + Y, choose k - X - 1 - Y 个 
//				cout << X << " " << Ymax << "\n";
				dp[g3(i)][j][X] = pres[g3(i - 1)][j][k];
//				cout << g3(i) << " " << g3(i - 2) << " - " << g2(j) << " " << g2(j - 1) << "\n";
				if(Ymax < 0 or i == 1) continue ;
				int dp1 = Ymax * pres[g3(i - 2)][g2(j - 1)][Ymax] % p;
				dp[g3(i)][j][X] = (dp[g3(i)][j][X] + dp1) % p;
				dp[g3(i)][j][X] = (dp[g3(i)][j][X] - prei[g3(i - 2)][g2(j - 1)][Ymax]) % p;
			} 
		}
	} 
	ans = (dp[g3(n + 1)][0][0] - dp[g3(n + 1)][1][0]) % p;
	cout << (ans + p) % p << "\n";
}
/*
num 表示有几个不满足   则 X+Y<=nowchoose 
dp[i&1][num&1][X] = \sum dp[i-1&1][num-1&1][Y] * (k - X - 1 - Y)
维护 sum dp[i][num] 
，以及 sum dp[i][num]*i 即可 
*/
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    while(T--) solve();
    return 0;
}