RT，

#include<iostream>
#define int long long
using namespace std;
int n,p,ans;
const int N=5e3+5;
int f[N];
int c[N][N];
signed main(){
	cin>>n>>p;
	f[0]=1;
	for(int i=0;i<=n;i++){
		c[i][0]=1;
		c[i][i]=1;
	}
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			c[j][i]=(c[j-1][i-1]+c[j-1][i])%p;
		}
	}
	for(int i=1;i<=n*2;i++) f[i]=f[i-1]*i%p;
	for(int i=n/2+1;i<=n;i++){
		int l=max(0ll,n-i-1);
		for(int j=0;j<=l;j++){
			ans+=min(i-1,n-i+1-n%2)*c[l][j]%p*f[i+j-2]%p;
			if(ans>p) ans-=p;
		}
	}
	cout<<ans*n%p<<endl;
	return 0;
}

复杂度 $O(n^2)$ 常数约为 $\frac{1}{8}$

没过 $5000$ /kk