经典题型。如果列数较少，就能用我们熟知的状态压缩DP解决。但现在列数有2
31。考虑到相邻两列之间状态转移规则是相同的，我们可以用矩阵表示这种转移规则，而最后的结果就是求这个转移矩阵的n次幂的左上角元素。
/**//*************************************************************************
Author: WHU_GCC
Created Time: 2007-10-6 11:05:55
File Name: pku3420.cpp
Description:
************************************************************************/
#include <iostream>
using namespace std;
#define out(x) (cout<<#x<<": "<<x<<endl)
const int maxint=0x7FFFFFFF;
typedef long long int64;
const int64 maxint64 = 0x7FFFFFFFFFFFFFFFLL;
template<class T>void show(T a, int n)
{for(int i=0; i<n; ++i) cout<<a[i]<<' '; cout<<endl;}
template<class T>void show(T a, int r, int l){for(int i=0; i<r; ++i)show(a[i],l);cout<<endl;}
int g[16][16];
int M;
void dfs(int old_state, int now, int new_state)
{
if (now > 3)
{
g[old_state][new_state]++;
return;
}
if (old_state & (1 << now))
dfs(old_state, now + 1, new_state);
if (now <= 2)
{
if ((old_state & (1 << now)) == 0 && (old_state & (1 << (now + 1))) == 0)
dfs(old_state, now + 2, new_state);
}
if ((old_state & (1 << now)) == 0)
dfs(old_state, now + 1, new_state | (1 << now));
}
void mul(int a[16][16], int b[16][16], int c[16][16])
{
for (int i = 0; i < 16; i++)
for (int j = 0; j < 16; j++)
{
c[i][j] = 0;
for (int k = 0; k < 16; k++)
c[i][j] += a[i][k] * b[k][j];
c[i][j] %= M;
}
}
int calc(int n)
{
int p[16][16];
memcpy(p, g, sizeof(p));
int ans[16][16], tmp[16][16];
memset(ans, 0, sizeof(ans));
for (int i = 0; i < 16; i++)
ans[i][i] = 1;
while (n)
{
if (n & 1)
{
mul(ans, p, tmp);
memcpy(ans, tmp, sizeof(tmp));
}
n >>= 1;
mul(p, p, tmp);
memcpy(p, tmp, sizeof(tmp));
}
return ans[0][0];
}
int main()
{
memset(g, 0, sizeof(g));
for (int i = 0; i < 16; i++)
dfs(i, 0, 0);
int n;
while (scanf("%d%d", &n, &M), n + M != 0)
{
printf("%d\n", calc(n));
}
return 0;
}