Görüləcək iş olmayanda, evdə isə yalnız permutasiya olanda#12857

Görüləcək iş olmayanda, evdə isə yalnız permutasiya olanda

2 saniyə
256 meqabayt
Çox çətin

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:

Bir iterasiyada aşağıdakıları edirsiniz:

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.

Giriş

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.

Çıxış

Proses bitənə qədər keçəcək saniyələrin sayını 10^9+7 moduluna görə çıxarın.

Nümunələr

Nümunə 1

Loading
Loading

Nümunə 2

Loading
Loading

Qeyd

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ə.