//f[n]=2*f[n-2]+f[n-1]+1
//矩阵快速幂
# include
  
   
# include
   
     # include
    
      # include
     
       using namespace std; struct node { __int64 m[3][3]; }; __int64 mod; node answ,origin,d; node f(node a,node b) { __int64 i,j,k; node c; for(i=0; i<3; i++) { for(j=0; j<3; j++) { c.m[i][j]=0; for(k=0; k<3; k++) { c.m[i][j]+=(a.m[i][k]*b.m[k][j])%mod; c.m[i][j]%=mod; } } } return c; } node quick(node answ,node origin,__int64 n) { while(n) { if(n%2) answ=f(answ,origin); origin=f(origin,origin); n/=2; } return answ; } int main() { __int64 i,j,n; while(~scanf("%I64d %I64d",&n,&mod)) { memset(answ.m,0,sizeof(answ.m)); memset(d.m,0,sizeof(d.m)); memset(origin.m,0,sizeof(origin.m)); for(i=0; i<3; i++) answ.m[i][i]=1; d.m[0][0]=1; d.m[0][1]=2; d.m[0][2]=1; origin.m[0][1]=2; origin.m[1][0]=1; origin.m[1][1]=1; origin.m[2][1]=1; origin.m[2][2]=1; if(n==1) printf("%I64d\n",1%mod); else if(n==2) printf("%I64d\n",2%mod); else { answ=quick(answ,origin,n-2); answ=f(d,answ); printf("%I64d\n",answ.m[0][1]%mod); } } return 0; }