완전히 정렬되지 않은 수열

당신은 최근 NASA(National Association for Sorting Algorithms)의 수석 과학자로 승진했다. 축하한다! 주요 업무는 팀이 만든 정렬 알고리즘을 테스트하는 것이다. 올해 예산이 넉넉해서 테스트에 쓸 최신 정수들을 구입할 수 있었다.

수석 과학자로서 알고리즘은 최악의 입력에서 보이는 동작으로 평가된다는 것을 알고 있다. 정렬 알고리즘을 테스트하려면 최대한 정렬되지 않은 수열이 필요하다.

수열 $(a_1, \ldots, a_n)$이 주어졌을 때, 원소 $a_k$는 $j > k$인 모든 인덱스 $j$에 대해 $a_j \ge a_k$이고, $j < k$인 모든 인덱스 $j$에 대해 $a_j \le a_k$이면 정렬되어 있다고 한다. 예를 들어 $(1, 3, 2, 3, 4, 6, 5, 5)$에서 정렬되어 있는 원소는 1, 두 번째 3, 4이다. 수열은 모든 원소가 정렬되어 있을 때에만 정렬된 수열이다. 어떤 원소도 정렬되어 있지 않은 수열을 완전히 정렬되지 않은 수열이라고 한다.

정수 수열이 주어졌을 때, 원소를 재배열하여 만들 수 있는 완전히 정렬되지 않은 수열의 개수를 구하라. 두 수열 $(b_1, \ldots, b_n)$과 $(c_1, \ldots, c_n)$은 어떤 인덱스 $i$에 대해 $b_i \ne c_i$이면 서로 다른 수열이다. 개수가 매우 클 수 있으므로 $10^9 + 9$로 나눈 나머지를 출력한다.

첫 줄에 정수 $n$이 주어진다 ($1 \le n \le 5000$). 둘째 줄에는 정수 $a_1, \ldots, a_n$이 주어진다 ($0 \le a_i \le 10^9$).

$a_1, \ldots, a_n$을 재배열하여 만들 수 있는 완전히 정렬되지 않은 수열의 개수를 $10^9 + 9$로 나눈 나머지로 한 줄에 출력한다.