数据强度有待提高

struct ds{
	int s[N],p,k,r;
	int ca(int n){
		if(n<p) return s[n];
		return ca(n/p)*qp(s[p-1],n/p,r)%r*s[n%p]%r;
	}
	int re(int x){
		if(x<p) return 0;
		return re(x/p)+(x/p);
	}
	int sec(int n,int m,int x,int y){
		p=x,k=y,r=qp(x,y,inf);
		int c=re(n)-re(m)-re(n-m);
		s[0]=1;
		for(int i=1;i<r;i++){
			s[i]=s[i-1];
			if(i%p) s[i]=s[i]*i%r;
		}
		int ans=qp(p,c,r);
		int d1=ca(n);
		int d2=ca(n-m);
		int d3=ca(m);
		return ans*d1%r*inv(d2,r)%r*inv(d3,r)%r;
	}
};

struct ds{
	int s[N],p,k,r;
	int ca(int n){
		if(n<p) return s[n];
		return ca(n/p)*qp(s[p-1],n/p,r)%r*s[n%p]%r;
	}
	int re(int x){
		if(x<p) return 0;
		return re(x/p)+(x/p);
	}
	int sec(int n,int m,int x,int y){
		p=x,k=y,r=qp(x,y,inf);
		int c=re(n)-re(m)-re(n-m);
		s[0]=1;
		for(int i=1;i<p;i++){
			s[i]=s[i-1];
			if(i%p) s[i]=s[i]*i%r;
		}
		int ans=qp(p,c,r);
		int d1=ca(n);
		int d2=ca(n-m);
		int d3=ca(m);
		return ans*d1%r*inv(d2,r)%r*inv(d3,r)%r;
	}
};

3 1 4

3