#include<iomanip>
#include<limits>
#include<thread>
#include<utility>
#include<iostream>
#include<string>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<stack>
#include<queue>
#include<cmath>
#include<numeric>
#include<cassert>
#include<random>
#include<chrono>
#include<unordered_set>
#include<unordered_map>
#include<fstream>
#include<list>
#include<functional>
#include<bitset>
#include<complex>
#include<tuple>
using namespace std;
typedef unsigned long long int ull;
typedef long long int ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pi;
typedef pair<double,double> pd;
typedef pair<double,ll> pdl;
#define F first
#define S second
const ll E=1e18+7;
const ll MOD=1000000007;

/*
 0 1
 2 3
 4 5
 
  0 1 2 3
0   0 1 2
1 3   4 5
2 6 7   8
3 9 10 11
*/

vector<vector<ll>> edge(6,vector<ll>(6,E));

bool Cycle(){
    for(int i=0;i<6;i++){
        for(int t=0;t<6;t++){
            for(int j=0;j<6;j++){
                edge[t][j]=min(edge[t][j],edge[t][i]+edge[i][j]);
            }
        }
    }
    for(int i=0;i<6;i++){
        if(edge[i][i]!=E){return true;}
    }
    return false;
}



int main(){
    vector<vector<ll>> A(1LL<<12,vector<ll>(1LL<<3,-1));
    vector<vector<ll>> B(1LL<<12,vector<ll>(1LL<<2,0));
    for(int i=0;i<(1LL<<12);i++){
        for(int t=0;t<(1LL<<3);t++){
            for(auto &I:edge){
                for(auto &T:I){T=E;}
            }
            for(int k=0;k<4;k++){
                for(int h=0;h<4;h++){
                    if(k==h){continue;}
                    ll w=h;
                    if(h>k){w--;}
                    if(i>>(k*3+w)&1){edge[k][h]=1;}
                }
            }
            if(t&1){edge[3][5]=1;}
            else{edge[5][3]=1;}
            if(t>>1&1){edge[2][4]=1;}
            else{edge[4][2]=1;}
            if(t>>2&1){edge[4][5]=1;}
            else{edge[5][4]=1;}
            if(Cycle()){continue;}
            ll w=0;
            for(int k=0;k<4;k++){
                for(int h=0;h<4;h++){
                    ll K=k;
                    if(K>=2){K+=2;}
                    ll H=h;
                    if(H>=2){H+=2;}
                    if(edge[K][H]!=E){
                        ll W=h;
                        if(h>k){W--;}
                        w|=(1LL<<(3*k+W));
                    }
                }
            }
            A[i][t]=w;
        }
    }
    for(int i=0;i<(1LL<<12);i++){
        for(int t=0;t<(1LL<<2);t++){
            for(auto &I:edge){
                for(auto &T:I){T=E;}
            }
            for(int k=0;k<4;k++){
                for(int h=0;h<4;h++){
                    if(k==h){continue;}
                    ll w=h;
                    if(h>k){w--;}
                    if(i>>(k*3+w)&1){edge[k][h]=1;}
                }
            }
            if(t>>0&1){edge[0][2]=1;}
            else{edge[2][0]=1;}
            if(t>>1&1){edge[1][3]=1;}
            else{edge[3][1]=1;}
            if(!Cycle()){B[i][t]=1;}
        }
    }
    
    
    ll n,m;
    cin>>n>>m;
    vector<vector<ll>> dp(n,vector<ll>(1LL<<12,0));
    for(int i=0;i<(1LL<<12);i++){
        for(auto &I:edge){
            for(auto &T:I){T=E;}
        }
        for(int k=0;k<4;k++){
            for(int h=0;h<4;h++){
                if(k==h){continue;}
                ll w=h;
                if(h>k){w--;}
                if(i>>(k*3+w)&1){edge[k][h]=1;}
            }
        }
        
        
        if(edge[0][1]+edge[1][0]!=E+1 || edge[0][2]+edge[2][0]!=E+1 || edge[1][3]+edge[3][1]!=E+1 || edge[2][3]+edge[3][2]!=E+1 || edge[0][3]!=E || edge[3][0]!=E || edge[1][2]!=E || edge[2][1]!=E){continue;}
        
        if(!Cycle()){
            ll w=0;
            for(int k=0;k<4;k++){
                for(int h=0;h<4;h++){
                    if(edge[k][h]!=E){
                        ll W=h;
                        if(h>k){W--;}
                        w|=(1LL<<(3*k+W));
                    }
                }
            }
            dp[1][w]++;
        }
    }
    
    for(int i=1;i+1<n;i++){
        for(int t=0;t<(1LL<<12);t++){
            for(int h=0;h<(1LL<<3);h++){
                if(A[t][h]!=-1){
                    dp[i+1][A[t][h]]+=dp[i][t];
                    dp[i+1][A[t][h]]%=m;
                }
            }
        }
    }
    ll ans=0;
    for(int i=0;i<(1LL<<12);i++){
        for(int k=0;k<4;k++){
            ans+=dp.back()[i]*B[i][k];
        }
    }
    ans%=m;
    cout<<ans<<endl;
    
    
    
    return 0;
}



Measured memory_bytes: 35492