找了半天错发现m有可能是1.。
/*
如果n是奇数，就进行(n/2)次转移，然后取F[2]，反之取F[1]
*/
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,m,F[];
struct Mat{
ll m[][];
Mat(){memset(m,,sizeof m);}
};
void mul1(ll F[],Mat A){
ll C[]={};
for(int j=;j<;j++)
for(int i=;i<;i++)
C[j]=(C[j]+F[i]*A.m[i][j]%m)%m;
memcpy(F,C,sizeof C);
}
void mul2(Mat & A,Mat B){
Mat C;
for(int i=;i<;i++)
for(int j=;j<;j++)
for(int k=;k<;k++)
C.m[i][j]=(C.m[i][j]+A.m[i][k]*B.m[k][j]%m)%m;
memcpy(A.m,C.m,sizeof C.m);
}
int main(){
while(cin>>n>>m){
memset(F,,sizeof F);
F[]=,F[]=,F[]=;
Mat A;
A.m[][]=A.m[][]=;
A.m[][]=,A.m[][]=; if(n==){
cout<<%m<<endl;
continue;
} int flag=n%;
n/=;
while(n){
if(n%)
mul1(F,A);
mul2(A,A);
n>>=;
}
cout<<F[+flag]%m<<endl;
}
}