Sequenze completamente non ordinate

Recentemente siete stati nominati ricercatore capo presso la NASA — la National Association for Sorting Algorithms (Associazione Nazionale per gli Algoritmi di Ordinamento). Congratulazioni! Il vostro compito principale è testare gli algoritmi di ordinamento sviluppati dal vostro team. Fortunatamente, quest'anno la NASA dispone di un budget consistente, e siete riusciti ad acquistare i più recenti numeri interi per testare gli algoritmi di ordinamento.

In qualità di ricercatore capo, sapete bene che gli algoritmi vengono valutati in base al loro comportamento sui dati di input peggiori. Pertanto, per testare gli algoritmi di ordinamento, avete bisogno di sequenze che siano il più possibile non ordinate.

Sia data una sequenza di numeri (a_1, \ldots, a_n). Diremo che l'elemento a_k è al suo posto se a_j \ge a_k per tutti gli indici j > k e a_j \le a_k per tutti gli indici j < k. Ad esempio, nella sequenza

sono al loro posto gli elementi $1$, la seconda occorrenza di $3$ e $4$. Osserviamo che la sequenza è ordinata se e solo se tutti i suoi elementi sono al loro posto. Una sequenza si dice completamente non ordinata se nessuno dei suoi elementi è al suo posto.

Quante sequenze completamente non ordinate si possono ottenere permutando gli elementi di una data sequenza di numeri interi? Due sequenze (b_1, \ldots, b_n) e (c_1, \ldots, c_n) sono considerate diverse se b_i \ne c_i per qualche indice i \in \{1, \ldots, n\}. Poiché questo numero può essere molto grande, stampatelo modulo 10^9 + 9.