Problem:
 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 B or W .         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

Solution (Python):



MOD = 1000000007


def solve():
  N = int(input())
  Sn = str(input())
  Slr = ["L" for _ in range(2*N)]

  for i in range(1,2*N):
    if Sn[i-1] == Sn[i]:
      Slr[i] = "LR".strip(Slr[i-1])
    else:
      Slr[i] = Slr[i-1]

  if Slr.count("L")!=Slr.count("R"):
    return 0
  if Sn[0]!="B" or Sn[-1]!="B":
    return 0

  ans,l,r = [1,1,0]
  for i in range(1,2*N):
    if Slr[i]=="L":
      l += 1
    else:
      ans = (ans*(l-r)) % MOD
      r += 1
  for i in range(1,N+1):
    ans = (ans*i)%MOD
  return ans


ans = solve()
print(ans)

Solution (Python):
n=int(input())
s=list(input())
m=2*n
mod=10**9+7

if s[0]=="W" or s[m-1]=="W":
    print(0)
    exit()

rl=["L"]
for i in range(1,m):
    if s[i-1]==s[i]:
        if rl[i-1]=="R":
            rl.append("L")
        else: 
            rl.append("R")
    else:
        if rl[i-1]=="L":
            rl.append("L")
        else: 
            rl.append("R")
if rl[m-1]=="L":
    print(0)
    exit()
nl=0
for i in range(m):
    if rl[i]=="L":
        nl+=1
if nl!=n:
    print(0)
    exit()
    
ans=1
li=0
ri=0
for i in range(m):
    if rl[i]=="L":
        li+=1
    else:
      if li-ri<0:
          ans=0
      ans*=li-ri
      ans=ans%mod
      ri+=1
    if i>=1 and i<=n:
        ans*=i
        ans=ans%mod
print(ans)

Solution (Python):
n = int(input())
s = input()
if s[0] == 'B':
  imos = [1]
else:
  imos = [0]
for i in range(1,2*n):
  if s[i] == s[i-1]:
    imos.append(0)
  else:
    imos.append(1)

ans = 1
mod = 10 ** 9 + 7
l = 0
att = 0
for i in range(2*n):
  if imos[i] ^ att == 1:
    l += 1
    att = 0
  else:
    ans *= l
    l -= 1
    att = 1
  ans %= mod
  
for i in range(1,n+1):
  ans *= i
  ans %= mod
if l == 0:
  print(ans)
else:
  print(0)

Solution (Python):
import math
mod=10**9+7
n=int(input())*2
S=list(input())

dp=[0]*(n)
dp[0]=1
if S[0]=='W' or S[-1]=='W':
	print(0)
	exit()
for i in range(1,n):
	
	if S[i]==S[i-1]:
		dp[i]=0 if dp[i-1] else 1
	else:
		dp[i]=1 if dp[i-1] else 0

count=1
counter=[0]*2
for i in range(n):
	if dp[i]==0:
		count*=counter[1]-counter[0]
		count%=mod
	counter[dp[i]]+=1
if counter[0]!=counter[1]:
	print(0)
	exit()

