Svet je konačno postao jedno mirno mesto, puno sreće i ljubavi. Kako bi uspela da se suprostave kragujevačkom fudbalskom gigantu, dva mala fudbalska kluba Partizan i Crvena zvezda su se ujedinili u jedan i postali Crno Bela Zvezda. Nakon ujedinjenja, Crno Bela Zvezda je dobila novi grb. Grb je u obliku crno belog zvezda grafa sa ~4~ čvora. Crno beli zvezda graf sa ~4~ čvora predstalja stablo čiji su svi čvorovi obojeni crnom ili belom bojom i čiji je koren obojen suprotnom bojom od listova (ako je koren obojen crnom bojom onda su listovi obojeni belom, dok ako je koren obojen belom bojom listovi su obojeni crnom).

Mladi Ćimi, vođa navijača Crno Bele Zvezde, dobio je crveni papir na kome su nacrtane crne i bele tačke. Nacrtano je tačno ~N~ tačaka numerisanih brojevima od ~1~ do ~N~. Boje tačaka su određene nizom ~A~, ako je ~i~-ta tačka bela onda je ~A_i = 0~, u suportnom ~A_i = 1~. Kada bi se tačke spojile redom ~1 -> 2 -> \dots -> N -> 1~, gradile bi pravilan ~N~-tougao. Ćimi je prosto opsednut grbom novog kluba i želi da ga nacrta tačno ~\frac{N}{4}~ puta na tom crvenom papiru. On želi da svaka tačka pripada tačno jednom grbu i da se grbovi međusobno ne presecaju, jer misli da bi tako urušio lepotu grbova.

Ćimi vas je zamolio da mu pomognete da izračuna broj načina da nacrta tačno ~\frac{N}{4}~ grbova. Dva načina se razlikuju ako postoji bar jedan grb koji je nacrtan na jednom crtežu i nije nacrtan na drugom. Kako broj načina može biti veliki, ispisati taj broj po modulu ~10^9 + 7~.

Opisi funkcija

Potrebno je da implementirate funkciju:

• ~Zvezda (~N~, A[\dots])~

~N~ je broj tačaka na papiru. ~A~ je niz dužine ~N~ koji predstavlja boje tačaka, ~i~-ta tačka je bela ako važi ~A_i = 0~, inače je tačka crna i ~A_i = 1~. Niz ~A~ je indeksiran od ~1~ .

Funkcija treba da vrati ceo broj ~X~ -- broj načina da Ćimi nacrta grbove po modulu ~10^9 + 7~.

Primer

Neka je ~N = 8~, ~A = [1, 1, 0, 1, 0, 1, 1, 1]~.

Postoji ~2~ načina da se nacrtaju zvezde:

• prva zvezda : ~[1, 2, 3, 4]~, druga zvezda ~[5, 6, 7, 8]~
• prva zvezda : ~[8, 1, 2, 3]~, druga zvezda ~[4, 5, 6, 7]~

Ograničenja

• ~1 \leq N \leq 500~ , ~N~ je deljivo sa ~4~
• ~0 \leq A_i \leq 1~

Podzadaci

Postoji ukupno ~14~ podzadataka, koji zadovoljavaju ograničenja napisana u tabeli:

Detalji implementacije

Potrebno je da pošaljete tačno jedan fajl zvezda.cpp, koji implementira pomenutu funkciju. Osim tražene funkcije, vaš fajl može sadržati i dodatne globalne promenljive, pomoćne funkcije i dodatne biblioteke.

Vaša funkcija mora biti sledećeg oblika:

int Zvezda(int N, int *A);

Vašim programima je dozvoljeno da menjaju sadržaj nizova/matrica, ali ne smeju da pristupaju van granica datih nizova.

Testiranje i eksperimentisanje

Uz zadatak, obezbeđen vam je "template" fajl code.cpp koji možete koristiti i menjati po potrebi. Takođe vam je obezbeđen program grader.cpp koji služi da lakše testirate kodove. Ovaj program učitava sa standardnog ulaza sledeće podatke:

• U prvom redu broj ~N~,
• U narednom redu ~N~ celih brojeva - ~A_i~.

Zatim ovaj program zove vašu funkciju i štampa vrednost koju je funkcija vratila. Kodove ovih programa možete menjati po potrebi.