Yapacak Bir Şey Yokken ve Evde Sadece Bir Permütasyon Varken#12857

Yapacak Bir Şey Yokken ve Evde Sadece Bir Permütasyon Varken

2 saniye
256 megabayt
Çok zor

Size 'den 'ye kadar olan sayıların bir (p_1, p_2, \ldots, p_n) permütasyonu veriliyor.

Bu permütasyon üzerinde aşağıdaki işlemi yapabilirsiniz:

Bir iterasyonda şunları yaparsınız:

Bu iterasyonu, elde edilen permütasyonuna, o birim permütasyon olana (yani (1, 2, 3, \ldots, n)) eşit olana) kadar uygularsınız. Bu ne kadar zaman alacak? Bu sayı çok büyük olabileceğinden, onu 10^9+7 modunda yazdırın.

Bir permütasyonu, öyle bir indisi varsa ki tüm j<i için p_j = q_j ve ayrıca p_i<q_i olsun, permütasyonundan leksikografik olarak küçük kabul edilir.

Giriş

Birinci satırda bir tam sayı (1 \le n \le 2\cdot 10^5) — permütasyonun uzunluğu verilir.

İkinci satırda tam sayı p_1, p_2, \ldots, p_n (1 \le p_i \le n, tüm sayılar ikişer ikişer farklıdır) — permütasyonun elemanları verilir.

Çıktı

Süreç sona erene kadar geçecek saniye sayısını 10^9+7 modunda yazdırın.

Örnekler

Örnek 1

Loading
Loading

Örnek 2

Loading
Loading

Not

Birinci örnekte elimizde şunlar var:

(1, 4, 2, 3) \to (1, 4, 3, 2) \to (1, 3, 4, 2): saniye.

(1, 3, 4, 2) \to (1, 3, 2, 4): saniye.

(1, 3, 2, 4) \to (1, 2, 3, 4) \to (1, 2, 4, 3): saniye.

(1, 2, 4, 3) \to (1, 2, 3, 4): saniye.

Toplamda saniye.