鉴定为质量非常高的题目，我觉得再给我一天我也未必能往这个方向想。

首先我必须留出来的空隙是 $\sum max(p_i,p_{i+1})$， 因为相邻的两头奶牛距离为两者高度的较大值。

设上述和为 $S$ ，我们只需要对于每一个和统计有多少 $1-n$ 的排列满足，再乘上一个组合数就行了。

然后这个 $dp$ 我想了将近一天，看了题解后发现真的十分巧妙。

他的设法是 $f_{i,j,k}$ 表示当前我放了前 $i$ 个数，这 $i$ 个数构成了 $j$ 个连续的段落，然后他们的总贡献为 $k$。

我们如何理解这样设状态的组合意义呢？上述设计状态妙在他处理时的灵活性，正常如果我们只是考虑把 $i$ 塞进序列当中，处理起来是很困难的，因为我们不知道和 $i$ 相邻的数是谁。但是这样设计我们就不需要知道 $i$ 与谁相邻，我们只要考虑 $i$ 是自己独立形成一个连续段，还是与前面某一个形成一个新的连续段，还是他拼接了两个不同的连续段即可。

状态转移方程大家可以直接看我的代码，然后我们要处理的其实还有一个棘手的问题，就是我最后乘上的组合数，在固定 $S$ 时应该是 $C(m-S-1+n,n)$，然后我们一看范围发现 $m ,p\leq 10^9$，还没有 $p$ 规定是不是质数。

但是有一点，我们的 $n$ 是特别小的，所以我们可以暴力求他的组合数。

还有一点，就是如果存在和 $p$ 不互质的部分我们要单独进行处理，因为这一部分在模 $p$ 下不存在逆元，不过我们发现这一部分一定不超过$100$ ，于是可以直接存下来处理。

我个人认为这个逆天 $dp$ 就有紫的难度了，后面这一个小处理本身也有黄到绿的难度，综合评分紫色。

转移方程和一些实现细节在代码当中

CODE

#include<bits/stdc++.h>
#define ll long long
//#define int long long
using namespace std;
int f[2][105][10005],mod;
// 这个题卡空间，必须开int+滚动数组 
int countt[105];
inline ll Pow(ll x,ll y){
	ll ans=1;
	while(y){
		if(y&1)ans=ans*x%mod;
		x=x*x%mod;y>>=1;
	}return ans;
}int pr[40]={0,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97};
//直接把100以内的素数列了出来 
inline ll C(int n,int m){
	memset(countt,0,sizeof countt);
	ll res=1;
	if(n<m)return 0;
	for(int i=n; i>=n-m+1; i--){
		int d=i;
		for(int j=1; j<=25&&pr[j]<=d; j++){
			while(d%pr[j]==0)countt[j]++,d/=pr[j];
		}res=res*d%mod;
	}
	for(int i=1; i<=m; i++){
		int d=i;
		for(int j=1; j<=25&&pr[j]<=i; j++){
			while(d%pr[j]==0)countt[j]--,d/=pr[j];
		}
	}
	for(int i=1; i<=25; i++)res=res*1ll*Pow(pr[i],countt[i])%mod;
	return res;
}inline int Mod(ll a,int b){//卡时间，取模太慢了 
	a+=b;
	if(a>mod)a-=mod;
	return a;
}
signed main(){
	int n,m;
	scanf("%d%d%lld",&n,&m,&mod);
	f[1][1][0]=1;
	bool now=1;
	for(int i=2; i<=n; i++){
		now^=1;
		memset(f[now],0,sizeof f[now]); 
		for(int j=1; j<=i; j++){
			for(int k=0; k<=(i-1)*(i-1); k++){
				f[now][j+1][k]=Mod(f[now^1][j][k]*1ll*(j+1)%mod,f[now][j+1][k]);
				//如果自成一个连续段，他可以放在(j+1)个位置，自行画图理解 
				f[now][j][k+i]=Mod(f[now^1][j][k]*2ll*j%mod,f[now][j][k+i]);
				//如果和别人构成连续段，每一个之前的连续段的前后都可以放，所以是2*j 
				if(j>1)f[now][j-1][k+i*2]=Mod(f[now^1][j][k]*1ll*(j-1)%mod,f[now][j-1][k+2*i]);
				//如果我要连接两个不同的连续段，可以有(j-1)个放置的位置。 
			}
		}
	}ll ans=0;
	for(int i=1; i<=n*n; i++){
		if(f[now][1][i]){
			ll cnt=f[now][1][i];
			ans=(ans+C(m-i-1+n,n)*1ll*cnt%mod)%mod;
		}
	}
	cout<<ans;
	return 0;
} /*

*/