$n$这么大，一眼矩阵快速幂。

从第$i$列转移到第$i+1$列，每一列有$32$种状态，暴力枚举，判断能否转移，转移矩阵就搞好了。

初始化用黑白黑白黑白，能转移到所有情况。

注意高精。

没了

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int m,p,s,Ans;
char t[105];
struct mat{
	int c[32][32];
	void clear(){memset(c,0,sizeof(c));}
	mat operator *(const mat &o)const{
		mat r;
		r.clear();
		for(int i=0;i<s;i++)
		for(int k=0;k<s;k++)
		for(int j=0;j<s;j++)
		if(c[i][k]&&o.c[k][j])
		r.c[i][j]=(r.c[i][j]+c[i][k]*o.c[k][j])%p;
		return r;
	}
}f,g;
struct BigInt{
	int c[105],len;
	void rad(){
		scanf("%s",t);
		len=strlen(t);
		for(int i=0;i<len;i++)c[i]=t[i]-48;
		reverse(c,c+len);
	}
	bool pd(){return len>1||c[0];}
	void div(){
		int tmp=0;
		for(int i=len-1;i>=0;i--){
			tmp=tmp*10+c[i];
			c[i]=tmp>>1;
			tmp&=1;
		}
		if(!c[len-1])len--;
	}
	bool je(){return c[0]&1;}
}n;
int main(){
	n.rad();scanf("%d%d",&m,&p);
	s=1<<m;
	for(int i=0;i<s;i++)
	for(int j=0;j<s;j++){
		int tmp=1;
		for(int k=0;k<m-1;k++){//注意-1
			if(((i>>k)&(i>>(k+1))&(j>>k)&(j>>(k+1)))&1){tmp=0;break;}//2*2黑
			if(!(((i>>k)|(i>>(k+1))|(j>>k)|(j>>(k+1)))&1)){tmp=0;break;}//2*2白
		}
		g.c[j][i]=tmp;
        //转移矩阵
	}
	int tmp=0;
	for(int i=0;i<m;i++)tmp+=(i&1)*(1<<i);
	f.c[0][tmp]=1;//初始化 黑白黑白
	for(;n.pd();n.div(),g=g*g)
	if(n.je())f=f*g;
	for(int i=0;i<s;i++)Ans+=f.c[0][i];//累加最后一列所有情况
	printf("%d\n",Ans%p);
}