병사들

막사에서 아침 점호를 할 때, 그곳에 있는 모든 병사는 한 줄로 서야 한다. 다만 아무 순서로나 설 수는 없고, 키 순서대로, 즉 가장 큰 병사부터 가장 작은 병사까지 정렬된 순서로 서야 한다. 이때 가장 큰 병사는 줄의 왼쪽 끝과 오른쪽 끝 중 어느 쪽에 서도 된다. 병사들이 올바르게 설 수 있는 방법의 수를 구하도록 도와주자.

두 배치는 다음 조건을 모두 만족할 때에만 같은 것으로 본다. 모든 병사에 대해, 두 배치에서 그 병사의 왼쪽 이웃이 서로 같고(또는 두 배치 모두 왼쪽 이웃이 없고), 오른쪽 이웃도 서로 같다(또는 두 배치 모두 오른쪽 이웃이 없다).

다음을 수행하는 프로그램을 작성하여라.

• 표준 입력에서 막사에 있는 모든 병사의 정보를 읽는다.
• 병사들을 키가 큰 순서부터 작은 순서까지 정렬해 한 줄로 세우는 배치의 수를 구한다.
• 그 수의 마지막 네 자리 십진수를 표준 출력에 출력한다.

첫째 줄에 막사에 있는 병사의 수를 나타내는 정수 $n$ ($1 \le n \le 200\,000$)이 주어진다. 둘째 줄에는 $n$개의 정수 $w_i$ ($1 \le w_i \le 10^9$)가 공백 하나로 구분되어 주어지며, 입력 순서대로 각 병사의 키를 나타낸다.

병사들을 키 순서로 한 줄로 세우는 배치의 수의 마지막 네 자리 십진수를 출력의 유일한 줄에 출력한다. 이 수가 $1000$ 이상이면 항상 네 자리로 출력하며, 필요하면 앞을 0으로 채운다. $1000$보다 작으면 그 수의 모든 자리를 그대로 출력한다.

키가 2 3 1 4 4 5 2인 입력에 대한 모든 올바른 배치는 아래와 같다. 각 항목은 병사의 입력 순서 번호와 괄호 안의 키를 나타낸다.

• 3 (1), 1 (2), 7 (2), 2 (3), 4 (4), 5 (4), 6 (5)
• 3 (1), 7 (2), 1 (2), 2 (3), 4 (4), 5 (4), 6 (5)
• 3 (1), 1 (2), 7 (2), 2 (3), 5 (4), 4 (4), 6 (5)
• 3 (1), 7 (2), 1 (2), 2 (3), 5 (4), 4 (4), 6 (5)
• 6 (5), 4 (4), 5 (4), 2 (3), 1 (2), 7 (2), 3 (1)
• 6 (5), 5 (4), 4 (4), 2 (3), 1 (2), 7 (2), 3 (1)
• 6 (5), 4 (4), 5 (4), 2 (3), 7 (2), 1 (2), 3 (1)
• 6 (5), 5 (4), 4 (4), 2 (3), 7 (2), 1 (2), 3 (1)

총 $8$가지이므로 이 입력의 답은 $8$이다.