#include<bits/stdc++.h>
#define int long long
#define mod 1000000
using namespace std;
int n,m,k,dp[10005][300],s[300],cnt,v,ans,mp,mps;//i行j个k第k情况
int t,la,ff;
bool ad(int a,int b)
{
	if(a==b)return true;
	while(a)
	{
		if(a%3==b%3)return true;
		a/=3,b/=3;
	}
	return false;
}
void init()
{
	for(int i=(m>1);i<pow(3,m);i++)
	{
		t=i,ff=0,la=-1;
		while(t)
		{
			if(t%3==la)ff=1;
			la=t%3,t/=3;
		}
		if(ff)continue;
		if(i==mps)mp=cnt;
		s[cnt++]=i;
	}
}
signed main()
{
    cin>>n>>m>>k;
    for(int j=0;j<m;j++)
    {
    	cin>>v,v--;
    	if(j&&mps%3==v)mp=-1;
    	mps=mps*3+v;
    }
    if(mp==-1)
    {
    	puts("0");
    	return 0;
	}
	init();
    if(k==1)dp[1][mp]=1;
    else
	{
		for(int i=0;i<cnt;i++)
    		dp[1][i]++;
	}
	for(int i=2;i<=n;i++)
	{
		if(i!=k)
		{
			for(int p=0;p<cnt;p++)
			{
				for(int q=0;q<cnt;q++)
				{
				
					if(ad(s[p],s[q]))continue;
					dp[i][p]+=dp[i-1][q],dp[i][p]%=mod;	
				}
			}
		}
		else
		{
			for(int q=0;q<cnt;q++)
			{
				if(ad(mps,s[q]))continue;
				dp[i][mp]+=dp[i-1][q],dp[i][mp]%=mod;
			}
		}
	}
	for(int i=0;i<cnt;i++)ans+=dp[n][i],ans%=mod;
    cout<<ans%mod;
    return 0;
}

题目链接