#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

const int MOD = 1000003;
const int MAXN = 5 * 1e5 + 5;

int n, a[MAXN], f[MAXN], cnt[MAXN];
vector<int> rep;

int main(){
	freopen("digit.in", "r", stdin);
	freopen("digit.out", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for(int i = 1;i <= n;i ++){
        cin >> a[i];
        rep.push_back(a[i]);
    }
    sort(rep.begin(), rep.end());
    rep.erase(unique(rep.begin(), rep.end()), rep.end());
    for(int i = 1;i <= n;i ++){
        a[i] = lower_bound(rep.begin(), rep.end(), a[i]) - rep.begin() + 1;
    }
    f[0] = 1;
    for(int i = 1;i <= n;i ++){
        memset(cnt, 0, sizeof(cnt));
        int last = -1;
        f[i] = 0;
        for(int j = i;j >= 1;j --){
            int x = a[j];
            cnt[x] ++;
            int cur = (cnt[x] >= 2) ? 1 : 0;
            bool flag = true;
            if(j < i) flag = (cur != last);
            if(flag) f[i] = (f[i] + f[j - 1]) % MOD;
            last = cur;
        }
    }
    cout << (f[n] % MOD + MOD) % MOD << '\n';
    return 0;
}