Problem Description

There is a graph with $N$ nodes, numbered from $1$ to $N$. Each node is coloured either black or white. Additionally, it is known that node $1$ is black and node $2$ is white. For any $i$ and $j$ where $i \ne j$, there exists a directed edge from node $i$ to $j$ that is either red or blue. Its colour is determined using the following logic:

• If $i < j$ and the nodes have the same colour, then it is red.
• If $i < j$ and the nodes have different colours, then it is blue.
• If $i > j$ and the nodes have the same colour, then it is blue.
• If $i > j$ and the nodes have different colours, then it is red.

LoBren’s favourite colour is initially blue. He then takes a walk on the graph (note that walks allow for repeated vertices and edges). He uses the following rules when walking:

• If he is currently on node $1$, his favourite colour becomes blue.
• Otherwise, if he is currently on node $2$, his favourite colour becomes red.
• He then traverses an outgoing edge from his current node with the same colour as his favourite colour. It can be shown that such an edge must exist.
• Finally, he optionally repeats the process.

By writing down the nodes he visits, in order, he gets a list $l_1, l_2, \ldots, l_L$. Find the number of possible lists, mod $10^9 + 7$, that satisfy the following conditions:

• The list starts at node $1$ and ends at node $2$.
• For all $i$ where $3 \le i \le N$, node $i$ appears at most once in the list.
• For all $j$ where $3 \le j \le L$, we have $l_{j-2} \ne l_j$.

It is provable that the number of such lists is finite.

It may also be useful to note that “mod” corresponds to the % operator in most programming languages, indicating the remainder after division. For example, $5 \bmod 3 = 2$ and $17 \bmod 4 = 1$.

Input Format

The first line of input contains a single integer, $N$.

The next line contains a string of length $N$, consisting of the characters $\mathrm{B}$ and $\mathrm{W}$. If the $i$th character is $\mathrm{B}$, then node $i$ is black. Otherwise, it is white. It is guaranteed that node $1$ is black and node $2$ is white.

Output Format

On a single line, output the number of possible lists, modulo $10^9 + 7$.

4
BWWB

4

12
BWBWBBBWWBBW

3377552

Hint

Explanation of Output for Sample Input $1$

The graph looks like:

:::align{center} :::

The solid lines represent blue edges, while the dashed lines represent red edges. The possible paths are:

• $\color{blue}{1}\ \color{blue}{\to}\ \color{red}{\underline{2}}$
• $\color{blue}{1}\ \color{blue}{\to}\ \color{blue}{3}\ \color{blue}{\to}\ \color{red}{\underline{2}}$
• $\color{blue}{1}\ \color{blue}{\to}\ \color{blue}{3}\ \color{blue}{\to}\ \color{blue}{4}\ \color{blue}{\to}\ \color{red}{\underline{2}}$
• $\color{blue}{1}\ \color{blue}{\to}\ \color{red}{\underline{2}}\ \color{red}{\dashrightarrow}\ \color{red}{\underline{3}}\ \color{red}{\dashrightarrow}\ \color{blue}{1}\ \color{blue}{\to}\ \color{red}{\underline{2}}$

The favourite colour is red at the underlined nodes, and blue otherwise.

The following table shows how the $25$ available marks are distributed: