题目：P3746

参考了这篇题解。

jly的题解

问题：rt，指数 $b$ 为什么不能对 $p-1$ 取模？

也就是说，卷积幂不能用费马小定理么？求解答qwq

以下是我的代码。

#include<bits/stdc++.h>
#define sf scanf
#define pf printf
using namespace std;
typedef long long ll;
const int N=1e5+3;
int n,r,k,p;
struct node{
	int q[N];
}ans,a;
node operator *(node a,node b){
	node c;
	memset(c.q,0,sizeof(c.q));
	for(int i=0;i<k;++i){
		for(int j=0;j<k;++j){
			int m=(i+j)%k;
			c.q[m]=(c.q[m]+1ll*a.q[i]*b.q[j])%p;
		}
	}
	return c;
}
int main(){
	sf("%d%d%d%d",&n,&p,&k,&r);
	ll b=1ll*n*k;
	if(k==1){
		a.q[0]=2%p;
	}else{
		a.q[0]=a.q[1]=1;
	}
	ans.q[0]=1;
//	b%=p-1;加上这句会变成 70pts ，不加就 AC 
	while(b){
		if(b&1) ans=ans*a;
		a=a*a;
		b>>=1;
	}
	pf("%d\n",ans.q[r]);
}