三进制状态压模板题，具体思路请看注释吧

#include<bits/stdc++.h>
using namespace  std;
const int mo=1e6;

int c[100000],n,m,k; //c[i]=3的i次方
vector<int> v,g[310];//v中是所有的合法状态，g[i]中的是能和状态i相邻的状态
int state=0; //state为题目中所给的第k行的状态
int f[10005][300]; //f[i][j]为只涂了前i行，最后一行状态为j,并且第一行要能和state相邻的方案数目

int get(int x,int u) //此函数相当于二进制状压的x>>u&1
{
    return x%c[u+1]/c[u];
}

bool chk(int x) //判断行内状态x是否合法
{
    for(int i=1;i<m;i++)
    {
        if(get(x,i)==get(x,i-1)) return false;
    }
    return true;
}

bool chk2(int x,int y) //判断状态x和状态y是否可以挨着
{
    for(int i=0;i<m;i++)
        if(get(x,i)==get(y,i)) return false;
    return true;
}

int main()
{
    cin>>n>>m>>k;
    c[0]=1;
    for(int i=1;i<=m;i++) c[i]=3*c[i-1];
    for(int i=0;i<m;i++)
    {
        int x;cin>>x;
        state=state*3+x-1;
    }
    for(int i=0;i<c[m];i++)
        if(chk(i)) v.push_back(i);
    for(auto a:v)   
        for(auto b:v) if(chk2(a,b)) g[a].push_back(b);

    int x=max(k-1,n-k),y=min(k-1,n-k);

    f[0][state]=1;
    for(int i=1;i<=x;i++)
        for(auto a:v)
        {
            {
                for(auto b:g[a]) 
                    (f[i][a]+=f[i-1][b])%=mo;
            }
        }
    int ans1=0,ans2=0; //ans1为第k行上方的方案数，ans2是第k行下方的方案数目
    for(auto i:v) (ans1+=f[x][i])%=mo,(ans2+=f[y][i])%=mo;

    cout<<(long long )ans1*ans2%mo<<endl;
    return 0;
}