因为有T的限制，所以不难搞出来一个$O(T^3)$的暴力dp
但我没试 据说有30分？
正解的话显然是组合数学啦
首先$n,m$可能为负，但这并没有影响，
我们可以都把它搞成正的 即都看作向右上方走
那么可以想到真正有效的步都是向右或者向上走的 其它两个方向都是在起反作用
设u为向上走步数，d下，l左，r右
它们满足关系：
$r-l=m,u-d=n,T=u+d+l+r$
因为有效步数为$m+n$，所以$T-m-n$必为偶数
因为要保证剩下的步上下均分，左右均分
枚举$udlr$其中一个可得最终答案：
$ans=sum limits_{i=n,2|(i-n)}^{t-m} inom{t}{i} inom{i}{frac{i-n}{2}} inom{t-i}{frac{t-i-m}{2}}$
(从天皇那里copy过来的)
按道理讲本题应该结束了
但丧心病狂的出题人还要恶心你一下：模数可能不为质数
但也给出一定是几个互不相同的质数之积，从exLucas的魔爪中拯救了我们
之后就中国剩余定理就行了
把模数分解出质因子$p[i]$，对于每个因子都算一边答案，记为$ans[i]$
那么得到最后答案的过程，就相当于求解
$egin{cases} xequiv ans_1(mod p_1)\ xequiv ans_2(mod p_2)\ xequiv ans_3(mod p_3)\ ...\ xequiv ans_n(mod p_n)\ end{cases}$
这不裸的CRT么？板子打一遍就完事了。
扩欧都不用打，可以用前边的快速幂 结合费马小定理 解CRT里的同余方程。
//#define R #include<cstdio> #include<iostream> #include<cstring> #include<vector> #include<cmath> #define re register using namespace std; const int N=100005; typedef long long ll; int T,mod,n,m; ll fac[N],ans[1005]; vector<int> fact; int abss(int x) { return x<0?-x:x; } void divi(int x) { int sq=sqrt(x)+1; for(int i=2;i<=sq;i++) { if(x%i==0) { fact.push_back(i); while(x%i==0)x/=i; } if(x==1)break; } if(x!=1)fact.push_back(x); } ll qpow(ll a,ll b,ll p) { ll res=1;a=a%p; while(b) { if(b&1)res=res*a%p; a=a*a%p; b>>=1; } return res; } ll C(ll x,ll y,ll p) { if(x<y)return 0; return fac[x]*qpow(fac[y],p-2,p)%p*qpow(fac[x-y],p-2,p)%p; } ll lucas(ll x,ll y,ll p) { if(!y)return 1; return C(x%p,y%p,p)*lucas(x/p,y/p,p)%p; } void getfac(ll p) { fac[0]=1; for(int i=1;i<=T;i++) fac[i]=1LL*i*fac[i-1]%p; } int main() { scanf("%d%d%d%d",&T,&mod,&n,&m); n=abss(n),m=abss(m); divi(mod); int sz=fact.size(); for(re int now=0;now<sz;now++) { int p=fact[now];getfac(p); for(re int i=n;i<=T-m;i++) { if((i-n)&1||(T-i-m)&1)continue; ll res=1; res=res*lucas(T,i,p)%p*lucas(i,(i-n)/2,p)%p*lucas(T-i,(T-i-m)/2,p)%p; ans[now]=(ans[now]+res)%p; } } ll anss=0; for(re int i=0;i<sz;i++) { ll times=mod/fact[i]; ll ress=qpow(times,fact[i]-2,fact[i]); ress=(ress%fact[i]+fact[i])%fact[i]; anss=(anss+times*ress*ans[i])%mod; } cout<<(anss+mod)%mod<<endl; return 0; }