Tamamen Sıralanmamış Diziler#9882
Kısa süre önce NASA'nın — Ulusal Sıralama Algoritmaları Derneği'nin (National Association for Sorting Algorithms) — baş bilim insanı olarak atandınız. Tebrikler! Asıl göreviniz, ekibinizin geliştirdiği sıralama algoritmalarını test etmek. Neyse ki bu yıl NASA'nın bütçesi oldukça yüksek ve sıralama algoritmalarını test etmek için en yeni tam sayıları satın almayı başardınız.
Baş bilim insanı olarak, algoritmaların en kötü girdiler üzerindeki davranışlarına göre değerlendirildiğini çok iyi biliyorsunuz. Bu nedenle, sıralama algoritmalarını test etmek için mümkün olduğunca sıralanmamış dizilere ihtiyacınız var.
(a_1, \ldots, a_n) sayı dizisi verilsin. Eğer j > k olan tüm indisler için a_j \ge a_k ve j < k olan tüm indisler için a_j \le a_k ise, a_k elemanının kendi yerinde olduğunu söyleyeceğiz. Örneğin,
dizisinde , ikinci ve elemanları kendi yerindedir. Dikkat edilirse, bir dizi ancak ve ancak tüm elemanları kendi yerindeyse sıralanmıştır. Eğer bir dizinin hiçbir elemanı kendi yerinde değilse, bu diziye tamamen sıralanmamış denir.
Verilen tam sayı dizisinin elemanları yeniden düzenlenerek kaç tane tamamen sıralanmamış dizi elde edilebilir? (b_1, \ldots, b_n) ve (c_1, \ldots, c_n) dizileri, eğer bazı i \in \{1, \ldots, n\} indisi için b_i \ne c_i ise farklı kabul edilir. Bu sayı çok büyük olabileceğinden, sonucu 10^9 + 9 modülüne göre yazdırın.
İlk satırda bir tam sayı n~(1 \le n \le 5000) verilir.
İkinci satırda tane tam sayı a_1, \ldots, a_n~(0 \le a_i \le 10^9) verilir.
a_1, \ldots, a_n elemanlarının permütasyonuyla elde edilebilecek tamamen sıralanmamış dizilerin sayısını, 10^9 + 9 modülüne göre tek bir tam sayı olarak yazdırın.
Örnek 1
Örnek 2
Örnek 3