#include <iostream>
#define LEWY 0
#define PRAWY 1

int*** t;
int* a;
int n;

int policz(int i, int j, int k)
{
    if (t[i][j][k] == -1) {
        if (k == 0) {
            t[i][j][k] = ((a[i] < a[i + 1]) ? policz(i + 1, j, 0) : 0) + ((a[i] < a[j]) ? policz(i + 1, j, 1) : 0);
        }
        else {
        	t[i][j][k] = ((a[j] > a[j - 1]) ? policz(i, j - 1, 1) : 0) + ((a[i] < a[j]) ? policz(i, j - 1, 0) : 0);
        }
    }
    return t[i][j][k]%1000000000;
}

int main() {
    std::cin >> n;

    t = new int**[n];
    a = new int[n];

	for (int i = 0; i < n; ++i) {
		std::cin >> a[i];
        t[i] = new int*[n];
        for (int j = 0; j < n; ++j) {
            t[i][j] = new int[2];
            t[i][j][LEWY] = -1;
            t[i][j][PRAWY] = -1;
        }
        t[i][i][LEWY] = 0;
        t[i][i][PRAWY] = 1;
    }

    std::cout << policz(0, n-1, LEWY) + policz(0, n - 1, PRAWY);

    return 0;
}