2395번 - 순열의 개수

문제

A = (a₁, a₂, …, a_n)을 n개의 원소를 가진 집합 X = {1,2,3,…,n}의 순열이라고 하자. 즉, i ≠ j이면, a_i ≠ a_j이고 (1 ≤ i, j ≤ n), 모든 i (1 ≤ i ≤ n)에 대해서 a_i∈X이다. 순열 A에 대해서 수열 P(A) = (p₁, p₂, …, P_n-1)을 다음과 같이 정의한다.

만약 a_i > a_i+1이면, p_i = 0이고, 그렇지 않으면 p_i = 1이다. (1 ≤ i ≤ n-1). 문제는 n과 순열 A가 주어질 때, P(A) = P(B)를 만족하는 순열의 수를 구하여 출력하는 것이다.

예를 들어 A=(1,3,2,4)이라면, P(A) = (1,0,1)이다. 아래와 같은 순열 B에 대해서 P(A)=P(B)가 성립한다.

(1,3,2,4), (1,4,2,3), (2,3,1,4), (2,4,1,3), (3,4,1,2)

입력

첫째 줄에 집합 X의 크기 n이 주어진다. n은 5,000이하인 양의 정수이다. 둘째 줄에 X의 순열 하나가 주어진다. 순열은 n개의 정수로 나타내고, 이들 사이에 공백이 있다.

출력

첫째 줄에 주어진 순열 A에 대하여 P(A) = P(B)를 만족하는 순열의 수를 출력한다. 이때 A 자신도 순열의 수를 헤아릴 때 포함시킨다. 답이 매우 클 수 있으니 1,000,000,000으로 나눈 나머지만 출력한다.

제한

힌트