#include <cstdio>

#include <iostream>

#include <algorithm>

#include <cmath>

#include <cstring>

using namespace std;

const int N = 5;

int msize, Mod;

struct Mat

{

    int mat[N][N];

};

Mat operator *(Mat a, Mat b)

{

    Mat c;

    memset(c.mat, 0, sizeof(c.mat));

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

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

            if(a.mat[i][k])

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

                    if(b.mat[k][j])

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

    return c;

}

Mat operator ^(Mat a, int k)

{

    Mat c;

    memset(c.mat,0,sizeof(c.mat));

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

        c.mat[i][i]=1;

    for(; k; k >>= 1)

    {

        if(k&1) c = c*a;

        a = a*a;

    }

    return c;

}

int main()

{

//    freopen("in.txt","r",stdin);

    int n;

    msize = 4;

    int f[] = {9, 6, 4, 2};

    while(~scanf("%d%d", &n, &Mod))

    {

        if(n <= 4)

        {

            printf("%d\n", f[4-n] % Mod);

            continue;

        }

        Mat A;

        memset(A.mat,0,sizeof(A.mat));

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

            A.mat[0][i] = 1;

        A.mat[0][1] = 0;

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

            A.mat[i][i-1] = 1;

        A = A^(n - msize);

        int ans = 0;

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

            ans = (ans + A.mat[0][i]*f[i]) % Mod;

        printf("%d\n", ans);

    }

    return 0;

}