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



Sample input:
2
BWWB


Sample output:
4

Submission status: Accepted

Solution code:
from itertools import groupby
import heapq

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

fact=[i for i in range(2*N+1)]
fact[0]=1
for i in range(1,2*N+1):
    fact[i]*=fact[i-1]
    fact[i]%=mod

inverse=[pow(fact[i],mod-2,mod) for i in range(2*N+1)]

data=["" for i in range(2*N)]
for i in range(2*N):
    if S[i]=="B" and i%2==1:
        data[i]="L"
    elif S[i]=="B" and i%2==0:
        data[i]="R"
    elif S[i]=="W" and i%2==1:
        data[i]="R"
    elif S[i]=="W" and i%2==0:
        data[i]="L"


if data[0]=="L" or data[-1]=="R":
    print(0)
    exit()



ans=fact[N]
data=groupby(data)
que=[]
heapq.heapify(que)
i=0
for key,group in data:
    g=len(list(group))
    heapq.heappush(que,(i,g))
    i+=1

rest=0
while que:
    i,R=heapq.heappop(que)
    j,L=heapq.heappop(que)
    if L>R+rest:
        print(0)
        break
    else:
        ans*=fact[R+rest]*inverse[R+rest-L]
        ans%=mod
        rest=R+rest-L
else:
    if rest==0:
        print(ans)
    else:
        print(0)

Submission status: Accepted

Solution code:


