bt

John și-a investit toate economiile în criptomonede. Acum încearcă să mai recupereze din bani, trecând pe dieta campionilor (brânză topită).

El are o cutie circulară cu $N$ bucăți de brânză (de mai multe tipuri), iar în fiecare zi ia câte una din cutie. Acesta are grijă ca înainte și după ce ia o bucată din cutie, oricare două bucăți adiacente rămase să fie de alt tip.

John s-a apucat să numere în câte moduri poate să termine cutia.

Formal, se dă un vector circular $v_1, v_2, \ldots, v_N$. Vrem să scoatem din el câte un element până rămâne gol vectorul. În urma fiecărei scoateri, inclusiv înaintea primei scoateri, nu trebuie să existe 2 poziții consecutive în vector cu aceeași valoare în ele.

În exemplul din dreapta, bucățile de brânză de pe pozițiile $A$ și $B$ au fost deja luate. Singurele bucăți pe care le-am putea scoate acum ar fi $E$ sau $G$. Dacă am scoate bucata $C$, atunci bucățile $D$ si $H$, ambele de tipul $2$, ar deveni vecine. Dacă l-am scoate pe $D$, $C$ și $E$ ar deveni vecine, deși sunt ambele de tipul $1$, etc.

Cerință

Să se numere în câte moduri putem goli vectorul respectând regulile din enunț (modulo $1\ 000\ 000\ 007$).

Un mod de a goli vectorul este definit de ordinea indicilor care părăsesc vectorul. De exemplu, pentru $N = 4$, sunt $4! = 24$ de moduri diferite de a goli vectorul (dintre care nu toate respecța regulile din enunț).

Date de intrare

Pe prima linie a fișierului de intrare se găsește un singur număr natural $N$ reprezentând lungimea vectorului.

Pe a doua linie se găsesc $N$ numere naturale, $v_1, v_2, \ldots, v_N$, reprezentând valorile din vector.

Date de ieșire

În fişierul de ieşire se va afişa un singur număr, reprezentând numărul de moduri de a goli vectorul.

Problema are 2 moduri de punctare: vectorul este circular (pentru $100\%$ din punctajul de pe un test), sau vectorul nu este circular – $v_1$ și $v_N$ nu sunt considerați vecini (pentru $80\%$ din punctaj).

Inițial, numărul afișat este comparat cu răspunsul corespunzător vectorului circular pentru $100\%$ din punctajul testului.

Dacă răspunsurile diferă, numărul este apoi comparat cu răspunsul corespunzător vectorului normal ($v_1$ și $v_N$ nu sunt considerați vecini) pentru $80\%$ din punctajul testului.

Restricții

• $1\leq N \leq 500$
• $1 \leq v_i \leq N$

Exemple

bt.in

4
1 2 1 2

bt.out

0

Orice element am scoate, am avea ulterior doi de $1$ vecini, sau doi de $2$ vecini, deci nu putem goli vectorul. Dacă am avea un delimitator între ultimul element și primul, răspunsul ar fi $8$. Secvențele de indici corecte în acest caz ar fi:

• $1$, $2$, $3$, $4$
• $1$, $2$, $4$, $3$
• $1$, $4$, $2$, $3$ (vectorul ar arăta: $(1, 2, 1, 2) \rightarrow (2, 1, 2) \rightarrow (2, 1) \rightarrow (1) \rightarrow$ gol)
• $1$, $4$, $3$, $2$
• $4$, $1$, $2$, $3$
• $4$, $1$, $3$, $2$
• $4$, $3$, $1$, $2$
• $4$, $3$, $2$, $1$

bt.in

8
1 2 1 3 1 2 1 3

bt.out

1728

Răspunsul corect dacă ar exista un delimitator este $6912$.

bt.in

4
1 2 3 4

bt.out

24

Deoarece orice element din vector este distinct, acestea pot fi scoase în orice ordine. Răspunsul pentru celălalt caz este tot $4! = 24$.

bt.in

6
1 2 3 1 3 2

bt.out

96

Răspunsul corect dacă ar exista un delimitator este $312$.

bt.in

1
1

bt.out

1

Avem un singur element în vector, deci există o singură cale de a-l scoate. Răspunsul pentru celălalt caz este tot $1$.