print((count*math.factorial(n//2))%mod)

Solution (Python):
n=int(input())
s=input()
st=''
mod=10**9+7
for i in range(2*n):
    if i%2==0:
        if s[i]=='B':
            st+='W'
        else:
            st+='B'
    else:
        st+=s[i]

cnt=0
ans=1
for i in range(2*n):
    if st[i]=='W':
        cnt+=1
    else:
        ans*=cnt
        ans%=mod
        cnt-=1
if cnt!=0:
    print(0)
    exit()
for i in range(1,n+1):
    ans*=i
    ans%=mod
print(ans)

Solution (Python):


import sys
from math import factorial

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
S = input()


if S[0] == 'W':
    print(0)
    exit()


remaining = 1
ans = 1
for i in range(1, N*2):
    
    
    if (S[i] == 'W') ^ (remaining%2 == 0):
        remaining += 1
        
        
        ans *= remaining
        ans %= MOD
    else:
        remaining -= 1
    
    if remaining < 0:
        print(0)
        exit()

if remaining != 0:
    print(0)
else:
    
    print(ans*factorial(N)%MOD)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

MOD = 10**9+7

N = int(input())
S = list(input().rstrip())

if S[0] == "W" or S[-1] == "W":
    print(0)
    sys.exit()

LR = [0 for i in range(2*N)]
count0 = 1
count0_raw = 1
ans = 1
for i in range(1, 2*N):
    if LR[i-1] == 0:
        if S[i] == S[i-1]:
            LR[i] = 1
        else:
            LR[i] = 0
    else:
        if S[i] == S[i-1]:
            LR[i] = 0
        else:
            LR[i] = 1

    if LR[i] == 0:
        count0 += 1
        count0_raw += 1
    else:
        ans *= count0
        ans %= MOD
        count0 -= 1

if count0_raw != N:
    print(0)
    sys.exit()

N_k = 1
for i in range(N):
    N_k *= i+1
    N_k %= MOD

print(ans*N_k%MOD)

Solution (Python):
n = int(input())
s = input()
count = 0
ans = 1 
for i, x in enumerate(s):
    if (i%2 == 0 and x == "B") or (i%2 == 1 and x == "W"): 
        count += 1
    else:
        ans *= count
        count -= 1
        ans %= (10**9+7)
if count != 0:
    print(0)
else:
    for i in range(1, n+1):
        ans *= i
        ans %= (10**9+7)
    print(ans)

Solution (Python):
n = int(input())
s = input()
MOD = 10 ** 9 + 7

ans = 1
for i in range(2, n + 1):
    ans = ans * i % MOD
pending = 0
for i, c in enumerate(s):
    if (i % 2 == 0 and c == 'B') or (i % 2 == 1 and c == 'W'):
        pending += 1
        continue
    ans = ans * pending % MOD
    pending -= 1
if pending != 0:
    ans = 0
print(ans)

Solution (Python):
mod = int(1e9+7)

n = int(input())
s = input()

a = [1 if s[i] == 'B' else 0 for i in range(len(s))]
ans = 1

if a[0] == 0:
    print(0)
    exit()

c = 1

for i in range(1,len(s)):
    if (a[i] + c) % 2 == 1:
        c += 1
    else:
        ans = (ans*c) % mod
        c -= 1

if c != 0:
    print(0)
    exit()

for i in range(n):
    ans = (ans*(i+1)) % mod

print(ans)

Solution (Python):
n=int(input())
s=input()
mod=10**9+7
op=1
ans=1
if s[0]=="W" or s[-1]=="W":
  print(0)
else:
  for i in range(1,2*n):
    if s[i]=="B":
      if op%2==0:
        op+=1
      else:
        ans*=op
        op-=1
    else:
      if op%2==1:
        op+=1
      else:
        ans=(ans*op)%mod
        op-=1
  if op!=0:
    ans=0
  for i in range(n):
    ans=(ans*(i+1))%mod
  print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)


n = int(input())
s = input().rstrip()
MOD = 10**9+7

cnt = 0
point = 1
for i, x in enumerate(s):
    if (x == 'B' and i % 2 == 0) or (x == 'W' and i % 2 != 0):
        cnt += 1
    else:
        point *= cnt
        cnt -= 1
        point %= MOD


if cnt != 0:
    print(0)
else:
    
    for x in range(1, n+1):
        point *= x
        point %= MOD

    print(point)

Solution (Python):

MOD = 10**9+7

n = int(input())
s = input()

if s[0]=="W" or s[-1]=="W":
    print(0)
    exit()

lr = ["L"]
for i in range(1,2*n):
    if s[i-1]==s[i]:
        if lr[i-1]=="L":
            lr.append("R")
        else:
            lr.append("L")
    else:
        lr.append(lr[i-1])

la = [0 for _ in range(2*n+1)]
ra = [0 for _ in range(2*n+1)]
for i in range(2*n):
    if lr[i]=="L":
        la[i+1] = la[i]+1
        ra[i+1] = ra[i]
    else:
        la[i+1] = la[i]
        ra[i+1] = ra[i]+1
if la[-1]!=ra[-1]:
    print(0)
    exit()

res = 1
for i in range(2*n):
    if lr[i]=="R":
        res *= la[i]-ra[i]
        res %= MOD

for i in range(2,n+1):
    res = (res*i)%MOD

print(res)

Solution (Python):
N=input()
S=raw_input()

L=[]

for i,x in enumerate(S):
		if x=="B": n=1
		elif x=="W": n=-1
		if i%2==1: n*=-1
		L.append(n)


mod=10**9+7

if sum(L)!=0:
	print 0
	quit()

ans=1
t=0
for x in L:
	if x==-1:
		ans*=t
		ans%=mod
	t+=x


for n in range(1,N+1):
	ans*=n
	ans%=mod

print ans

Solution (Python):


Q = 10**9+7
def main():
    N = int( input())
    S = input()
    left = 0
    ans = 1
    
    
    for s in S:
        if s == "B":
            if left%2 == 0:
                left += 1
            else:
                ans *= left
                left -= 1
        else:
            if left%2 == 1:
                left += 1
            else:
                ans *= left
                left -= 1
        ans %= Q
    if left > 0 or ans == 0:
        print(0)
        return
    for i in range(1,N+1):
        ans *= i
        ans %= Q
    print(ans)
if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline
Q = 10**9+7
def main():
    N = int( input())
    S = input()
    left = 0
    ans = 1
    for i in range(N*2):
        s = S[i]
        if s == "B":
            if left%2 == 0:
                left += 1
            else:
                ans *= left
                left -= 1
        else:
            if left%2 == 1:
                left += 1
            else:
                ans *= left
                left -= 1
        ans %= Q
    if left > 0 or ans == 0:
        print(0)
        return
    for i in range(1,N+1):
        ans *= i
        ans %= Q
    print(ans)
if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline
Q = 10**9+7
def main():
    N = int( input())
    S = input()
    left = 0
    ans = 1
    for i in range(N*2):
        s = S[i]
        if s == "B":
            if left%2 == 0:
                left += 1
            else:
                ans *= left
                left -= 1
        else:
            if left%2 == 1:
                left += 1
            else:
                ans *= left
                left -= 1
        ans %= Q
    if left > 0 or ans == 0:
        print(0)
        return
    for i in range(1,N+1):
        ans *= i
        ans %= Q
    print(ans)
if __name__ == '__main__':
    main()

Solution (Python):
"""
https://atcoder.jp/contests/jsc2019-qual/tasks/jsc2019_qual_c

B -> 1
W -> 0

BWWWWB
100001

反転操作を３つに分解
左端からl-1まで+1
左端からr-1まで+1
rに+1

こうしておくとつまり、右端として選ぶかどうかを決めるだけでよくなる

"""

from math import factorial

N = int(input())
d = {"W":0, "B":1}
ls = [d[s] for s in input()]
r_ls = reversed(ls)
xs = []
mod = 10**9 + 7

for i,r in enumerate(r_ls):
    xs.append(r + i)

LR = [x%2 for x in list(reversed(xs))]


cnt = 0 
num = 1 

for lr in LR:
    if lr == 0:
        cnt += 1
    else:
        num *= cnt
        cnt -= 1
        cnt = max(0,cnt)
        num %= mod

if cnt > 0:
    num = 0
ans = num * factorial(N)
print(ans%mod)

Solution (Python):
import sys
def main():
    n=int(input())
    s=input()
    MOD=10**9+7
    perm=1
    for i in range(1,n+1):
        perm=perm*i%MOD
    ans=1
    dp=[-1]*(2*n)

    dp[0]=1
    for i in range(1,2*n):
        if s[i]==s[i-1]:
            dp[i]=1-dp[i-1]
        else:
            dp[i]=dp[i-1]
    if s[0]=='W' or s[-1]=='W' or sum(dp)!=n:
        print(0)
        sys.exit()
    
    count=0
    for i in range(2*n):
        if dp[i]==1:
            count+=1
        else:
            ans*=count
            ans%=MOD
            count-=1
    print(ans*perm%MOD)

if __name__ == '__main__':
    main()

Solution (Python):
import sys
from sys import stdin

def main():
 
    n = int(stdin.readline().rstrip())
    s = stdin.readline().rstrip()
    MOD=10**9+7
    perm=1
    for i in range(1,n+1):
        perm=perm*i%MOD
    ans=1

    dp=1
    l=1
    r=0
    for i in range(1,2*n):
        if s[i]==s[i-1]:
            dp=1-dp
        if dp==1:
            l+=1
        else:
            r+=1
            ans*=l-r+1
            ans%=MOD
    if s[0]=='W' or s[-1]=='W' or l!=r:
        print(0)
        sys.exit()

    print(ans*perm%MOD)

if __name__ == '__main__':
    main()

Solution (Python):
import sys
from collections import Counter
from math import factorial

N = int(input())
S = input()
mod = 10**9+7

if S[0] == 'W' or S[-1] == 'W':
    print(0)
    sys.exit()

op = [0]*(2*N)
op[0] = False
ct_L = 1
ans = 1
for i in range(1, 2*N):
    if S[i] == S[i-1]:
        if op[i-1] is False:
            op[i] = True
            ans *= ct_L
            ct_L -= 1
        else:
            op[i] = False
            ct_L += 1
    else:
        if op[i-1] is False:
            op[i] = False
            ct_L += 1
        else:
            op[i] = True
            ans *= ct_L
            ct_L -= 1
    ans %= mod

ct_L, ct_R = Counter(op).values()
if ct_L != ct_R:
    print(0)
    sys.exit()


print(factorial(N) * ans % mod)

Solution (Python):
import sys


def factorial(N: int, mod: int) -> int:
    res = 1
    for i in range(1, N+1):
        res *= i
        res %= mod
    return res


N = int(input())
S = input()
mod = 10**9+7

if S[0] == 'W' or S[-1] == 'W':
    print(0)
    sys.exit()

op = [0]*(2*N)
op[0] = False
for i in range(1, 2*N):
    if S[i] == S[i-1]:
        op[i] = True if op[i-1] is False else False
    else:
        op[i] = True if op[i-1] is True else False

if op.count(True) != N:
    print(0)
    sys.exit()

ans = 1
L_ct = 0
R_ct = 0
for i in op:
    if i:
        ans *= L_ct
        L_ct -= 1
    else:
        L_ct += 1
    ans %= mod

print(factorial(N, mod) * ans % mod)

Solution (Python):
import sys
from math import factorial

N = int(input())
S = input()
mod = 10**9+7

if S[0] == 'W' or S[-1] == 'W':
    print(0)
    sys.exit()

op = "L"
for i in range(1, 2*N):
    if S[i] == S[i-1]:
        op += 'R' if op[i-1] == 'L' else 'L'
    else:
        op += 'R' if op[i-1] == 'R' else 'L'

if op.count('L') != N:
    print(0)
    sys.exit()

ct_L, ans = 0, 1

for i in op:
    if i == 'L':
        ct_L += 1
    else:
        ans *= ct_L
        ct_L -= 1
    ans %= mod


print(factorial(N) * ans % mod)

Solution (Python):
N = int(input())
S = input()
from math import factorial


cnt = 0

ans = 1
mod = 10 ** 9 + 7
for i in range(2 * N):
    s = S[i]
    if s == "W":
        if cnt == 0:
            print(0)
            exit()
        else:
            if cnt % 2 == 0:
                ans *= cnt
                ans %= mod
                cnt -= 1
            else:
                cnt += 1
    else:
        if cnt % 2 == 0:
            cnt += 1
        else:
            ans *= cnt
            ans %= mod
            cnt -= 1
if cnt != 0:
    print(0)
    exit()
ans *= factorial(N)
ans %= mod
print(ans)

Solution (Python):
from sys import stdin

N = int(stdin.readline().rstrip())
S = stdin.readline().rstrip()

ans = 1
inf = 10 ** 9 + 7
d = 'L'
l_count = 1
r_count = 0

if S[0] == 'W' or S[2 * N - 1] == 'W':
    print(0)
    exit()

for i in range(1, 2 * N):
    if S[i] != S[i - 1]:
        if d == 'R':
            ans *= l_count - r_count
            ans %= inf
            r_count += 1
        else:
            l_count += 1
    else:
        if d == 'R':
            d = 'L'
            l_count += 1
        else:
            ans *= l_count - r_count
            ans %= inf
            d = 'R'
            r_count += 1

if l_count != r_count:
    print(0)
    exit()

for j in range(1, N + 1):
    ans *= j
    ans %= inf

print(ans % inf)

Solution (Python):
from math import factorial
N = int(input())
S = input()
MOD = 10 ** 9 + 7

LR = [True]  
for i in range(N*2-1):
    LR += [LR[-1]] if S[i+1] != S[i] else [not LR[-1]]

valid = S[0] == S[-1] == 'B' and not LR[-1] and LR.count(True) == N

if valid:
    
    cmb = 1
    cr = 0
    for i in range(N*2-1, -1, -1):
        if not LR[i]:
            cr += 1
        else:
            cmb *= cr
            cmb %= MOD
            cr -= 1

    print((factorial(N) * cmb) % MOD)
else:
    print(0)

Solution (Python):
from collections import Counter

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


class FactMod():
    '''
    modの値が素数の時のfactと組み合わせを求める
    フェルマーの小定理を用いているため、modが素数以外の時は使えない
    '''

    def __init__(self, n, mod):
        '''
        コンストラクタ
        f:nまでの i!の値を　配列に入れる
        inv: (i!)^-1　の値を配列に入れる
        '''
        self.mod = mod
        self.f = [1]*(n+1)
        for i in range(1, n+1):
            self.f[i] = self.f[i-1]*i % mod

        self.inv = [pow(self.f[-1], mod-2, mod)]
        for i in range(1, n+1)[::-1]:
            self.inv.append(self.inv[-1]*i % mod)
        self.inv.reverse()

    def fact(self, n):
        '''
        n!の値を返す
        '''
        return self.f[n]

    def comb(self, n, r):
        '''
        nCrの値を返す
        '''
        ret = self.f[n] * self.inv[n-r]*self.inv[r]
        ret %= self.mod
        return ret

    def perm(self, n, r):
        """
        nPrの値を返す
        """
        ret = self.f[n] * self.inv[n-r]
        ret %= self.mod
        return ret

    def fact(self, n):
        return self.f[n]


MOD = 10**9+7
N = int(input())
S = input()[:-1]
F = FactMod(N+1, MOD)

cnt_W = 0
cnt = 0
ans = 1
for i, c in enumerate(S):
    if c == "B":
        tmp = 1
    else:
        tmp = 0
    if i % 2 == 0:
        tmp ^= 1

    if tmp == 0:
        cnt += 1
    else:
        ans *= cnt
        ans %= MOD
        cnt -= 1
        cnt_W += 1
if cnt_W != N:
    ans = 0
else:
    ans *= F.fact(N)
    ans %= MOD
print(ans)

Solution (Python):
MOD = 10**9 + 7
n = int(input())
s = input()

t = []
for i in range(2*n):
    if i % 2 == 0:
        t.append(0 if s[i] == 'B' else 1)
    else:
        t.append(0 if s[i] == 'W' else 1)


ans = 1
l = r = 0
for i in range(2*n):
    if t[i] == 1:
        ans *= max(l - r, 0)
        ans %= MOD

    if t[i] == 0:
        l += 1
    else:
        r += 1

if l == n:
    for i in range(1, n+1):
        ans *= i
        ans %= MOD
else:
    ans = 0

print(ans)

Solution (Python):
import numpy as np
MOD = 1000000007

def solve(S, N):
    a = [0] * (2 * N)
    if S[0] == 87:
        return 0
    a[0] = 1
    for i in range(1, 2 * N):
        
        if i & 1:
            if S[i] == 66:
                a[i] = a[i - 1]
                if 2 * a[i] < i + 1:
                    return 0
            else:
                a[i] = a[i - 1] + 1
        else:
            if S[i] == 87:
                a[i] = a[i - 1]
                if 2 * a[i] < i + 1:
                    return 0
            else:
                a[i] = a[i - 1] + 1
    if a[2 * N - 1] > N:
        return 0

    ans = 1
    for n in range(1, 2*N):
        if a[n] == a[n - 1]:
            ans = ans * (2 * a[n] - n) % MOD
    for n in range(2, N + 1):
        ans = ans * n % MOD
    return ans


stdin = open(0, 'rb')
N = int(stdin.readline())
S = np.frombuffer(stdin.readline(), dtype=np.int8)

print(solve(S.tolist(), N))

Solution (Python):
from math import factorial
n = int(input())
s = input()
mod = 10**9+7
t = ""
for i,c in enumerate(s):
	if i%2:
		t += "L" if c=="W" else "R"
	else:
		t += "R" if c=="W" else "L"
if t.count("L")!=t.count("R"):
	print(0)
else:
	ans = 1
	Lcnt = 0
	for i in t:
		if i=="L":
			Lcnt += 1
		else:
			ans *= Lcnt
			Lcnt -= 1
		ans %= mod
	print(ans*factorial(n)%mod)