终于过了。

首先考虑 dp，一个很 natural 的想法是设 $dp_{i,j}$ 表示填了 $1-i$ 的排列，其中最后一个填 $j$ 的方案数，这能转移吗？

感觉不行啊，但是实际上是对的。

考虑下降的情况，加入我们当前填的是 $x$，可以理解为把前面的所有 $\geq x$ 的数全部 $+1$，再将我放入最后，上升同理。

前缀和优化就做完了。

#include<iostream>
#include<cstdio>
using namespace std;
bool Test_MLE_start;
constexpr int N=4323;
int _=1,n,mod,ans=0,dp[N][N],g[N][N];
inline int reads(){
	int c=getchar(),x=0,f=1;
	while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}
	while(isdigit(c)){x=(x<<3)+(x<<1)+(c^'0');c=getchar();}
	return x*f;
}inline void files(){
	freopen("std.in","r",stdin);
	freopen("std.out","w",stdout);
}inline void clr(){
//	Don't forget!

}bool Test_MLE_end;
signed main(){
//	printf("%lf Mb\n",(&Test_MLE_end-&Test_MLE_start-1)/1024.0/1024.0);
//	files();
//	_=reads();
	while(_--){
		clr();n=reads(),mod=reads();
		g[1][1]=dp[1][1]=1;
		for(int i=2;i<=n;i++){
			for(int j=1;j<=i;j++){
				if(!(i&1)) dp[i][j]=g[i-1][j-1];
				else dp[i][j]=(g[i-1][i-1]-g[i-1][j-1]+mod)%mod;
				g[i][j]=(g[i][j-1]+dp[i][j])%mod;
			}
		}
		for(int i=1;i<=n;i++) ans=(ans+dp[n][i])%mod;
		printf("%lld\n",(ans<<1)%mod);
	}return 0;
}

纯唐题目我怎么不会。