Ivka si z akcie Enormne Giganticky Obrovskej Inštitúcie doniesla kopu nových zvieracích kamarátov (napríklad koalky a gumené kačičky) a chce si ich uložiť na poličku. Všetky sa jej ale do jedného radu nezmestia. Chce ich teda rozdeliť na skupinky, pričom každá má 2 rady. Záleží jej však na tom, aby rozdelenie vyzeralo pekne. Preto zvieratká umiestňuje nasledovne:

Na začiatku má zvieratká zoradené v jednom rade. Ich poradie počas procesu nebude meniť. Zoberie zo začiatku radu niekoľko zvieratiek. Tieto budú tvoriť zadný rad novej skupinky. Ich poradie sa nezmení. Potom znovu zoberie niekoľko zvieratiek. Tieto budú tvoriť predný rad tej istej skupinky. Aby to vyzeralo pekne, rady nemusia byť rovnako dlhé, ale v prednom a zadnom rade skupinky musí byť rovnaké prvé s prvým a posledné s posledným zvieratkom.

Keďže Ivka mešká a už dávno mala byť na sústredku, nestíha si ich uložiť. Než sa vráti, chcela by si rozmyslieť, ako ich rozloží. Má ale strašne veľa možností. Pomôžte jej zistiť, koľkými spôsobmi môže takto rozložiť zvieratká.

Úloha

Ivka má $n$ zvieratiek, ktoré sú vopred zoradené v jednom rade. Každé zvieratko má svoj typ. Potrebuje ich rozdeliť na ľubovoľné množstvo skupín, každú s dvoma radmi. Skupina je súvislý interval zvieratiek a oba rady sú súvislé podintervaly skupiny. Pri rozdeľovaní teda najprv zaplní celú 1. skupinu. Prvých niekoľko zvieratiek bude tvoriť jej zadný rad a následnie niekoľko zvieratiek jej predný rad. Podobne zaplní celú druhú skupinu, potom celú tretiu $\dots$

Má navyše nasledovné podmienky: V každej skupine musí byť typ prvého zvieraťa predného radu rovnaký ako typ prvého zvieraťa zadného radu a podobne typ posledného zvieraťa predného radu rovnaký s typom posledného zvieraťa zadného radu. Každý rad musí obsahovať aspoň 2 zvieratá. Každé zviera musí byť zaradené v nejakej skupine v rade.

Zistite, koľkými spôsobmi sa dajú zvieratká rozdeliť na základe požiadaviek. Toto číslo môže byť veľké, preto zistite len jeho zvyšok po delení $10^9+7$.

Formát vstupu

V prvom riadku vstupu je číslo $n$ ($4 \leq n \leq 10^6$) udávajúce počet zvieratiek, ktoré treba na poličku uložiť.

V druhom riadku vstupu je $n$ čísel oddelených medzerou $a_1, a_2, …, a_n$ udávajúcich typy zvieratiek. Pre všetky $a_i$ platí $1 \leq a_i \leq 10^{18}$

Úloha má 3 sady s nasledovnými obmedzeniami:

Formát výstupu

Vypíš jeden riadok a v ňom jedno celé číslo - počet možností, ako môže Ivka rozmiestniť zvieratká na poličku modulo $10^9+7$.

Príklady

9
5 8 6 5 6 4 3 4 3

1

Jediný možný spôsob je rozdelenie 5 8 6 | 5 6 | 4 3 | 4 3

5
47 47 42 42 42

0

8
1 2 1 2 1 2 1 2

4

Možné rozdelenia sú nasledovné, všetky intervaly začínajú 1 a končia 2:

1 2 | 1 2 1 2 1 2

1 2 1 2 | 1 2 1 2

1 2 1 2 1 2 | 1 2

1 2 | 1 2 | 1 2 | 1 2 - v tomto prípade Ivka vytvorila dve skupiny.