#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#define MAXN 4

using namespace std;

typedef long long int LL;

int mod;

struct matrix

{

    LL p[MAXN][MAXN];

}ans,tmp;

matrix operator*(matrix a,matrix b)

{

    matrix c;

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

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

        {

            c.p[i][j]=;

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

                c.p[i][j]=(c.p[i][j]+((a.p[i][k]%mod)*(b.p[k][j]%mod))%mod)%mod;

        }

    return c;

}

void cal(LL t,LL last) 

{

    memset(tmp.p,,sizeof(tmp.p));

    tmp.p[][]=t;

    tmp.p[][]=tmp.p[][]=tmp.p[][]=tmp.p[][]=tmp.p[][]=;

    LL y=last-t/+;

    while(y)

    {

        if(y&) ans=ans*tmp;

        tmp=tmp*tmp;

        y>>=;

    }

}

int main()

{

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

        ans.p[i][i]=;

    LL n;

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

    LL t=;

    while(n>=t)

    {

        cal(t,t-);

        t*=;

    }

    cal(t,n);

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

    return ;

}