#include <algorithm>
#include<iostream>

using i8=char;
using u8=unsigned char;
using i16=short;
using u16=unsigned short;
using i32=int;
using u32=unsigned int;
using i64=long long;
using u64=unsigned long long;
using i128=__int128;
using u128=unsigned __int128;
using f32=float;
using f64=double;
using f128=long double;

template<typename T> void read(T &x){
	char ch=getchar(),f=1;
	x=0;
	while(ch<'0'||ch>'9')f=(ch=='-')?-1:1,ch=getchar();
	while(ch>='0'&&ch<='9')(x=x*10+(ch-'0')),ch=getchar();
	x*=f;
}
template<typename T> void readstring(T &x,const std::string &s,i32 mod){
	x=0;
	for(auto i:s)x=((i64)x*10+i-'0')%mod;
}
template<typename T,typename ...Ts> void read(T &x,Ts &...xs){
	read(x);
	read(xs...);
}
template<typename T> void write(T x){
	if(x<0)putchar('-'),x=-x;
	else if(x>9)write(x/10);
	putchar((x%10)^48);
}
template<typename T> void writesp(T x){
	write(x);
	putchar(' ');
}
template<typename T> void writeln(T x){
	write(x);
	putchar('\n');
}
template<typename T> void writelns(T x){
	writeln(x);
}
template<typename T,typename ...Ts> void write(T x,Ts ...xs){
	writesp(x);
	write(xs...);
}
template<typename T,typename ...Ts> void writeln(T x,Ts ...xs){
	write(x,xs...);
	putchar('\n');
}
template<typename T,typename ...Ts> void writelns(T x,Ts ...xs){
	writeln(x);
	writelns(xs...);
}
i32 m,p;
struct Mat{
	i32 r,c;
	i32 m[35][35];
	void clear(){
		for(i32 i=1;i<=r;i++)for(i32 j=1;j<=c;j++)m[i][j]=0;
	}
	Mat(i32 _r=0,i32 _c=0):r(_r),c(_c){this->clear();}
	void resize(i32 _r,i32 _c){this->r=_r,this->c=_c;this->clear();}
	Mat operator*(const Mat &x)const{
		Mat re(this->c,x.c);
		for(i32 i=1;i<=this->r;i++){
			for(i32 j=1;j<=this->c;j++){
				for(i32 k=1;k<=x.r;k++){
					re.m[i][j]=((i64)re.m[i][j]+(i64)this->m[i][k]*x.m[k][j])%p;
				}
			}
		}
		return re;
	}
	Mat & operator*=(const Mat &x){
		*this=(*this)*x;
		return *this;
	}
}unit,st,ans;
void write(const Mat &x){
	for(i32 i=1;i<=x.r;i++){
		for(i32 j=1;j<=x.c;j++){
			writesp(x.m[i][j]);
		}
		putchar('\n');
	}
	putchar('\n');
}
bool check(i32 x,i32 y){
	for(i32 i=0;i<m-1;i++){
		if((x>>i)&1&(x>>(i+1))&(y>>i)&(y>>(i+1)))return false;
		// writeln(1,i,x,y);
		if(((x>>i)^1)&((x>>(i+1))^1)&((y>>i)^1)&((y>>(i+1))^1)) return false;
		// writeln(1,i,x,y);
	}
	// writeln(x,y);
	return true;
}
struct BigInt{
	std::basic_string<i32> s;
	BigInt & operator=(std::string s){
		for(auto i:s)this->s+=i-'0';
		std::reverse(this->s.begin(),this->s.end());
		return *this;
	}
	bool zero(){
		return s.empty();
	}
	bool odd(){
		return s.front()&1;
	}
	void div(){
		i32 down=0;
		for(i32 i=s.size()-1;i>=0;i--){
			i32 x=(s[i]+down)>>1;
			down=((s[i]+down)&1)*10;
			s[i]=x;
		}
		while(!s.empty()&&s.back()==0){
			s.pop_back();
		}
	}

}n;
Mat qp(Mat x,BigInt y){
	Mat re=x;
	while(!y.zero()){
		// write(x);
		if(y.odd()){
			re*=x;
		}
		x*=x;
		y.div();
	}
	return re;
}
int main(){
#ifdef LOCAL
	freopen("test.in","r",stdin);
	freopen("test.out","w",stdout);
	freopen("test.err","w",stderr);
#endif
	std::string s;
	std::cin>>s;
	n=s;
	//std::reverse(n.s.begin(),n.s.end());
	read(m,p);
	//readstring(n,s,p);
	i32 lim=(1<<m);
	unit.resize(lim,lim),st.resize(lim,1),ans.resize(1,lim);
	for(i32 i=1;i<=lim;i++)ans.m[1][i]=1;
	for(i32 i=0;i<lim;i++){
		for(i32 j=0;j<lim;j++){
			if(check(i,j)){
				unit.m[i+1][j+1]=1;
			}
		}
	}
	// write(unit);
	i32 wb=0;
	for(i32 i=1;i<=m;i++){
		wb=(wb<<1)|(i&1);
	}
	wb++;
	st.m[wb][1]=1;
	unit=qp(unit,n);
	unit*=st;
	writeln(unit.m[wb][1]);
	// writeln((i32)check(00,01),(i32)check(01,00));
	return 0;
}

我的开o2800多ms 题解的只需要200ms。。。 我哪里写慢了？