还有这种操作？？？？？？
直接用pre到now转移的方式构造一个矩阵就好了。
二进制长度为m，就构造一个长度为1 << m的矩阵
最后输出ans[(1 << m) - 1][(1 << m) - 1]就好了
牛逼！
#include<cstdio>
#include<cstring>
#include<algorithm>
#define REP(i, a, b) for(int i = (a); i < (b); i++)
#define _for(i, a, b) for(int i = (a); i <= (b); i++)
using namespace std;typedef long long ll;
const int MAXN = 16;
struct mat
{ ll m[MAXN][MAXN];mat() { memset(m, 0, sizeof(m)); }
}A;
int n, MOD;mat operator *(const mat& a, const mat& b)
{mat res;REP(i, 0, MAXN)REP(j, 0, MAXN)REP(k, 0, MAXN)res.m[i][j] = (res.m[i][j] + a.m[i][k] * b.m[k][j]) % MOD;return res;
}void dfs(int l, int now, int pre)
{if(l > 4) return;if(l == 4){A.m[pre][now]++;return;}dfs(l + 1, (now << 1) | 1, pre << 1);dfs(l + 1, now << 1, (pre << 1) | 1);dfs(l + 2, (now << 2) | 3, (pre << 2) | 3);
}mat pow(mat a, int b)
{mat res;REP(i, 0, MAXN) res.m[i][i] = 1;for(; b; b >>= 1){if(b & 1) res = res * a;a = a * a;}return res;
}int main()
{dfs(0, 0, 0);while(~scanf("%d%d", &n, &MOD) && n){mat ans = pow(A, n);printf("%lld\n", ans.m[15][15]);}return 0;
}