1 #include <cstdio> 2 #include <cstring> 3 #include <cstdlib> 4  5 #define MATN 4 6  7 typedef struct mat_st { 8     int m[MATN][MATN]; 9     mat_st() {10         memset(m, 0, sizeof(m));11     }12 } mat_st;13 14 int ans[MATN]={1,2,4,6};15 int mod;16 17 mat_st mult_mat(mat_st a, mat_st b) {18     mat_st ret;19     int i, j, k;20 21     for (i=0; i<MATN; ++i) {22         for (j=0; j<MATN; ++j) {23             for (k=0; k<MATN; ++k)24                 ret.m[i][j] += a.m[i][k]*b.m[k][j];25             ret.m[i][j] %= mod;26         }27     }28     return ret;29 }30 31 mat_st pow_mat(mat_st a, int n) {32     mat_st ret;33     int i;34 35     for (i=0; i<MATN; ++i)36         ret.m[i][i] = 1;37 38     while (n) {39         if (n & 1)40             ret = mult_mat(ret, a);41         a = mult_mat(a, a);42         n >>= 1;43     }44     return ret;45 }46 47 int main() {48     int l;49     int i;50     mat_st e, a;51 52     e.m[0][0] = e.m[0][1] = e.m[1][2] = e.m[2][0] = e.m[2][3] = e.m[3][0] = 1;53     for (i=0; i<MATN; ++i)54         a.m[0][i] = ans[MATN-1-i];55 56     while (scanf("%d %d", &l, &mod) != EOF) {57         if (l <= 3)58             printf("%d\n", ans[l]%mod);59         else {60             mat_st c = pow_mat(e, l-3);61             mat_st r = mult_mat(a, c);62             printf("%d\n", r.m[0][0]);63 #ifndef ONLINE_JUDGE64             fflush(stdout);65 #endif66         }67     }68 69     return 0;70 }