Sgu/197

#include <cstdio>
#include <cstdlib>
#include <cstring>
 
using namespace std ;
 
const int POW[4]= {1, 10, 100, 1000}, E[6]= {1, 1<<1, 1<<2, 1<<3, 1<<4, 1<<5}; 
const int MaxSize= 1 << 5;	
 
char Str[150];
int N[30], M, MOD;
int MtxBase[MaxSize][MaxSize], MtxAns[MaxSize][MaxSize], MtxTmp[MaxSize][MaxSize];
bool Skip;
 
inline int Check(int a, int b)
{
	for(int i(1); i< M; ++ i)
		if(((a & E[i])>0) == ((a & E[i - 1])>0) && 
		   ((b & E[i])>0) == ((b & E[i - 1])>0) && 
		   ((a & E[i])>0) == ((b & E[i])>0))return 0;
	return 1;
}
 
inline int Div()
{
	int Rem= 0; 
	for(int i(N[0]); i > 0; -- i)
	{
		Rem*= 10000; Rem+= N[i];
		N[i]= Rem >> 1; Rem &= 1;
	}
	for(;N[N[0]] == 0 && N[0] > 0; -- N[0]);
	return Rem;
}
 
int main()
{
	freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
	scanf("%s%d%d", Str, &M, &MOD);
	for(int i(strlen(Str) - 1), cache(0); i >= 0; -- i, ++cache)
	{
		if(cache % 4 == 0)++N[0];
		N[N[0]]+= (Str[i]-'0') * POW[cache % 4];
	}
	--N[1];
	for(int i(1); i<= N[0]; ++ i)if(N[i] < 0){N[i]= 9999; --N[i+1];}else break;
	if(N[N[0]]==0)-- N[0];
	if(N[0]==0)Skip= 1;
 
	if(M == 1){MtxBase[0][0]= 1; MtxBase[1][1]= 1;}else
	for(int i(0); i< E[M]; ++ i)
		for(int j(0); j< E[M]; ++ j)
			MtxBase[i][j]= Check(i, j);
 
	bool Flag= 0;
	for(; N[0];)
	{
		if(Div())
		{
			if(!Flag)
			{
				for(int i(0); i< E[M]; ++ i)for(int j(0); j< E[M]; ++ j)MtxAns[i][j]= MtxBase[i][j];
				Flag= 1;
			}else
			{
				for(int i(0); i< E[M]; ++ i)for(int j(0); j< E[M]; ++ j)MtxTmp[i][j]= 0;
				for(int i(0); i< E[M]; ++ i)for(int j(0); j< E[M]; ++ j)for(int k(0); k< E[M]; ++ k)
					MtxTmp[i][j]+= MtxAns[i][k] * MtxBase[k][j], MtxTmp[i][j] %= MOD;
				for(int i(0); i< E[M]; ++ i)for(int j(0); j< E[M]; ++ j)MtxAns[i][j]= MtxTmp[i][j];
			}/*
			//Only for debug
			for(int i(0); i< E[M]; ++ i)
			{
				for(int j(0); j< E[M]; ++ j)printf("%d ", MtxAns[i][j]);
				printf("\n");
			}
			printf("\n");*/
		}
 
		for(int i(0); i< E[M]; ++ i)for(int j(0); j< E[M]; ++ j)MtxTmp[i][j]= 0;
		for(int i(0); i< E[M]; ++ i)for(int j(0); j< E[M]; ++ j)for(int k(0); k< E[M]; ++ k)
			MtxTmp[i][j]+= MtxBase[i][k] * MtxBase[k][j], MtxTmp[i][j] %= MOD;
		for(int i(0); i< E[M]; ++ i)for(int j(0); j< E[M]; ++ j)MtxBase[i][j]= MtxTmp[i][j];
	}
 
	int Ans= 0; 
	if(Skip)
		{Ans= 1;for(int i(0); i< M; ++ i)Ans *= 2, Ans %= MOD;}
	else
		for(int i(0); i< E[M]; ++ i)for(int j(0); j< E[M]; ++ j)Ans+= MtxAns[i][j], Ans%= MOD ;
	printf("%d\n", Ans);
	return 0 ;
}

/by Logic
#include<stdio.h>
#include<string.h>
const int maxd=150,maxp=400,maxb=40;
int n[maxd]={0},m,p,d,ar,ans=0;
int po[maxp][maxb][maxb]={0},f[maxb][maxb]={0};
bool judg(int a,int b)
{
	int i,x=a&b,y=a|b;
	for(i=1;i<m;i++,x>>=1,y>>=1)
		if((x&3)==3||((y^3)&3)==3) return 0;
	return 1;
}
void mul(int mul1[][maxb],int mul2[][maxb],int pro[][maxb])
{
	int i,j,k,res[maxb][maxb]={0};
	for(i=0;i<ar;i++)
		for(j=0;j<ar;j++)
			for(k=0;k<ar;k++)
				res[i][j]+=mul1[i][k]*mul2[k][j],res[i][j]%=p;
	memcpy(pro,res,sizeof(po[0]));
}
void dec(int num[])
{
	int i;
	num[0]--;
	for(i=0;i<maxd-1&&num[i]<0;i++) 
		num[i+1]--,num[i]+=10; 
}
void div(int num[])
{
	int i;
	for(i=0;i<maxd-1;i++)
		num[i]=num[i]/2+(num[i+1]&1)*5;
}
int main()
{
#ifndef ONLINE_JUDGE
	freopen("data.in","r",stdin);
	//freopen("data.out","w",stdout);
#endif
	int i,j;
	char n0[maxd];
	scanf("%s %d %d\n",n0,&m,&p);
	ar=1<<m;
	d=strlen(n0);
	for(i=0;i<d;i++)
		n[i]=n0[d-i-1]-'0';
	for(i=0;i<ar;f[i][0]=1,i++)
		for(j=0;j<ar;j++)
			po[0][i][j]=judg(i,j);
	dec(n);
	for(i=1;i<maxp;i++)
	{
		if(n[0]&1) mul(po[i-1],f,f);
		div(n);
		mul(po[i-1],po[i-1],po[i]);
	}
	//for(i=0;i<ar;i++) { for(j=0;j<ar;j++) printf("%d ",f[i][j]); printf("\n");} printf("\n");
	for(i=0;i<ar;i++)
		ans+=f[i][0],ans%=p;
	printf("%d\n",ans);
	return 0;
}