Memes

Gimi a devenit noul coordonator de divertisment al platformei GuguștiucShorts! El știe că pe platforma lui sunt înscriși $N$ utilizatori, iar pentru fiecare user $i$ știe ce memă (eng. meme --- o idee, de obicei hazlie, materializată într-o imagine, un clip sau un text, care se răspândește prin intermediul internetului) $v_i$ i-ar apărea dacă ar intra pe rețea. Fiecare memă este codificată printr-un număr natural.

Cum Gimi este un coordonator responsabil, el poate să modifice conținutul utilizatorului $i \ (1 \leq i \leq N)$ preluând conținut:

• din dreapta: dacă $i < N$, mema utilizatorului $i$ devine aceeași cu mema utilizatorului $i + 1$;
• din stânga: dacă $i > 1$, mema utilizatorului $i$ devine aceeași cu mema utilizatorului $i - 1$.

De exemplu, dacă șirul de meme-uri era $[1, 2, 3, 4]$ și aplicăm o operație asupra utilizatorului $2$, din dreapta, șirul devine $[1, 3, 3, 4]$, iar dacă mai aplicăm încă o operație asupra șirului rezultat pe poziția $3$, din dreapta, șirul devine $[1, 3, 4, 4]$. De asemenea, dacă facem o operație asupra utilizatorului $2$, din stânga, pe șirul $[1, 2, 3, 4]$, obținem șirul $[1, 1, 3, 4]$.

Cerință

Gimi, curios de fel, vrea să afle, plecând de la un șir inițial $v$, în câte șiruri distincte îl poate transforma aplicând operația descrisă mai sus de oricâte (eventual $0$) de ori. Răspunsul va fi afișat modulo $10^9 + 7$.

Date de intrare

Pe prima linie a fișierului de intrare memes.in se găsește un număr natural $N$, care reprezintă numărul de utilizatori ai platformei. Pe următoarea linie din fișierul de intrare se va găsi un șir $v$ de $N$ numere naturale, unde $v_i$ reprezintă mema asignată utilizatorului $i$.

Date de ieșire

În fișierul de ieșire memes.out se va afișa un singur număr, care reprezintă numărul de șiruri distincte la care poate ajunge Gimi aplicând operația descrisă mai sus, modulo $10^9 + 7$.

Restricții și precizări

• $1 \leq N \leq 10 \ 000$
• $1 \leq v_i \leq N$ pentru orice $1 \leq i \leq N$.
• Doua șiruri se consideră distincte dacă diferă în cel puțin o poziție.

Exemplul 1

memes.in

3
1 2 1

memes.out

7

Explicație

Șirurile posibile la care putem ajunge sunt: $(1 \ 1 \ 1)$, $(1 \ 1 \ 2)$, $(1 \ 2 \ 1)$, $(1 \ 2 \ 2)$, $(2 \ 1 \ 1)$, $(2 \ 2 \ 1)$, $(2 \ 2 \ 2)$, deci $7$ șiruri distincte.

Exemplul 2

memes.in

3
1 1 1

memes.out

1

Explicație

Indiferent de câte ori aplicăm operația, ajungem la șirul inițial $(1 \ 1 \ 1)$. Deci avem un singur șir distinct.