#include <bits/stdc++.h>
using namespace std;
#define ll long long

const ll MOD=1000003;

ll n;
ll a[510000],dp[510000];

bool solve(ll a[],ll l,ll r){
	unordered_map<ll,ll> m;
	for (int i=l;i<=r;i++){
		m[a[i]]++;
	}
	for (int i=l;i<r;i++){
		ll t1=(m[a[i]]>1)?1:0;
		ll t2=(m[a[i+1]]>1)?1:0;
		if (t1==t2){
			return 0;
		}
	}
	return 1;
}


int main(){
	freopen("digit.in","r",stdin);
	freopen("digit.out","w",stdout);
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>n;
	for (int i=1;i<=n;i++){
		cin>>a[i];
	}
	dp[0]=1;
	for (int i=1;i<=n;i++){
		for (int j=1;j<=i;j++){
			if (solve(a,j,i)){
				dp[i]=(dp[i]+dp[j-1])%MOD;
			}
		}
	}
	cout<<dp[n]<<endl;
	return 0;
}