/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
2N 個のマスが左右一列に並んでおり、各マスの色を表す長さ 2N の文字列 S が与えられます。
左から i 番目のマスの色は、S の i 文字目が B のとき黒色で、W のとき白色です。
あなたは異なる 2 マスを選んで、それらのマスおよびそれらの間にあるマスの色を反転する操作をちょうど N 回行います。 ここで、マスの色を反転するとは、そのマスの色が黒色なら白色に、白色なら黒色にすることです。
ただし、操作を通して同じマスを 2 回以上選ぶことはできません。 つまり、各マスがちょうど 1 回ずつ選ばれることになります。
N 回の操作終了後に全てのマスを白色にする方法が何通りあるかを 10^9+7 で割った余りを求めてください。
ここで、条件を満たす 2 つの方法が異なるとは、1 つ目の方法で i 番目に選んだ 2 つのマスの組と 2 つ目の方法で i 番目に選んだ 2 つのマスの組が異なるような i (1 \leq i \leq N) が存在することをいいます。
制約
- 1 \leq N \leq 10^5
- |S| = 2N
- S の各文字は
BまたはWである。
入力
入力は以下の形式で標準入力から与えられる。
N S
出力
N 回の操作終了後に全てのマスを白色にする方法の個数を 10^9+7 で割った余りを出力せよ。そのような方法が存在しない場合、代わりに 0 を出力せよ。
入力例 1
2 BWWB
出力例 1
4
全てのマスを白色にする方法は次の 4 通りあります。
- 最初の操作では 1, 3 番目のマスを選び、次の操作では 2, 4 番目のマスを選びます。
- 最初の操作では 2, 4 番目のマスを選び、次の操作では 1, 3 番目のマスを選びます。
- 最初の操作では 1, 4 番目のマスを選び、次の操作では 2, 3 番目のマスを選びます。
- 最初の操作では 2, 3 番目のマスを選び、次の操作では 1, 4 番目のマスを選びます。
入力例 2
4 BWBBWWWB
出力例 2
288
入力例 3
5 WWWWWWWWWW
出力例 3
0
Score : 500 points
Problem Statement
There are 2N squares arranged from left to right. You are given a string of length 2N representing the color of each of the squares.
The color of the i-th square from the left is black if the i-th character of S is B, and white if that character is W.
You will perform the following operation exactly N times: choose two distinct squares, then invert the colors of these squares and the squares between them. Here, to invert the color of a square is to make it white if it is black, and vice versa.
Throughout this process, you cannot choose the same square twice or more. That is, each square has to be chosen exactly once.
Find the number of ways to make all the squares white at the end of the process, modulo 10^9+7.
Two ways to make the squares white are considered different if and only if there exists i (1 \leq i \leq N) such that the pair of the squares chosen in the i-th operation is different.
Constraints
- 1 \leq N \leq 10^5
- |S| = 2N
- Each character of S is
BorW.
Input
Input is given from Standard Input in the following format:
N S
Output
Print the number of ways to make all the squares white at the end of the process, modulo 10^9+7. If there are no such ways, print 0.
Sample Input 1
2 BWWB
Sample Output 1
4
There are four ways to make all the squares white, as follows:
- Choose Squares 1, 3 in the first operation, and choose Squares 2, 4 in the second operation.
- Choose Squares 2, 4 in the first operation, and choose Squares 1, 3 in the second operation.
- Choose Squares 1, 4 in the first operation, and choose Squares 2, 3 in the second operation.
- Choose Squares 2, 3 in the first operation, and choose Squares 1, 4 in the second operation.
Sample Input 2
4 BWBBWWWB
Sample Output 2
288
Sample Input 3
5 WWWWWWWWWW
Sample Output 3
0