Number of Permutations

Let A = (a_1, a_2, ..., a_n) be a permutation of the set X = {1, 2, 3, ..., n}. That is, different positions contain different values, and every value belongs to X.

For a permutation A, define a sequence P(A) = (p_1, p_2, ..., p_{n-1}) of length n - 1 as follows. For each i(1 <= i <= n - 1), if a_i > a_{i+1}, then p_i = 0; otherwise, p_i = 1.

Given n and a permutation A, count the permutations B of X such that P(B) = P(A). The permutation A itself is included in the count.

When A = (1, 3, 2, 4), P(A) = (1, 0, 1). The permutations with this same pattern are (1, 3, 2, 4), (1, 4, 2, 3), (2, 3, 1, 4), (2, 4, 1, 3), and (3, 4, 1, 2), so the count is 5.

The first line contains the size n of the set X. The value n is a positive integer not greater than 5,000.

The second line contains the permutation A of X, written as n space-separated integers.

Print the number of permutations B such that P(B) = P(A). Since the answer can be very large, print it modulo 1,000,000,000.