我们以M=3为例进行讲解。假设我们把这个矩形横着放在电脑屏幕上，从右往左一列一列地进行填充。其中前n-2列已经填满了，第n-1列参差不齐。现在我们要做的事情是把第n-1列也填满，将状态转移到第n列上去。由于第n-1列的状态不一样（有8种不同的状态），因此我们需要分情况进行讨论。在图中，我把转移前8种不同的状态放在左边，转移后8种不同的状态放在右边，左边的某种状态可以转移到右边的某种状态就在它们之间连一根线。注意为了保证方案不重复，状态转移时我们不允许在第n-1列竖着放一个多米诺骨牌（例如左边第2种状态不能转移到右边第4种状态），否则这将与另一种转移前的状态重复。把这8种状态的转移关系画成一个有向图，那么问题就变成了这样：从状态111出发，恰好经过n步回到这个状态有多少种方案。比如，n=2时有3种方案，111->011->111、111->110->111和111->000->111，这与用多米诺骨牌覆盖3×2矩形的方案一一对应。这样这个题目就转化为了我们前面的1486【数学基础（难度：4）】矩阵乘法?-1：多少条路呢？？。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
struct node
{
    LL a[35][35];
    node(){memset(a,0,sizeof(a));}
};

LL n,m,P,all,v[8]={0,3,6,12,15,24,27,30};
node operator* (node A, node B)
{
    node C;
    for(int i=0;i<=all;i++)
        for(int j=0;j<=all;j++)
            for(int k=0;k<=all;k++)
                C.a[i][j]=(C.a[i][j]+A.a[i][k]*B.a[k][j])%P;
    return C;
}
node qpow(node A, int b)
{
    node C=A;
    for(b--;b;b>>=1)
    {
        if(b&1)C=C*A; 
        A=A*A;
    }
    return C;
}
int main()
{
    scanf("%lld%lld%lld", &m, &n, &P);
    all=(1<<m)-1;
    node A;
    for(int i=0;i<=all;i++)A.a[i][i]=1;
    node f;
    for(int i=0;i<=all;i++)
        for(int j=0;j<=all;j++)
        {
            if(((~i)&j)==((~i)&all))
            {
                int bk=0;
                for(int k=0;k<=7;k++)
                {
                    if((i&j)==v[k])bk=bk||(i&j)==v[k];
                }
                f.a[i][j]=bk;
            }
        }
    A=A*qpow(f, n); 
    printf("%lld\n", A.a[all][all]);
    return 0;
}