/*
    题意：求长度为L的合法串，非法只包含fmf,fff
    画一下DFA，可知长度为L的合法串可由长度较短的合法串过来 
    （看从安全到安全状态的回路是怎样即可，注意这个路径也不能使其他状态走到非法的！去掉重复的）
    +m,+mmf,+mmff
    dp[L] = dp[L-1]+dp[L-3]+dp[L-4]
    注意dp[0]未定义！！
    所以要初始化dp[14]  ，dp[4]=9
    M<=30,可以打表 ，不过要开成char类型，int会MLE
    不打表很慢
    可以用矩阵二分
*/
#include<cstdio>
#include<cstring>

char dp[1000001][31];

int main()
{
    int L,M;
    for(M=1;M<=30;M++){
        dp[1][M]=2%M,dp[2][M]=4%M,dp[3][M]=6%M,dp[4][M]=9%M;
        for(L=5;L<=1000000;L++)
            dp[L][M]=(dp[L-1][M]+dp[L-3][M]+dp[L-4][M])%M;
    }
    while(~scanf("%d%d",&L,&M))
        printf("%d\n",dp[L][M]);
    return 0;
}

/*
    Matrix 二分版
*/
#include<cstdio>
#include<cstring>

int MOD,L;

int ANS[4][4],A[4][4]={
                    1,1,0,0,
                    0,0,1,0,
                    1,0,0,1,
                    1,0,0,0
                  };

void mul(int A[][4],int B[][4])
{
    int R[4][4];
    memset(R,0,sizeof(R));
    for(int k=0;k<4;k++)
        for(int i=0;i<4;i++)
            if(A[i][k])
                for(int j=0;j<4;j++)
                    R[i][j]=(R[i][j]+A[i][k]*B[k][j])%MOD;
    for(int i=0;i<4;i++)
        for(int j=0;j<4;j++)
            A[i][j]=R[i][j];
}
void power(int m[][4],int n)
{
    if(n==1)
    {
        for(int i=0;i<4;i++)
            for(int j=0;j<4;j++)
                m[i][j]=A[i][j];
        return;
    }
    power(m,n/2);
    mul(m,m);
    if(n&1)mul(m,A);
}
int main()
{
    while(~scanf("%d%d",&L,&MOD))
    {
        int num[5] = {0,2,4,6,9};
        if(L<=4)printf("%d\n",num[L]%MOD);
        else
        {
            power(ANS,L-4);
            int ans = 0;
            for(int i=0;i<4;i++)
                ans+=num[4-i]*ANS[i][0];
            printf("%d\n",ans%MOD);
        }
    }
    return 0;
}