Sizə -dən -ə qədər olan ədədlərin (p_1, p_2, \ldots, p_n) permutasiyası verilib.
Onunla aşağıdakı əməliyyatı yerinə yetirə bilərsiniz:
-nin iki qonşu elementinin yerini dəyişə bilərsiniz. Bu əməliyyat düz bir saniyə çəkir.
Bir iterasiyada aşağıdakıları edirsiniz:
Leksikoqrafik sıralamada (p_1, p_2, \ldots, p_n) permutasiyasından bilavasitə əvvəl gələn (q_1, q_2, \ldots, q_n) permutasiyasına baxın, yəni leksikoqrafik olaraq -dən kiçikdir və "onların arasında" heç bir permutasiya yoxdur. Məsələn, p = (2, 3, 1) üçün q = (2, 1, 3), p = (3, 1, 2, 4) üçün q = (2, 4, 3, 1), p = (1, 4, 2, 3) üçün isə q = (1, 3, 4, 2) olur.
permutasiyasını mümkün olan ən az sayda əməliyyatla permutasiyasına çevirin. Məsələn, (1, 4, 2, 3) permutasiyasını (1, 3, 4, 2) permutasiyasına çevirmək üçün ən azı əməliyyat lazımdır: (1, 4, 2, 3) \to (1, 4, 3, 2) \to (1, 3, 4, 2).
Bu iterasiyanı alınan permutasiyasına o, eynilik permutasiyası olana (yəni (1, 2, 3, \ldots, n)) bərabər olana) qədər tətbiq edirsiniz. Bu nə qədər vaxt aparacaq? Bu ədəd çox böyük ola bildiyi üçün onu 10^9+7 moduluna görə çıxarın.
permutasiyası permutasiyasından leksikoqrafik olaraq kiçik sayılır, əgər elə indeksi varsa ki, bütün j<i üçün p_j = q_j, həmçinin p_i<q_i olsun.
Birinci sətirdə bir tam ədəd (1 \le n \le 2\cdot 10^5) — permutasiyanın uzunluğu verilir.
İkinci sətirdə tam ədəd p_1, p_2, \ldots, p_n (1 \le p_i \le n, bütün ədədlər cüt-cüt fərqlidir) — permutasiyanın elementləri verilir.
Proses bitənə qədər keçəcək saniyələrin sayını 10^9+7 moduluna görə çıxarın.
Nümunə 1
Nümunə 2
Birinci nümunədə alırıq:
(1, 4, 2, 3) \to (1, 4, 3, 2) \to (1, 3, 4, 2): saniyə.
(1, 3, 4, 2) \to (1, 3, 2, 4): saniyə.
(1, 3, 2, 4) \to (1, 2, 3, 4) \to (1, 2, 4, 3): saniyə.
(1, 2, 4, 3) \to (1, 2, 3, 4): saniyə.
Ümumilikdə saniyə.