Il existe un graphe avec $N$ sommets, numérotés de $1$ à $N$. Chaque sommet est coloré soit en noir, soit en blanc. De plus, on sait que le sommet $1$ est noir et le sommet $2$ est blanc. Pour tout $i$ et $j$ où $i \neq j$, il existe une arête dirigée du sommet $i$ vers $j$ qui est soit rouge, soit bleue. Sa couleur est déterminée selon la logique suivante :

• Si $i < j$ et que les sommets ont la même couleur, alors elle est rouge.
• Si $i < j$ et que les sommets ont des couleurs différentes, alors elle est bleue.
• Si $i > j$ et que les sommets ont la même couleur, alors elle est bleue.
• Si $i > j$ et que les sommets ont des couleurs différentes, alors elle est rouge.

La couleur préférée de LoBren est initialement bleue. Il effectue ensuite une marche sur le graphe (notez que les marches autorisent la répétition de sommets et d'arêtes). Il utilise les règles suivantes lors de sa marche :

• S'il est actuellement sur le sommet $1$, sa couleur préférée devient bleue.
• Sinon, s'il est actuellement sur le sommet $2$, sa couleur préférée devient rouge.
• Il traverse ensuite une arête sortante de son sommet actuel ayant la même couleur que sa couleur préférée. On peut montrer qu'une telle arête doit exister.
• Enfin, il répète éventuellement le processus.

En notant les sommets qu'il visite, dans l'ordre, il obtient une liste $l_1, l_2, \dots, l_L$. Trouvez le nombre de listes possibles, modulo $10^9 + 7$, qui satisfont les conditions suivantes :

• La liste commence au sommet $1$ et se termine au sommet $2$.
• Pour tout $i$ où $3 \leq i \leq N$, le sommet $i$ apparaît au plus une fois dans la liste.
• Pour tout $j$ où $3 \leq j \leq L$, nous avons $l_{j-2} \neq l_j$.

Il est prouvable que le nombre de telles listes est fini.

Il peut également être utile de noter que « mod » correspond à l'opérateur % dans la plupart des langages de programmation, indiquant le reste de la division. Par exemple, $5 \pmod 3 = 2$ et $17 \pmod 4 = 1$.

Entrée

La première ligne de l'entrée contient un entier unique, $N$.

La ligne suivante contient une chaîne de longueur $N$, composée des caractères B et W. Si le $i$-ième caractère est B, alors le sommet $i$ est noir. Sinon, il est blanc. Il est garanti que le sommet $1$ est noir et le sommet $2$ est blanc.

Sous-tâches

Le tableau suivant montre comment les 25 points disponibles sont répartis :

Sortie

Sur une seule ligne, affichez le nombre de listes possibles, modulo $10^9 + 7$.

Exemples

Entrée 1

4
BWWB

Sortie 1

4

Remarque

Le graphe ressemble à ceci :

Les lignes pleines représentent les arêtes bleues, tandis que les lignes en pointillés représentent les arêtes rouges. Les chemins possibles sont :

• $1 \to 2$
• $1 \to 3 \to 2$
• $1 \to 3 \to 4 \to 2$
• $1 \to 2 \to 3 \to 1 \to 2$

La couleur préférée est rouge aux sommets soulignés, et bleue sinon.

Entrée 2

12
BWBWBBBWWBBW

Sortie 2

3377552