1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 #define debug(x) cout<<"["<<#x<<"]"<<"  "<<x<<endl;
 5 ll w[4][4],e[4][4];
 6 const int N=4;
 7 ll tmp[N][N],mod;
 8 void multi(ll a[][N],ll b[][N],int n)
 9 {
10     memset(tmp,0,sizeof tmp);
11     for(int i=0;i<n;i++)
12         for(int j=0;j<n;j++)
13         for(int k=0;k<n;k++)
14         {tmp[i][j]+=a[i][k]%mod*b[k][j]%mod;tmp[i][j]%=mod;}
15     for(int i=0;i<n;i++)
16         for(int j=0;j<n;j++)
17         a[i][j]=tmp[i][j];
18 }
19 ll res[N][N];
20 void Pow(ll a[][N],int n)
21 {
22     memset(res,0,sizeof res);//n是幂，N是矩阵大小
23     for(int i=0;i<N;i++) res[i][i]=1;
24     while(n)
25     {
26         if(n&1)
27             multi(res,a,N);//res=res*a;复制直接在multi里面实现了；
28         multi(a,a,N);//a=a*a
29         n>>=1;
30     }
31 }
32 void init(){
33     w[0][0]=1;
34     w[0][1]=0;
35     w[0][2]=1;
36     w[0][3]=1;
37 
38     w[1][0]=1;
39     w[1][1]=0;
40     w[1][2]=0;
41     w[1][3]=0;
42 
43     w[2][0]=0;
44     w[2][1]=1;
45     w[2][2]=0;
46     w[2][3]=0;
47 
48     w[3][0]=0;
49     w[3][1]=0;
50     w[3][2]=1;
51     w[3][3]=0;
52 }
53 int main()
54 {
55     int l;
56     e[0][0]=9;
57     e[1][0]=6;
58     e[2][0]=4;
59     e[3][0]=2;
60     while(scanf("%d%lld",&l,&mod)==2){
61         init();
62         if(l<4){
63             printf("%lld\n",e[l-1][0]%mod);
64         }
65         else{
66             Pow(w,l-4);
67             multi(res,e,4);
68             printf("%lld\n",res[0][0]);
69         }
70     }
71     return 0;
72 }