def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N=I()*2
    S=input()
    
    #括弧のように，各位置ごとに始まりか終わりかを規定
    #とじカッコの位置で，カッコを開いた数だけ通り数がある．
    
    st=list(range(N))
    for i in range(N):
        if S[i]=="B":
            c=0
        else:
            c=1
        st[i]=(st[i]+c)%2

    ans=1
    cnt=0#開き-閉じる
    
    for i in range(N):
        if st[i]==0:
            cnt+=1
        else:
            if cnt<0:
                ans=0
            ans=(ans*cnt)%mod
            cnt-=1
            
    #前半いらないが一応
    if st[-1]==0 or st[0]==1 or cnt!=0:
        ans=0
    for i in range(1,N//2+1):
        ans=(ans*i)%mod
    print(ans)
    
    
main()

Submission status: Accepted

Solution code:
N = int(input())
S = input()
MOD = 10**9 + 7

base = 1
unsettled = 0
remaining = 2 * N
for i, s in enumerate(S):
  if s == 'W':
    if unsettled % 2: # 奇数
      unsettled += 1
    else: # 偶数
      base = (base * unsettled) % MOD
      unsettled -= 1
  else: # s == 'B'
    if unsettled % 2: # 奇数
      base = (base * unsettled) % MOD
      unsettled -= 1
    else:
      unsettled += 1
  if unsettled < 0:
    print(0)
    quit()
  remaining -= 1
  if unsettled == remaining:
    break

for s in S[i+1:]:
  if s == 'W':
    if unsettled % 2: # 奇数
      print(0)
      quit()
    else: # 偶数
      base = (base * unsettled) % MOD
      unsettled -= 1
  else: # s == 'B'
    if unsettled % 2: # 奇数
      base = (base * unsettled) % MOD
      unsettled -= 1
    else: # 偶数
      print(0)
      quit()

def factorial(n, mod=10**9+7):
    a = 1
    for i in range(1,n+1):
        a = a * i % mod
    return a

print(base * factorial(N) % MOD)

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

MOD = 10 ** 9 + 7

def cmb(n, k):
    if k < 0 or k > n: return 0 
    return fact[n] * fact_inv[k] % MOD * fact_inv[n-k] % MOD

def cumprod(arr, MOD):
    L = len(arr); Lsq = int(L**.5+1)
    arr = np.resize(arr, Lsq**2).reshape(Lsq, Lsq)
    for n in range(1, Lsq):
        arr[:, n] *= arr[:, n-1]; arr[:, n] %= MOD
    for n in range(1, Lsq):
        arr[n] *= arr[n-1, -1]; arr[n] %= MOD
    return arr.ravel()[:L]

def make_fact(U, MOD):
    x = np.arange(U, dtype=np.int64); x[0] = 1
    fact = cumprod(x, MOD)
    x = np.arange(U, 0, -1, dtype=np.int64); x[0] = pow(int(fact[-1]), MOD-2, MOD)
    fact_inv = cumprod(x, MOD)[::-1]
    return fact, fact_inv

U = 10 ** 6  # 階乗テーブルの上限
fact, fact_inv = make_fact(U, MOD)

# 最終形が白一色、逆再生、leftとrightで別に考える
N = ir()
S = sr()
cur = 'W'  # 左端に白があるとする
left = 0
right = 0
dic = {'W': 'B', 'B': 'W'}
answer = fact[N]
X = []
for s in S:
    if s == cur:
        right += 1
        cur = dic[s]
    else:
        left += 1
        remain = N - right
        X.append(remain)
        cur = s
    if right > left:
        print(0); exit()

if right != left:
    print(0); exit()

for i, x in enumerate(X[::-1]):
    answer *= (x - i)
    answer %= MOD

print(answer % MOD)
# 07

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Jun 15 22:01:38 2019

@author: aozora
"""
N,S = open(0).read().split()
N = int(N)
T = []
MOD = 10**9+7
for i,c in enumerate(S):
  if i%2==0:
    if c=='B':
      T.append('W')
    else:
      T.append('B')
  else:
    T.append(c)

pre = 0
ans = 1
for c in T:
  if c=='B':
    ans *= pre
    ans %= MOD
    pre -= 1
    flag = False
  else:
    pre += 1
if T.count('B')!=T.count('W'):
  ans = 0
coef = 1
for i in range(1,N+1):
  coef *= i
  coef %= MOD
print(ans*coef%MOD)

Submission status: Accepted

Solution code:
import sys
mod=10**9+7
n=int(input())
s=input()

count=0
ans=1
for i in range(2*n):
    if s[i]=="B": p=1
    else: p=0
    if (count+p)%2==0:
        ans=ans*count%mod
        count-=1
    else: count+=1
    if count<0: print(0);sys.exit()
if count!=0: print(0);sys.exit()
for i in range(1,n+1):
    ans=ans*i%mod
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
mod = 10**9+7
mod2 = 998244353
rng = 100100
fctr = [1]
finv = [1]
for i in range(1,rng):
  fctr.append(fctr[-1]*i%mod)
for i in range(1,rng):
  finv.append(pow(fctr[i],mod-2,mod))
def cmb(n,k):
  if n<0 or k<0:
    return 0
  else:
    return fctr[n]*finv[n-k]*finv[k]%mod
n = int(input())
s = input()
a = [0]*(2*n)
a[0] = 1
for i in range(1,2*n):
  if s[i-1] == s[i]:
    a[i] = a[i-1]
  else:
    if i == 1:
      a[i] = a[i-1]+1
    else:
      if a[i-1] != a[i-2]:
        a[i] = 2*a[i-1]-a[i-2]
      if (i+a[i-1])%2 == 0:
        a[i] = a[i-1]+1
      else:
        a[i] = a[i-1]-1
if a[-1] != 1 or a.count(0) >= 1 or s[0] != "B" or s[-1] != "B":
  print(0)
  exit()
c = Counter(a)
ans = 1
for i,x in c.items():
  ans = (ans*pow(i,x//2,mod))%mod
ans = ans*fctr[n]%mod
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
S=input()
MOD=10**9+7

p = [0 if c=='W' else 1 for c in S]
c = [p[i] ^ (0 if i&1 else 1) for i in range(len(p))]

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

ans = 1
l = 0
for r in c:
    if r:
        if l < 1:
            print(0)
            exit()
        ans = ans * l % MOD
        l -= 1
    else: l += 1

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

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class Mod:
    def __init__(self, m):
        self.m = m

    def add(self, a, b):
        return (a + b) % self.m

    def sub(self, a, b):
        return (a - b) % self.m

    def mul(self, a, b):
        return ((a % self.m) * (b % self.m)) % self.m

    def div(self, a, b):
        return self.mul(a, pow(b, self.m-2, self.m))

    def pow(self, a, b):
        return pow(a, b, self.m)

@mt
def slv(N, S):
    if S[0] != 'B' or S[-1] != 'B':
        return 0

    LR = [''] * N * 2
    l = 0
    ans = 1
    M = Mod(10**9+7)
    for i in range(2*N):
        if S[i] == 'B':
            if l % 2 == 0:
                LR[i] = 'L'
                l += 1
            else:
                LR[i] = 'R'
                ans = M.mul(ans, l)
                l -= 1

        else:
            if l % 2 == 0:
                LR[i] = 'R'
                ans = M.mul(ans, l)
                l -= 1
            else:
                LR[i] = 'L'
                l += 1

    C = Counter(LR)
    if C['L'] != C['R']:
        return 0

    for i in range(1, N+1):
        ans = ans = M.mul(ans, i)


    return ans


def main():
    N = read_int()
    S = read_str()
    print(slv(N, S))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
S = list(input())

for i in range(2*N):
    if (2*N-i)%2==1:
        S[i] = 'B' if S[i]=='W' else 'W'
        
if S.count('B')!=N:
    print(0)
    exit()

ans = 1
MOD = 10**9+7
B = 0

for Si in S:
    if Si=='B':
        B += 1
    else:
        ans *= B
        ans %= MOD
        B -= 1

fact = [1]

for i in range(1, N+1):
    fact.append(fact[-1]*i%MOD)

ans *= fact[N]
ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations,groupby
import sys
import bisect
import string
import math
import time
import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)]
        rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
#sys.setrecursionlimit(10**5)
input=lambda: sys.stdin.readline().rstrip()

def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

show_flg=False
show_flg=True

ans=1

n=I()
s=input()
l,r=0,0

for i in range(n*2):
    t=1 if s[i]=='B' else 0
    if (l-r+t)%2==1:
        l+=1
    else:
        ans*=(l-r)
        ans%=mo
        r+=1
    if i>=n:
        ans*=i-n+1
        ans%=mo
if r-l!=0:
    print(0)
else:
    print(ans)

Submission status: Accepted

Solution code:
import sys
N=int(input())
S=list(input())
mod=10**9+7
data=[0]*2*N
if S[0]=="W":
    print(0)
    sys.exit()
data[0]=-1
for i in range(1,2*N):
    if S[i]==S[i-1]:
        data[i]=-data[i-1]
    else:
        data[i]=data[i-1]
if data[-1]==-1:
    print(0)
    sys.exit()
lst=[0]*2*N
lst[-1]=data[-1]
for i in range(2*N-2,-1,-1):
    lst[i]=lst[i+1]+data[i]
ans=1
for i in range(2*N-1,-1,-1):
    if data[i]==-1:
        ans=ans*(lst[i]+1)%mod
count=0
for i in range(2*N):
    if data[i]==1:
        count+=1
if count!=N:
    print(0)
    sys.exit()
for i in range(1,N+1):
    ans=ans*i%mod
print(ans)

Submission status: Accepted

Solution code:
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    # divisors.sort()
    return divisors
def examA():
    M, D = LI()
    c = D//10
    ans = 0
    for i in range(2,M+1):
        d = make_divisors(i)
#        print(d)
        for j in range(len(d)//2):
            cur0 = d[j*2+1]; cur10 = d[j*2]
            if cur10==1:
                continue
            if cur0<=9:
                if cur10<c:
                    ans +=1
#                    print(cur10,cur0)
                elif cur10==c and cur0+cur10*10<=D:
                    ans +=1
#                    print(cur10,cur0)
        for j in range(len(d) // 2):
            cur0 = d[j * 2];cur10 = d[j * 2+1]
            if cur0 == 1:
                continue
            if cur10 <= 9:
                if cur10 < c:
                    ans += 1
                elif cur10 == c and cur0 + cur10 * 10 <= D:
                    ans += 1
        if len(d)%2==1:
            cur0 = d[-1]; cur10 = d[-1]
            if cur10==1:
                continue
            if cur0<=9:
                if cur10<c:
                    ans +=1
#                    print(cur10,cur0)
                elif cur10==c and cur0+cur10*10<=D:
                    ans +=1
#                    print(cur10,cur0)
    print(ans)
    return

class Bit():
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
        return
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
        return
def examB():
    N, K = LI()
    A = LI()
    bit = Bit(max(A))
    cur = 0
    for i, a in enumerate(A):
        bit.add(a, 1)
        cur += i + 1 - bit.sum(a)
    As = 0
    A.sort()
    now = 0
    for i in range(1,N):
        if A[i]!=A[i-1]:
            now = i
        As += now
#    print(cur,As)
    ans = (As*(K**2) - (As-2*cur)*K)//2
    ans %=mod
    print(ans)
    return

def examC():
    N = I()
    S = SI()
    L = [0]; R= []
    flagL = True
    for i in range(1,2*N):
        if S[i]==S[i-1]:
            if flagL:
                R.append(i)
                flagL = False
            else:
                L.append(i)
                flagL = True
        else:
            if flagL:
                L.append(i)
                flagL = True
            else:
                R.append(i)
                flagL = False
#    print(L); print(R)
    if len(L)!=N or S[0]=="W" or S[-1]=="W":
        print("0")
        return
    cur = 1
    sumR = [0]*(2*N)
    now = 0
    for k,i in enumerate(R):
        for j in range(now,i):
            sumR[j] = k
        now = i
#    print(sumR)
    for i in range(N-1,-1,-1):
        cur *=(N-sumR[L[i]]-(N-i-1))
#        print(cur,L[i])
        cur %=mod
#    print(cur)
    for i in range(N):
        cur *=(i+1)
        cur %=mod
    ans = cur
    print(ans)
    return

def examE():
    N, H, W = LI()
    d = defaultdict(list)
    HL = [[]for _ in range(H+1)]
    WL = [[]for _ in range(W+1)]
    for _ in range(N):
        r,c,a = LI()
        d[(r,c)].append(a)
        HL[r].append(-a)
        WL[c].append(-a)
    print(d)

    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,inf
mod = 10**9 + 7
inf = float('inf')

if __name__ == '__main__':
    examC()

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7

N = int(input())
S = input()

d = 0
ans = 1
for s in S:
    if (s == "B") ^ (d % 2 != 0):
        d += 1
    else:
        ans = (ans * d) % mod
        d -= 1

if d != 0:
    print(0)
    quit()

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

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
s=input()
m=10**9+7
l=1
for i in range(1,n+1):l=(l*i)%m
t=[0]*(2*n)
t[0]=1
for i in range(1,2*n):
    if s[i-1]==s[i]:
        t[i]=1-t[i-1]
    else:
        t[i]=t[i-1]
if t.count(1)==n and s[0]==s[-1]=="B":
    p=1
    c=0
    for i in t:
        c+=i
        if i==0:
            p=(p*c)%m
            c-=1
    print((p*l)%m)
else:
    print(0)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n=int(input())
    S=input()
    A=[((S[i]=='B') is (i&1==1))+0 for i in range(2*n)]

    # pair が偏る場合は不可能
    if(sum(A)!=n):
        print(0)
        return

    cnt=0
    ans=1
    for a in A:
        if(a==0):
            cnt+=1
        else:
            ans*=cnt
            ans%=MOD
            cnt-=1

    # factorial(n) を掛ける
    for i in range(1,n+1):
        ans*=i
        ans%=MOD
    print(ans)
resolve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()

class modfact(object):
    def __init__(self,n):
        fact=[1]*(n+1); invfact=[1]*(n+1)
        for i in range(1,n+1): fact[i]=i*fact[i-1]%MOD
        invfact[n]=pow(fact[n],MOD-2,MOD)
        for i in range(n-1,-1,-1): invfact[i]=invfact[i+1]*(i+1)%MOD
        self.__fact=fact; self.__invfact=invfact

    def inv(self,n):
        assert(n>0)
        return self.__fact[n-1]*self.__invfact[n]%MOD

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

    def invfact(self,n):
        return self.__invfact[n]

    def comb(self,n,k):
        if(k<0 or n<k): return 0
        return self.__fact[n]*self.__invfact[k]*self.__invfact[n-k]%MOD

    def perm(self,n,k):
        if(k<0 or n<k): return 0
        return self.__fact[n]*self.__invfact[n-k]%MOD

def resolve():
    n=int(input())
    mf=modfact(n)
    S=input()

    A=[None]*(2*n)
    for i,s in enumerate(S,1):
        A[i-1]=(s=='W')^(i&1)
    B=A[:]
    for i in range(2*n-1):
        B[i+1]+=B[i]

    # A が 0 であるものに対して、自分より左に何個 1 があるかを考える
    if(A[0]==0):
        print(0)
        return
    if(sum(A)!=n):
        print(0)
        return

    now=0
    ans=1
    for i in range(2*n):
        if(A[i]==0):
            ans*=B[i-1]-now
            ans%=MOD
            now+=1

    print(ans*mf.fact(n)%MOD)
resolve()

Submission status: Accepted

Solution code:
def main():
    mod=10**9+7
    n=int(input())
    a=input()+'z'
    if a[0]=='W':
        print(0)
        return 0
    x=[]
    cnt=1
    for i in range(2*n):
        if a[i]==a[i+1]:
            cnt+=1
        else:
            x.append(cnt)
            cnt=1
    lx=len(x)
    if lx==1:
        ans=1
        for i in range(2,n+1):
            ans=ans*i%mod
        print(ans)
        return 0
    if x[0]%2==0 or x[-1]%2==0:
        print(0)
        return 0
    y=[1]
    now=1
    cnt=1
    for i in range(lx-1):
        if x[i]%2!=0:
            cnt+=now
            y.append(cnt)
        else:
            now*=-1
            cnt+=now
            y.append(cnt)
    if y[-1]>1 or 0 in y:
        print(0)
        return 0
    z=[1]+[y[i+1]-y[i] for i in range(lx-1)]
    ans=1
    for i in range(lx):
        if x[i]%2==0:
            ans=ans*pow(y[i],x[i]//2,mod)%mod
        else:
            ans=ans*pow(y[i],(x[i]-1)//2+(z[i]==-1),mod)%mod
    for i in range(2,n+1):
        ans=ans*i%mod
    print(ans)
main()

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007





n = I()
s = S()

fac = [1] * (n + 1)
inv = [1] * (n + 1)
for j in range(1, n + 1):
    fac[j] = fac[j-1] * j % mod


ans = 1
l = 0
for i in s:
    if (i == 'B' and l % 2 == 0) or (i == 'W' and l % 2):
        l += 1
    else:
        if l == 0:
            print(0)
            exit()
        ans = ans * l % mod
        l -= 1


if l:
    print(0)
else:
    print(ans * fac[n] % mod)

Submission status: Accepted

Solution code:
def f_c():
    n = int(input())
    s = input()
    q = 10**9 + 7

    stack, c = 0,1
    for i in range(2*n):
        if i % 2 == 0:
            if s[i] == "B":
                stack += 1
            else:
                c *= stack
                stack -= 1
        else:
            if s[i] == "B":
                c *= stack
                stack -= 1
            else:
                stack += 1
        c %= q
    if c == 0 or stack != 0:
        print(0)
    else:
        for i in range(1,n+1):
            c *= i
            c %= q
        print(c)

if __name__ == "__main__":
    f_c()

Submission status: Accepted

Solution code:
N = int(input())
S = input()

mod = 10 ** 9 + 7

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

else :
    ret = 1
    l = 1
    pre = 0
    for i in range(1, 2 * N) :
        if S[i-1] == S[i] :
            if pre == 0 :
                ret *= l
                ret %= mod
                l -= 1
                pre ^= 1
            else :
                l += 1
                pre ^= 1
        else :
            if pre == 0 :
                l += 1
            else :
                ret *= l
                ret %= mod
                l -= 1
                
    if l != 0 :
        print(0)
    else :
        for i in range(1, N + 1) :
            ret *= i
            ret %= mod
            
        print(ret)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

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

R = [None]*(2*N)
odd = False
for i in range(2*N):
    if S[i] == 'W':
        if odd:
            R[i] = 1
            odd = False
        else:
            R[i] = 0
            odd = True
    else:
        if odd:
            R[i] = 0
            odd = False
        else:
            R[i] = 1
            odd = True
if sum(R) != N:
    print(0)
else:
    ans = 1
    mod = 10**9+7
    num_r = 0
    for i in range(2*N):
        if R[i]:
            num_r += 1
        else:
            ans = (ans*num_r)%mod
            num_r -= 1
    for n in range(1, N+1):
        ans = (ans*n)%mod
    print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
ModNum = 10**9+7

def main():
    N = int(input())
    S = input()

    direction = [0] * (2*N)

    line = 0
    for i in range(2*N):
        if S[i]=="B" and line%2==0:
            direction[i] = 1
            line += 1
        elif S[i]=="B" and line%2==1:
            direction[i] = -1
            line -= 1
        elif S[i]=="W" and line%2==0:
            direction[i] = -1
            line -= 1
            if line < 0:
                print(0)
                break
        elif S[i]=="W" and line%2==1:
            direction[i] = 1
            line += 1
    else:
        if line>0:
            print(0)
        else:
            ans = 1
            Sum = 0           
            for i in range(2*N):  
                if direction[i]==1:
                    Sum += 1
                else:
                    ans *= Sum
                    ans %= ModNum
                    Sum -= 1
            for i in range(1,N+1):
                ans *= i
                ans %= ModNum
            print(ans)




if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7

N = int(input())
s = raw_input()
ans, cnt, tmp = 1, 0, 0
for i in xrange(1, N*2+1):
    if (cnt & 1) ^ (s[i-1] == 'B'):
        cnt += 1
    else:
        ans = (ans * cnt) % mod
        cnt -= 1
        tmp += 1
for i in xrange(1, N+1):
    ans = ans * i % mod

print(ans if tmp == N else 0)

Submission status: Accepted

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

X = []
for i, s in enumerate(S):
    if i % 2 == 1:
        X.append(s)
    else:
        if s == 'W':
            X.append('B')
        else:
            X.append('W')


W_cnt = 0
ans = 1
for x in X:
    if x == 'W':
        W_cnt += 1
    else:
        ans *= W_cnt
        ans %= MOD
        W_cnt -= 1
else:
    if W_cnt:
        print(0)
    else:
        print(ans * factorial(N) % MOD)

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
from collections import *
from math import atan2, pi
from bisect import *
mod = 10**9+7

N = int(input())
S = [int(c == 'B') for c in input()]
if S[0] + S[-1] < 2:
    print(0)
    exit()
for i in range(N):
    S[2*i] ^= 1
if sum(S) != N:
    print(0)
    exit()
cnt, ans = 0, 1
for x in S:
    if x == 0:
        cnt += 1
    else:
        if cnt == 0:
            print(0)
            exit()
        ans = ans * cnt % mod
        cnt -= 1
for i in range(2, N+1):
    ans = ans * i % mod
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
S=input()
mod=10**9+7
d=[0 for i in range(2*N)]
#L=0
#R=1
for i in range(1,2*N):
    if S[i-1]==S[i]:
        d[i]=1-d[i-1]
    else:
        d[i]=d[i-1]
if sum(d)!=N or S[0]=="W" or S[-1]=="W":
    print(0)
    exit()
Li=0
Ri=0
ans=1
for i in range(2*N):
    if d[i]==1:
        ans*=Li-Ri
        ans%=mod
    if d[i]==0:
        Li+=1
    else:
        Ri+=1
for i in range(1,N+1):
    ans=ans*i
    ans%=mod
print(ans)

Submission status: Accepted

Solution code:
import sys
N = int(input())
S = list(input())
MOD = 10**9+7

if S[0] == 'B':
    Left = 1
    ans = 1
else:
    print(0)
    sys.exit()
    
flag = True
for i in range(1,2*N):
    if flag:
        if S[i-1] != S[i]:
            Left += 1
        else:
            flag = False
            ans *= Left
            ans %= MOD
            Left -= 1
    else:
        if S[i-1] != S[i]:
            ans *= Left
            ans %= MOD
            Left -= 1
        else:
            Left += 1
            flag = True
            
if Left != 0:
    print(0)
    sys.exit()
    
for i in range(1,N+1):
    ans *= i
    ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
S = list(input())
L = [1]
cumsumL = [1]
res = 1
rvisited = 0
mod = 10 ** 9 + 7
class Factorial:
  def __init__(self, n, mod):
    self.f=[1]
    for i in range(1, n + 1):
      self.f.append(self.f[-1] * i % mod)
    self.i=[pow(self.f[-1], mod - 2, mod)]
    for i in range(1, n + 1)[: : -1]:
      self.i.append(self.i[-1] * i % mod)
    self.i.reverse()
  def factorial(self, i):
    return self.f[i]
  def ifactorial(self, i):
    return self.i[i]
  def combi(self, n, k):
    return self.f[n] * self.i[n - k] % mod * self.i[k] % mod
f = Factorial(N, mod)
if S[0] == "W" or S[-1] == "W":
  print(0)
  exit(0)
for i in range(1, 2 * N):
  if S[i - 1] == S[i]:
    L.append((L[i - 1] + 1 )% 2)
  else:
    L.append(L[i - 1])
if sum(L) != N:
  print(0)
  exit(0)
for i in range(1, 2 * N):
  cumsumL.append(cumsumL[i - 1] + L[i])
for i in range(1, 2 * N):
  if L[i] == 0:
    res *= cumsumL[i] - rvisited % mod
    res %= mod
    rvisited += 1
print(f.factorial(N) * res % mod)

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7

n = int(input())
s = input()
t = [(ind % 2) ^ (ss == 'W') for ind, ss in enumerate(s)]
# print(t)

ans = 1
zeros = 0
for tt in t:
    if tt == 0:
        zeros += 1
    else:
        if zeros == 0:
            print(0)
            exit()
        ans = ans * zeros % mod
        zeros -= 1

if zeros > 0:
    print(0)
    exit()

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

print(ans)

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7

n = int(input())
s = input()
t = list(map(lambda x: 1 if x == 'B' else 0, s))
t = tuple((tt - df) % 2 for tt, df in zip(t, reversed(range(n * 2))))
# print(t)

ans = 1
zeros = 0
ones = 0
for tt in t:
    if tt == 0:
        zeros += 1
    else:
        if zeros == 0:
            print(0)
            exit()
        ans *= zeros
        ans %= mod
        zeros -= 1
        ones += 1

if zeros > 0:
    print(0)
    exit()

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

print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)


def fact(x):
    if x == 0:
        return 1
    else:
        return x * fact(x - 1) % mod


mod = 10 ** 9 + 7

n = int(input())
s = input()
t = list(map(lambda x: 1 if x == 'B' else 0, s))
t = tuple((tt - df) % 2 for tt, df in zip(t, reversed(range(n * 2))))
# print(t)

zeros = 0
ans = 1
ones = 0
for tt in t:
    if tt == 0:
        zeros += 1
    else:
        if zeros == 0:
            print(0)
            exit()
        ans *= zeros
        ans %= mod
        zeros -= 1
        ones += 1

if zeros > 0:
    ans = 0

ans *= fact(ones)
ans %= mod
print(ans)