#include<bits/stdc++.h>
#define ll long long
#define mod 1000003
#define N 500001
using namespace std;
int n,a[N],cnt[N];
ll dp[N];
bool f(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]]++;
    if(l>r) return false;
    int first=(cnt[a[l]]>=2?1:0);
    for(int i=l+1;i<=r;i++){
        if((cnt[a[i]]>=2?1:0)==first) return false;
        first=(cnt[a[i]]>=2?1:0);
    }
    return true;
}
int main(){
    freopen("digit.in","r",stdin);
    freopen("digit.out","w",stdout);
    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(f(j,i)) dp[i]=(dp[i]+dp[j-1])%mod;
    cout<<dp[n]%mod<<endl;
    return 0;
}