这期神了

$\infty$是吓唬你的喵，实际上只要算到$n$就可以。

组合数无从下手，考虑它的实际意义。

发现$k$和$r$比较小，因此考虑将其作为状态的一部分。

原式可以理解为，在$nk$个物品中选$x$个物品，使得$x \: mod \: k=r$。

记$dp_{i,j}$表示处理了$i$个物品，选的个数$mod\:k$为$j$。

这里我认为，把余数为$0$看作余数为$k$好像更有道理。

柿子:

$$dp_{i-1,j}+dp_{i-1,j-1} \rightarrow dp_{i,j}\:\: (j \neq 1) \\ dp_{i-1,j}+dp_{i-1,k} \rightarrow dp_{i,j}\:\: (j = 1) $$

然后我们发现对于每一个$i$都是由$i-1$递推而来，所以可以矩阵快速幂。转移矩阵容易得出，具体的看代码吧。注意特判$k=1$。

复杂度$O(k^3\log{(nk)})$

原题：P3746 [六省联考 2017] 组合数问题

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define F first
#define S second
#define mkp make_pair
#define psb push_back
const int mod=1e9+7;
int n,p,k,r;
int qpow2(int y){
	int sum=1,x=2;
	while(y){
		if(y&1) sum=sum*x%p;
		x=x*x%p;
		y>>=1;
	}return sum;
}

int ans[55][55],a[55][55],to[55][55];
void mul1(){
	for(int i=1;i<=k;i++){
		for(int j=1;j<=k;j++) to[i][j]=0;
	}
	for(int i=1;i<=k;i++){
		for(int j=1;j<=k;j++){
			for(int mm=1;mm<=k;mm++){
				to[i][j]=(to[i][j]+ans[i][mm]*a[mm][j])%p;
			}
		}
	}for(int i=1;i<=k;i++){
		for(int j=1;j<=k;j++){
			ans[i][j]=to[i][j];
		}
	}
}void mul2(){
	for(int i=1;i<=k;i++){
		for(int j=1;j<=k;j++) to[i][j]=0;
	}
	for(int i=1;i<=k;i++){
		for(int j=1;j<=k;j++){
			for(int mm=1;mm<=k;mm++){
				to[i][j]=(to[i][j]+a[i][mm]*a[mm][j])%p;
			}
		}
	}for(int i=1;i<=k;i++){
		for(int j=1;j<=k;j++){
			a[i][j]=to[i][j];
		}
	}
}
void qpow(int y){
	for(int i=1;i<=k;i++) ans[i][i]=1;
	for(int i=1;i<=k;i++){
		if(i==1) a[i][1]=a[i][k]=1;
		else a[i][i-1]=a[i][i]=1;
	}while(y){
		if(y&1) mul1();
		mul2();
		y>>=1;
	}
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
//	system("fc my.out ex.out");return 0;
//	freopen("ex.in","r",stdin);
//	freopen("my.out","w",stdout);
	cin>>n>>p>>k>>r;
	if(r==0) r=k;
	if(k==1){
		cout<<qpow2(n*k);
		return 0; 
	}
	qpow(n*k);
	cout<<ans[r][k];
	return 0;
}