#include <bits/stdc++.h>

#define pb push_back
#define S second
#define F first

using  namespace std;

const int MOD = 1e9;


vector<int> a;
int dp [2005][2005];

int fans(int l, int r)
{
    //cerr << l <<' '<< r << endl;
    if (l > r)
        return 0;
    int cran = 0;
    int fans1 = 0;
    int fans2 = 0;
    if (l == r)
        return dp[l][r] = 1;
    if (dp[l + 1][r - 1] == 0)
         cran = fans(l + 1, r - 1);
    else
        cran = dp[l + 1][r - 1];
    int dubalar = 0;
    if (dp[l + 1][r] == 0)
        fans1 = fans(l + 1, r);
    else
        fans1 = dp[l + 1][r];
    if (dp[l][r - 1] == 0)
         fans2 = fans(l, r - 1);
    else
        fans2 = dp[l][r - 1];
    if (a[l] == a[r])
        dubalar = (cran + 1) % MOD;

    return dp[l][r] = (((fans1 + fans2) % MOD - cran + MOD) % MOD + dubalar) % MOD;
}

int main() {
    // freopen("matching.in", "r", stdin);
    //freopen("matching.out", "w", stdout);
    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            dp[i][j] = 0;
    a.resize(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];
    fans(0, n - 1);
    cout << dp[0][n - 1] << endl;
  /*  for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++)
            cout << dp[i][j] << ' ';

        cout << endl;
    }*/
}