Tired of the Tri Tiling game finally, Michael turns to a more challengeable game, Quad Tiling:

In how many ways can you tile a 4 × N (1 ≤ N ≤ 10⁹) rectangle with 2 × 1 dominoes? For the answer would be very big, output the answer modulo M (0 < M ≤ 10⁵).

 1 #include<set> 2 #include<queue> 3 #include<cstdio> 4 #include<cstring> 5 #include<cstdlib> 6 #include<iostream> 7 #include<algorithm> 8 using namespace std; 9 #define For(i,n) for(int i=1;i<=n;i++)10 #define Rep(i,l,r) for(int i=l;i<=r;i++)11 12 struct Matrix{13     int A[17][17];14     Matrix(){15         memset(A,0,sizeof(A));16     }17 }Unit,Ans,TAns;18 19 int opt[20],n,Mod;20 21 Matrix operator * (Matrix A,Matrix B){22    Matrix C;23     Rep(i,0,15)24       Rep(j,0,15)25         Rep(k,0,15)26            C.A[i][j] = ( C.A[i][j] + (A.A[i][k] * B.A[k][j]) % Mod ) % Mod;27     return C;28 }29 30 bool Check(int s1,int s2){31     if((s1|s2)!=15) return false;32     for(int i=0;i<=15;){33         if( (s1&(1<<i)) != (s2&(1<<i)) ) i++;34         else{35             if(i==15) return false; else36             if(  ( s1 & (1<<(i+1)) ) != ( s2 & (1<<(i+1)) ) ) return false;37             i+=2;38         }39     }40     return true;41 }42 43 int main(){44     Rep(i,0,15){45         Rep(j,0,15)46             if(Check(i,j)) Ans.A[i][j] = TAns.A[i][j] = 1;47         if(Check(i,15)) 48             opt[i] = 1;49     }50     while(scanf("%d%d",&n,&Mod),Mod+n){        51         Rep(i,0,15){52             Rep(j,0,15){53                 Ans.A[i][j] = TAns.A[i][j];54                 Unit.A[i][j] = 0;55             }56             Unit.A[i][i] = 1;57         } 58         while(n){59             if(n&1) Unit = Unit * Ans;60             Ans = Ans * Ans;61             n = n >> 1;62         }63         int ans = 0;64         Rep(i,0,15) 65             ans = (ans % Mod + (opt[i] * Unit.A[0][i] % Mod) % Mod) % Mod;66         printf("%d\n",ans);67     }68     return 0;69 }