#include<cstdio>

 #include<cstring>

 #include<cmath>

 typedef long long ll;

 ll n,mod;

 struct Matrix{

     ll a[][];

     Matrix (){

         memset(a,,sizeof(a));

     }

     inline void e(){

         for(int i=;i<=;i++)

             a[i][i]=;

     }

     friend Matrix operator *(Matrix x,Matrix y){

         Matrix c;

         for(int k=;k<=;k++)

             for(int i=;i<=;i++)

                 for(int j=;j<=;j++){

                     c.a[i][j]+=x.a[i][k]*y.a[k][j];

                     if(c.a[i][j]>mod)

                         c.a[i][j]%=mod;

                 }

         return c;

     }

     friend Matrix operator ^(Matrix a,ll b){

         Matrix ans;ans.e();

         while(b){

             if(b&) ans=ans*a;

             b>>=;

             a=a*a;

         }return ans;

     }

     inline void kmod(ll k){

         for(int i=;i<=;i++)

             for(int j=i;j<=;j++)

                 a[i][j]=;

         a[][]=k%mod;

     }

 };

 int main(){

     scanf("%lld%lld",&n,&mod);

     Matrix ans;

     ans.a[][]=;

     ans.a[][]=;

     ans.a[][]=;

     int i;ll j;

     for(i=,j=;j*<=n;j*=,i++){

         Matrix b;b.kmod(j*);

         ans=(b^(j*-j))*ans;

     }//printf("%lld\n",ans.a[1][1]);

     Matrix b;b.kmod(j*);

     if(n-j+>)

         ans=(b^(n-j+))*ans;

     printf("%lld\n",ans.a[][]);

 }