순열의 개수

길이 n의 수열 A = (a_1, a_2, ..., a_n)가 집합 X = {1, 2, 3, ..., n}의 순열이라고 하자. 즉, 서로 다른 위치에는 서로 다른 값이 있고, 모든 값은 X에 속한다.

순열 A에 대해 길이 n - 1의 수열 P(A) = (p_1, p_2, ..., p_{n-1})를 다음과 같이 정의한다. 각 i(1 <= i <= n - 1)에 대해 a_i > a_{i+1}이면 p_i = 0이고, 그렇지 않으면 p_i = 1이다.

n과 순열 A가 주어졌을 때, P(B) = P(A)를 만족하는 집합 X의 순열 B의 개수를 구하라. 순열 A 자신도 개수에 포함한다.

A = (1, 3, 2, 4)라면 P(A) = (1, 0, 1)이다. 이 패턴을 만족하는 순열은 (1, 3, 2, 4), (1, 4, 2, 3), (2, 3, 1, 4), (2, 4, 1, 3), (3, 4, 1, 2)로 모두 5개이다.

첫째 줄에 집합 X의 크기 n이 주어진다. n은 5,000 이하인 양의 정수이다.

둘째 줄에 집합 X의 순열 A가 주어진다. 순열은 공백으로 구분된 n개의 정수로 주어진다.

P(B) = P(A)를 만족하는 순열 B의 개수를 첫째 줄에 출력한다. 답이 매우 클 수 있으므로 1,000,000,000으로 나눈 나머지를 출력한다.