#include <bits/stdc++.h>
using namespace std;
class SegTree
{
private:
vector<int> st, nb, lazy;
int N, MOD = 1000003;
int r(int x) { return (x << 1) + 1; }
int l(int x) { return (x << 1); }
void propagate(int L, int R, int x)
{
st[x] += lazy[x];
if (L != R)
{
lazy[r(x)] += lazy[x];
lazy[l(x)] += lazy[x];
}
lazy[x] = 0;
}
void update(int L, int R, int a, int b, int val, int x)
{
propagate(L, R, x);
if (L > b || R < a)
return;
if (L >= a && R <= b)
{
lazy[x] += val;
propagate(L, R, x);
}
else
{
int m = (L + R) / 2;
update(L, m, a, b, val, l(x));
update(m + 1, R, a, b, val, r(x));
st[x] = min(st[l(x)], st[r(x)]);
nb[x] = (((st[l(x)] == st[x]) ? nb[l(x)] : 0) + ((st[r(x)] == st[x]) ? nb[r(x)] : 0)) % MOD;
}
}
void set(int L, int R, int a, int val, int x)
{
propagate(L, R, x);
if (L > a || R < a)
return;
if (L == a && R == a)
nb[x] = val % MOD;
else
{
int m = (L + R) / 2;
set(L, m, a, val, l(x));
set(m + 1, R, a, val, r(x));
nb[x] = (((st[l(x)] == st[x]) ? nb[l(x)] : 0) + ((st[r(x)] == st[x]) ? nb[r(x)] : 0)) % MOD;
}
}
int RSQ(int L, int R, int a, int b, int x)
{
propagate(L, R, x);
if (L > b || R < a)
return 0;
if (st[x] != 0)
return 0;
if (L >= a && R <= b)
return nb[x];
int m = (L + R) / 2;
return (RSQ(L, m, a, b, l(x)) + RSQ(m + 1, R, a, b, r(x))) % MOD;
}
public:
SegTree(int x)
{
N = pow(2, ceil(log2(x)));
st.assign(2 * N, 0);
nb.assign(2 * N, 0);
lazy.assign(2 * N, 0);
}
void update(int a, int b, int val)
{
if (b >= a)
update(0, N - 1, a, b, val, 1);
}
void set(int x, int val) { set(0, N - 1, x, val, 1); }
int RSQ(int a, int b) { return RSQ(0, N - 1, a, b, 1); }
};
int main()
{
int N;
cin >> N;
vector<int> Tab(N);
for (int i = 0; i < N; i++)
{
cin >> Tab[i];
Tab[i]--;
}
SegTree STodd(N + 1), STeven(N + 1);
STodd.set(N, 1);
STeven.set(N, 1);
vector<int> last(N, N + 1), last2(N, -1);
for (int i = N - 1; i >= 0; i--)
{
if (i % 2 == 1)
{
STeven.update(last[Tab[i]] + 1, N, 1);
if (last[Tab[i]] % 2 == 0)
STodd.update(last[Tab[i]] + 1, N, 10);
else
STodd.update(last[Tab[i]] + 1, last2[Tab[i]], -1);
STodd.update(i + 1, last[Tab[i]], 1);
}
else
{
STodd.update(last[Tab[i]] + 1, N, 1);
if (last[Tab[i]] % 2 == 1)
STeven.update(last[Tab[i]] + 1, N, 10);
else
STeven.update(last[Tab[i]] + 1, last2[Tab[i]], -1);
STeven.update(i + 1, last[Tab[i]], 1);
}
last2[Tab[i]] = last[Tab[i]];
last[Tab[i]] = i;
int tot = (STodd.RSQ(i, N) + STeven.RSQ(i, N)) % 1000003;
STodd.set(i, tot);
STeven.set(i, tot);
}
cout << (STodd.RSQ(1, N) + STeven.RSQ(1, N)) % 1000003;
}
