Problem Description

There are $2N$ cells arranged in a row, and a string $S$ of length $2N$ is given that represents the color of each cell.

The color of the $i$-th cell from the left is black if the $i$-th character of $S$ is B, and white if it is W.

You will perform exactly $N$ operations where you select two different cells, and invert the colors of these cells and all cells in between. Inverting the color of a cell means changing it from black to white or from white to black.

However, you cannot select the same cell more than once throughout the operations. This means each cell will be selected exactly once.

Find the number of ways to make all cells white after $N$ operations, modulo $10^9+7$.

Two methods are considered different if there exists an $i$ ($1 \leq i \leq N$) such that the pair of cells selected in the $i$-th operation in the first method is different from the pair selected in the $i$-th operation in the second method.

Input Format

The input is given from the standard input in the following format:

$ N $ $ S $

Output Format

Output the number of ways to make all cells white after $N$ operations, modulo $10^9+7$. If no such method exists, output $0$ instead.

Sample Input and Output

Sample Input #1

2
BWWB

Sample Output #1

4

Sample Input #2

4
BWBBWWWB

Sample Output #2

288

Sample Input #3

5
WWWWWWWWWW

Sample Output #3

0

Notes/Hints

Constraints

• $1 \leq N \leq 10^5$
• $ |S| = 2N $
• Each character of $S$ is either B or W.

Sample Explanation 1

There are $4$ ways to make all cells white:
- In the first operation, select cells $1$ and $3$, and in the second operation, select cells $2$ and $4$.
- In the first operation, select cells $2$ and $4$, and in the second operation, select cells $1$ and $3$.
- In the first operation, select cells $1$ and $4$, and in the second operation, select cells $2$ and $3$.
- In the first operation, select cells $2$ and $3$, and in the second operation, select cells $1$ and $4$.

见题面 Input 部分

见题面 Output 部分