1 #include<iostream> 2 #include<cstdio> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 #include<queue> 7 using namespace std; 8 int mod; 9 void mul(int a[4][4], int b[4][4])10 {11     int c[4][4];12     memset(c,0,sizeof(c));13     for(int i=0;i<4;i++)14         for(int j=0;j<4;j++)15         for(int k=0;k<4;k++)16         c[i][j] = (c[i][j]+a[i][k]*b[k][j])%mod;17     memcpy(a,c,sizeof(c));18 }19 void quick_mod(int a[4][4], int b)20 {21     int c[4][4];22     memset(c,0,sizeof(c));23     for(int i=0;i<4;i++) c[i][i] = 1;24     while(b)25     {26         if(b&1) mul(c,a);27         mul(a,a);28         b>>=1;29     }30     memcpy(a,c,sizeof(c));31 }32 33 int main()34 {35     int i,j,k,m,n;36     int a[4][4];37     int f[5] = {0,2,4,6,9};38     while(scanf("%d%d",&k,&mod)==2)39     {40         if(k<5) { printf("%d\n",f[k]%mod); continue; }41         memset(a,0,sizeof(a));42         a[0][0] = a[2][0] = a[3][0] = a[0][1] = a[1][2] = a[2][3] = 1;43         quick_mod(a,k-4);44         int ans = (9*a[0][0]+6*a[1][0]+4*a[2][0]+2*a[3][0])%mod;45         printf("%d\n",ans);46     }47 }