Tamamilə çeşidlənməmiş ardıcıllıqlar

Bu yaxınlarda siz NASA — Çeşidləmə Alqoritmləri üzrə Milli Assosiasiyanın (National Association for Sorting Algorithms) aparıcı elmi işçisi təyin edilmisiniz. Təbrik edirik! Sizin əsas vəzifəniz — komandanızın hazırladığı çeşidləmə alqoritmlərini test etməkdir. Xoşbəxtlikdən, bu il NASA-nın böyük büdcəsi var və siz çeşidləmə alqoritmlərini test etmək üçün ən yeni tam ədədlər əldə edə bilmisiniz.

Aparıcı elmi işçi olaraq, siz yaxşı bilirsiniz ki, alqoritmlər ən pis giriş məlumatlarında necə davranmasına görə qiymətləndirilir. Buna görə də çeşidləmə alqoritmlərini test etmək üçün sizə mümkün qədər çeşidlənməmiş ardıcıllıqlar lazımdır.

Tutaq ki, (a_1, \ldots, a_n) ədədlər ardıcıllığı verilib. Deyəcəyik ki, a_k elementi öz yerindədir, əgər bütün j > k indeksləri üçün a_j \ge a_k və bütün j < k indeksləri üçün a_j \le a_k olarsa. Məsələn,

ardıcıllığında $1$, $3$-ün ikinci təkrarı və $4$ elementləri öz yerlərindədir. Qeyd edək ki, ardıcıllıq o zaman və yalnız o zaman çeşidlənmişdir ki, onun bütün elementləri öz yerlərində olsun. Əgər ardıcıllığın heç bir elementi öz yerində deyilsə, bu ardıcıllıq tamamilə çeşidlənməmiş adlanır.

Verilmiş tam ədədlər ardıcıllığının elementlərini yenidən düzərək neçə tamamilə çeşidlənməmiş ardıcıllıq əldə etmək olar? Əgər hər hansı i \in \{1, \ldots, n\} indeksi üçün b_i \ne c_i olarsa, (b_1, \ldots, b_n) və (c_1, \ldots, c_n) ardıcıllıqları fərqli hesab olunur. Bu say çox böyük ola biləcəyi üçün, onu 10^9 + 9 modulu üzrə çıxarın.