8. Masaker v Kratarií

Kedysi dávno, v časoch, keď vo svete ešte vládla mágia a po vonku si voľne behali zázračné bytosti, v jednej ďalekej krajine s názvom Krataria, žilo \(N\) čarodejov. A ako iste viete, každý poriadny čarodej potrebuje svoju vlastnú vežu, v ktorej bude vykonávať svoje experimenty, vymýšľať nové kúzla, variť lektvary a inak čarovať… Taktiež je celkom logické, že keď budú mať dvaja čarodejovia vežu s rovnakou výškou, nebudú sa mať radi a nedopadne to dobre. Preto sa rozhodli, že spolu budú priateľsky súperiť o to, kto bude mať akú výšku veže. Po dlhoročnom súperení boli nakoniec zoradení a každý z nich vedel, ktorá z veží vysokých od \(1\) po \(N\) mu patrí. Keď si už obyvatelia konečne mysleli, že budú mať pokoj, čarodejovia začali s výstavbou svojich veží a rozruch pokračoval. Každý čarodej si vybral nejaké miesto na hranici Kratarie, kde si svoju vežu postavil. Tieto veže boli však také obrovské a drahé na výstavbu, že sa Krataria ocitla v kríze a ich výstavba trvala dlhé roky. Už to vyzeralo tak, že sa výstavba bude musieť zrušiť, avšak stálo to za to. Krataria sa od momentu dokončenia výstavby stala najmocnejšiou krajinou na celom svete. Nikto sa nikdy neodvážil na ňu zaútočit. Tak to aspoň hovorí legenda o Kratarii.

Existuje ešte jedna legenda, z ktorej sa síce zachovali iba útržky, ale spomína sa v nej \(N\) veží:

V legende sa spomína pustatina, v ktorej žijú draky a celá táto pustatina je obklopená \(N\) vežami. Drakom sa tieto veže nepáčia a preto možno niekoľkokrát zničili niektoré najvyššie poschodia niektorých veží. Tiež sa spomína presný popis toho, ako draky ničia poschodia, ale nie to, či sa to aj naozaj stalo alebo koľkokrát sa to stalo. Draky ničia poschodia tak, že každú vežu znížia na minimum jej výšky a výšky predošlej veže.

Dnes sa nám podarilo odkryť pozostatky poslednej veže. Som presvedčený, že tieto pozostatky patria vežiam z legiend. Teraz už len zostáva zistiť, ako vyzerali veže pôvodne, teda koľko možností spĺňa to, čo sa píše v legendách.

denník archeologickej jednotky 0471

Úloha

Na vstupe dostanete postupnosť \(N\) čísel (\(1 \le P_i \le N\)).

Nájdite počet permutácií čísel \(1\) až \(N\), z ktorých je možné dosiahnuť postupnosť \(P\) opakovaním (možno aj 0-krát) nasledovnej operácie:

Pre každé \(1 \le i \le N\), \(b_i = \min(a_{i-1}, a_i)\), pričom \(n = 0\), kde \(a\) je postupnosť pred operáciou a \(b\) postupnosť po operácii.

Na štandardný výstup vypíšte hľadaný počet modulo 1000000007.

Formát vstupu

Na prvom riadku vstupu sa nachádza číslo \(N\) (\(1 \le N \le 1000000\)). Na druhom riadku je výsledná postupnosť čísel \(P\), zapísaná ako \(N\) medzerami oddelených čísel. (\(1 \le P_i \le N\))

Formát výstupu

Vypíšte jedno číslo - počet permutácií, z ktorých vieme dostať postupnosť \(P\) opakovaním vyššie uvedenej operácie. Keďže tento počet môže byť veľmi veľký, vypisujte ho modulo \(10^9+7\).

Príklady

Input:

4
2 1 1 2

Output:

2

Postupnosti \((3, 1, 4, 2)\) a \((4, 1, 3, 2)\) spĺňajú podmienky.

Input:

6
6 3 1 1 2 2

Output:

0

Neexistuje žiadna permutácia, ktorá spĺňa podmienky.

Input:

7
4 3 3 1 1 1 2

Output:

18