RT，时间复杂度大概为$O(\frac{m^2}{log_2m})$ 问一下有没有什么好方法卡常或者优化？

Code:

#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define mod 998244353
//save
map<int,int> primMon;
map<int,int> primSon;
int n,m,k,p,jc[100100],prim[500000],primtot,all=1;
bool pp[101000];
void shai(){
	for(int i=2;i<=m;i++){
		if(!pp[i]){
			pp[i]=1;
			prim[++primtot]=i;
			for(int j=i;j*i<=m;j++){
			    pp[i*j]=1;
			}
		}
	}
}inline int qp(int a,int k){
    int now=1; 
    while(k){
    	if(k&1){
    		now=(a*now)%p;
		}a=(a*a)%p;
		k>>=1;
	}return now%p;
}inline void /*Decomposition*/Dec(int now,bool which){
    if(which==1){
    	for(register int i=1;i<=primtot&&now>=prim[i];i++){
    		while(now%prim[i]==0&&now!=0){
    			primMon[prim[i]]++;
    			now/=prim[i];
			}
		}
	}else{
		for(register int i=1;i<=primtot&&now>=prim[i];i++){
	  		while(now%prim[i]==0&&now!=0){
    			primSon[prim[i]]++;
    			now/=prim[i];
			}
		}if(now>=prim[primtot]){
			all=(all*now)%p;
		}
	}return;
}signed main(){
	cin>>n>>m>>k>>p;
	shai();
	for(int i=1;i<=m;i++){
		Dec(i,1);
		Dec(i+k-1,0);
	}for(int i=1;i<=primtot;i++){
		primSon[prim[i]]-=primMon[prim[i]];
	    all=(all*qp(prim[i],primSon[prim[i]]))%p;
	}int ans=1;
	//cout<<all<<' ';
	for(int i=0;i<=n-1;i++){
	    ans=(ans*((all-i+p)%p))%p;
	}cout<<ans;
}
//dp[0][0]=1,dp[i][j]=dp[i][j=-1]+dp[i-1][j];
//C^{m-1}_{m+k-1};
//(m+k-1)!/(m-1)!(k)!
// Π^{m}_i=0 i+k/i;