#include <iostream>
#include <cstdio>
using namespace std;
const int N=5e5+10;
const int mod=1000003;
int n,cnt[N],a[N],ans,lst[N],t[N];
long long f[N],s[N];
int ask(int l,int r){
	for(int i=l;i<=r;i++)cnt[a[i]]=0;
	for(int i=l;i<=r;i++)cnt[a[i]]++;
	for(int i=l;i<r;i++)if((cnt[a[i]]>1)==(cnt[a[i+1]]>1))return 0;
	return 1;
}
void PlanB(){
	f[0]=1;
	for(int i=1,l;i<=n;i++){
		l=max(i-100,1);
		for(int j=i;j>=l;j--){
			if(ask(j,i))f[i]=(f[i]+f[j-1])%mod;
		}
	}
	printf("%lld\n",f[n]);
	return;
}
void PlanA(){
	for(int i=1;i<=n;i++){
		lst[i]=t[a[i]];
		t[a[i]]=i;
	}
	f[0]=1,s[0]=1;int l=0;
	for(int i=1;i<=n;i++){
		if(a[i]==1){
			f[i]=f[i-1];			
			if(i-2>=l){
				f[i]+=s[i-3];
				if(l>1)f[i]-=s[l-2];
			}
			f[i]=f[i]%mod+mod;
			f[i]%=mod;
			s[i]=s[i-1]+f[i];
			s[i]%=mod;
		}else{
			l=max(l,lst[i]+1);
			f[i]=f[i-1];
			if(i-3>=l){
				f[i]+=s[i-4];
				if(l>1)f[i]-=s[l-2];
			}
			f[i]=f[i]%mod+mod;
			f[i]%=mod;
			s[i]=s[i-1]+f[i];
			s[i]%=mod;
		}
	}
	printf("%lld\n",f[n]);
	return;
}
int main(){
	freopen("digit.in","r",stdin);
	freopen("dight.out","w",stdout); 
	scanf("%d",&n);bool flag=0;
	for(int i=1;i<=n;i++){
		scanf("%d",a+i);
		if((i&1)&&(a[i]!=1))flag=1;
	}
	if(!flag)PlanA();
	else PlanB();
	
	return 0;
}