#include <bits/stdc++.h>
using namespace std;
const int mod = 1e6 + 3;
int n,arr[500009];
int dp[500009];
int freq[500009];
int main() {
ios_base::sync_with_stdio(0);cin.tie(nullptr);
//freopen(".inp","r",stdin);
//freopen(".out","w",stdout);
cin >> n;
for (int i = 1;i <= n;i++) cin >> arr[i];
dp[0] = 1;
for (int i = 1;i <= n;i++) {
int lightodd = 0,lighteven = 0;
for (int j = i;j >= 1;j--) {
if (freq[arr[j]] == 0) {
freq[arr[j]] = j;
if (j % 2 == 0) lighteven++;
else lightodd++;
} else if (freq[arr[j]] > 0) {
int d = freq[arr[j]];
if (d % 2 == 0) lighteven--;
else lightodd--;
freq[arr[j]] = -1;
}
if (freq[arr[i]] > 0) { //neu i la light
int need = (i - j + 2)/2;
if (i % 2 == 0 && lightodd == 0 && lighteven == need) {
dp[i] = (dp[i] + dp[j - 1])%mod;
}
if (i % 2 != 0 && lighteven == 0 && lightodd == need) {
dp[i] = (dp[i] + dp[j - 1])%mod;
}
} else { //neu i la heavy
int need = (i - j + 1)/2;
if (i % 2 != 0 && lightodd == 0 && lighteven == need) {
dp[i] = (dp[i] + dp[j - 1])%mod;
}
if (i % 2 == 0 && lighteven == 0 && lightodd == need) {
dp[i] = (dp[i] + dp[j - 1])%mod;
}
}
}
for (int j = i;j >= 1;j--) freq[arr[j]] = 0;
}
cout << dp[n];
}
/*
Nho doi vai em gay
co gai ay ngoi duoi goc pho nen tho ...
*/
