시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB105141320.968%

문제

A = (a1, a2, …, an)을 n개의 원소를 가진 집합 X = {1,2,3,…,n}의 순열이라고 하자. 즉, i ≠ j이면, ai ≠ aj이고 (1 ≤ i, j ≤ n), 모든 i (1 ≤ i ≤ n)에 대해서 ai∈X이다. 순열 A에 대해서 수열 P(A) = (p1, p2, …, Pn-1)을 다음과 같이 정의한다.

만약 ai > ai+1이면, pi = 0이고, 그렇지 않으면 pi = 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으로 나눈 나머지만 출력한다.

예제 입력 1

4
1 3 2 4

예제 출력 1

5