Fuzetea

Suntem la Craiova și $N$ olteni intră într-un bar unde specialitatea principală este Fuzetea. Barul, recent deschis, are un format aparte, cu locuri disponibile doar la masa din centru. Aceasta are formă circulară, iar în centrul său sunt toți barmanii și tot Fuzetea-ul. Știm sigur că în bar intră doar $N$ olteni pentru că în bar există doar $N$ locuri disponibile și niciun oltean nu va pleca până dimineață.

Ca în toate locurile din lumea asta, în Craiova sunt două tipuri de olteni, unii sunt introvertiți și alții extrovertiți. Astăzi fiind o zi frumoasă de mai la Craiova mulți oameni intră în bar și din păcate sau din fericire toți vin singuri. Atunci când un oltean intră într-un bar are anumite preferințe pentru locul unde se așează în funcție de felul său de a fi, astfel:

Un oltean introvertit vrea să-și petreacă seara singur și liniștit așa că își alege locul astfel:

• Prima dată se uită dacă există un loc unde nici în locul stânga nici în locul dreapta acestui loc nu s-a așezat nimeni. Dacă sunt mai multe astfel de locuri îl alege pe oricare.
• Dacă nu există niciun astfel de loc atunci se uită dacă există un loc care nu are un vecin ori în locul din stânga ori în locul din dreapta. Dacă există mai multe astfel de locuri îl alege pe oricare.
• Dacă există doar locuri libere cu ambele locuri vecine ocupate atunci alege oricare dintre aceste locuri.

Unui oltean extrovertit, deși a venit singur la bar, nu prea îi convine acest fapt și își dorește ca măcar să-și facă prieteni noi cu care să se distreze, astfel că el își alege locul astfel:

• Prima dată se uită dacă există un loc care are ambii vecini ocupați de alți oameni. Dacă există mai multe astfel de locuri îl alege pe oricare.
• Dacă nu există un astfel de loc cu ambii vecini ocupați, atunci el va căuta să se așeze pe un loc ce are totuși un vecin ocupat. Dacă există mai multe locuri de acest fel îl va alege pe oricare.
• Dacă barul este gol se așează oriunde și speră că o să se așeze alții lângă el mai târziu.

Cerință

Se dă $N$ și un șir cu $N$ caractere fără spații albe format din literele $e$ și $i$:

• dacă pe poziția $x$ se află litera $I$ înseamnă că al $x$-lea oltean sosit la bar este introvertit.
• dacă pe poziția $x$ se află litera $E$ înseamnă că al $x$-lea oltean sosit la bar este extrovertit.

Se cere să se calculeze în câte feluri se pot așeza în bar cei $N$ olteni dacă ei vin de fiecare dată în aceeași ordine.

Date de intrare

Pe prima linie a intrării se dă $N$ iar pe cea de-a doua linie se dă un șir continuu de $N$ caractere, fiecare caracter poate fi doar un $E$ sau $I$ cu semnificația din enunț.

Date de ieșire

Pe prima linie a ieșirii se cere să se afișeze un singur întreg reprezentând numărul de moduri în care se pot așeza oltenii la bar modulo $1 \ 000 \ 000 \ 007$. Două moduri de așezare se consideră distincte dacă există cel puțin un scaun pe care se așează persoane distincte în cele două moduri. În particular, configurațiile echivalente prin rotație a mesei se consideră distincte.

Restricții și precizări

• $1 \leq N \leq 250$.

Exemplul 1

stdin

4
EIEE

stdout

8

Explicație

Mai jos se poate vedea reprezentarea grafică a două moduri din opt de așezare a oltenilor în cadrul primului exemplu:

Exemplul 2

stdin

10
EIIEEEIIEE

stdout

47040

Exemplul 3

stdin

5
EEEEE

stdout

40

Exemplul 4

stdin

5
IIIII

stdout

40