#include <vector> 
#include <list> 
#include <map> 
#include <set> 
#include <deque> 
#include <queue> 
#include <stack> 
#include <bitset> 
#include <algorithm> 
#include <functional> 
#include <numeric> 
#include <utility> 
#include <sstream> 
#include <iostream> 
#include <iomanip> 
#include <cstdio> 
#include <cmath> 
#include <cstdlib> 
#include <cctype> 
#include <string> 
#include <cstring> 
#include <ctime> 

using namespace std;

#define _int64 long long

_int64 a[2][2];
_int64 b[2][2];
_int64 c[2][2];


int main()
{
  int i,j,n,m,ans,tmp,k,l,o;
  a[0][0]=4;
  a[0][1]=0;
  a[1][0]=2;
  a[1][1]=1;
  while (scanf("%d%d",&n,&m)!=EOF)
  {
    if (n%2==0) tmp=n/2;
    else tmp=(n-1)/2;
    memset(b,0,sizeof(b));
    b[0][0]=1;
    b[1][1]=1;
    for (i=30;i>=0;i--)
    {
      memset(c,0,sizeof(c));
      for (j=0;j<2;j++)
        for (k=0;k<2;k++)
          for (l=0;l<2;l++)
          {
            c[j][k]=(c[j][k]+(_int64)b[j][l]*b[l][k])%m;
          }
      if (((1<<i)&tmp)!=0)
      {
        memset(b,0,sizeof(b));
        for (j=0;j<2;j++)
          for (k=0;k<2;k++)
            for (l=0;l<2;l++)
            {
              b[j][k]=(b[j][k]+(_int64)c[j][l]*a[l][k])%m;
            }
      }
      else
      {
        memcpy(b,c,sizeof(b));
      }
    }
    ans=b[1][0];
    if (n%2!=0) ans=(ans*2+1)%m;
    cout<<ans<<endl;
  }
}