#include <iostream>
#include <stdio.h>
#include <cmath>
#include <math.h>
#include <cstdio>
#include <string>
#include <algorithm>
#include <functional>
#include <stack>
#include <list>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <iomanip>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <regex>
#include <sstream>

using namespace std;

const int mod = 1e9;
int INF = 1e9;

int main() {
	long long n;
	cin >> n;
	vector < long long > a(n);

	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}

	vector < vector < long long > > dp(n, vector < long long >(n, 0));

	for (int i = 0; i < n; i++) {
		dp[i][i] = 1;
	}

	for (int i = 0; i < n - 1; i++) {
		dp[i][i + 1] = 2;
		if (a[i] == a[i + 1]) {
			dp[i][i + 1]++;
		}
	}

	for (int len = 3; len <= n; len++) {
		for (int i = 0; i < n; i++) {
			int j = i + len - 1;
			if (j >= n)
				continue;

			dp[i][j] = (dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1] + mod) % mod;
			if (a[i] == a[j]) {
				dp[i][j] += dp[i + 1][j - 1] + 1;
			}
			dp[i][j] %= mod;
		}
	}

	cout << dp[0][n - 1] % mod;
	//system("pause");
}