Entirely Unsorted Sequences

You have recently been promoted to lead scientist at NASA, the National Association for Sorting Algorithms. Congratulations! Your main responsibility is testing the sorting algorithms that your team develops. Fortunately, NASA has a large budget this year, and you were able to buy some state-of-the-art integers to test the sorting algorithms with.

As the lead scientist, you are well aware that algorithms are judged by their behaviour on worst-case inputs. So, to test sorting algorithms, you need sequences that are as unsorted as possible.

Given a sequence of numbers (a_1, \ldots, a_n), we say that an element a_k is sorted if a_j \ge a_k for all indices j > k and a_j \le a_k for all indices j < k. For example, in the sequence

the sorted elements are $1$, the second occurrence of $3$, and $4$. Note that a sequence is sorted if and only if all of its elements are sorted. A sequence is called entirely unsorted if none of its elements is sorted.

Given a sequence of integers, how many entirely unsorted sequences can be obtained by permuting its elements? Two sequences (b_1, \ldots, b_n) and (c_1, \ldots, c_n) are considered different if b_i \ne c_i for some index i \in \{1, \ldots, n\}. Since this number may be very large, output it modulo 10^9 + 9.