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: Time Limit Exceeded

Solution code:
from math import factorial

N = int(input())
S = input()
LR = [0]*(2*N)
LR[0] = 0
if S[0] == "W" or S[-1] == "W":
    print(0)
    exit()
for i in range(1, 2*N):
    if S[i-1] == S[i]:
        LR[i] = (LR[i-1] + 1) % 2
    else:
        LR[i] = LR[i-1]
if LR.count(0) != LR.count(1):
    print(0)
    exit()
L = 0
R = 0
count = 1
for w in LR:
    if w == 0:
        L += 1
    else:
        count *= L - R
        R += 1
print(count * factorial(N) % int(1e9+7))

Submission status: Time Limit Exceeded

Solution code:
if __name__ == '__main__':
    import sys
    input = sys.stdin.readline

    import math

    n = int(input())
    ss = input()
    count = 1

    num_linear = 1
    if ss[0] == 'W':
        print(0)
        exit()
    if ss[-1] == 'W':
        print(0)
        exit()
    for s in ss[1:-2]:
        if s == 'W':
            if num_linear % 2 == 0:
                count *= num_linear
                num_linear -= 1
            else:
                num_linear += 1
        else:
            if num_linear % 2 == 1:
                count *= num_linear
                num_linear -= 1
            else:
                num_linear += 1
    if num_linear != 1:
        print(0)
        exit()
    ans = math.factorial(n) % (10**9+7)

    ans *= count

    print(ans%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
from math import factorial

MOD = 10 ** 9 + 7

def mult(a, b):
  return ((a % MOD) * (b % MOD)) % MOD

def solve():
  N = int(input())
  S = input()
  if S[0] != 'B' or S[-1] != 'B': return 0

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

  if D.count('L') != D.count('R'): return 0

  C = 1
  c = 0
  for d in D:
    if d == 'L': c += 1
    else:
      C *= c
      c -= 1
      if c < 0: return 0

  return mult(factorial(N), C)

print(solve())

Submission status: Time Limit Exceeded

Solution code:
if __name__ == '__main__':
    import sys
    input = sys.stdin.readline

    n = int(input())
    ss = input()
    count = 1

    num_linear = 1
    if ss[0] == 'W':
        print(0)
        exit()
    if ss[-1] == 'W':
        print(0)
        exit()
    for s in ss[1:-2]:
        if s == 'W':
            if num_linear % 2 == 0:
                count *= num_linear
                num_linear -= 1
            else:
                num_linear += 1
        else:
            if num_linear % 2 == 1:
                count *= num_linear
                num_linear -= 1
            else:
                num_linear += 1
    if num_linear != 1:
        print(0)
        exit()
    ans = 1
    for i in range(1,n+1):
        ans *= i
        ans = ans % (10**9+7)
    ans *= count

    print(ans%(10**9+7))

Submission status: Time Limit Exceeded

Solution code:
import math
N = int(input())
S = input()
ans = 1
ans_base = 1
numofS = 0  # 線の左端になっている点をSとするとその数はちょうどNでないといけない
line = 0  # 左から順に線を引く。上に何本通っているかをあらわす
for i in range(2*N):
    if S[i] == "B":
        if line % 2 == 0:
            numofS += 1
            line += 1
        else:
            ans_base *= line
            line -= 1
    else:
        if line % 2 == 0:
            ans_base *= line
            line -= 1
        else:
            line += 1
            numofS += 1

    if line < 0:
        ans = 0
if numofS != N:
    ans = 0
    # print(numofS)

if ans != 0:
    fact = math.factorial(N)
    ans = ans_base * fact
    ans %= 10**9+7
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
 
N = int(input())
S = input()
 
if S[0] == "W" or S[-1] == "W":
  print(0)
  exit()

counter = 0
output = math.factorial(N)
for i in range(2*N):
  k = 2 * N - i - 1
  if (S[k] == "W" and k % 2 == 1) or (S[k] =="B" and k % 2 == 0):
    output *= (i - 2 * counter)
    counter += 1
print(output % (10**9+7))

Submission status: Time Limit Exceeded

Solution code:
import math
 
N = int(input())
S = input()
 
if S[0] == "W" or S[-1] == "W":
  print(0)
  exit()

counter = 0
output = math.factorial(N)
outcounter = 0
for i in range(2*N):
  k = 2 * N - i - 1
  if S[k] == "W" and k % 2 == 1:
    output *= (i - 2 * counter)
    counter += 1
  elif S[k] == "B" and k % 2 == 0:
    output *= (i - 2 * counter)
    counter += 1
print(output % (10**9+7))

Submission status: Time Limit Exceeded

Solution code:
import math
 
N = int(input())
S = input()
 
if S[0] == "W" or S[-1] == "W":
  print(0)
  exit()

counter = 0
output = math.factorial(N)
outcounter = 0
for i in range(2*N):
  k = 2 * N - i - 1
  if S[k] == "W":
    if k % 2 == 0:
      outcounter += 1
    else:
      output *= (outcounter - counter)
      counter += 1
  else:
    if k % 2 == 1:
      outcounter += 1
    else:
      output *= (outcounter - counter)
      counter += 1
print(output % (10**9+7))

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop
from collections import deque,defaultdict,Counter
from itertools import permutations,groupby
import sys
import bisect
import string
alp=string.ascii_lowercase
sys.setrecursionlimit(10**6)
def SI():
    return input().split()
def MI():
    return map(int,input().split())
def I():
    return int(input())
def LI():
    return [int(i) for i in input().split()]
YN=['Yes','No']
mo=10**9+7
#mo=998244353
#input=sys.stdin.readline

n=I()
s=input()
ans=0
t=''
l,r=0,0
for i in range(n*2):
    if i==0:
        t+='L'
        l+=1
        continue
    if ((l-r)%2==1 and s[i]=='W') or ((l-r)%2==0 and s[i]=='B'):
        t+='L'
        l+=1
    else:
        t+='R'
        r+=1
if t.count('L')!=n:
    print(0)
    exit()
    
#print(s,t)
L,R=0,0
ans=1
for i in t:
    if i=='L':
        L+=1
    if i=='R':
        ans*=L-R
        ans%=mo
        R+=1
f=1
for i in range(2,n+1):
    f*=i
    f%=mo
print((ans*f)%mo)

Submission status: Time Limit Exceeded

Solution code:
import sys

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


def getN():
    return int(input())


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


import math
MOD = 10**9 + 7

def factorial(n):
    ans = 1
    for i in range(1, n+1):
        ans *= i

    return ans

n = getN()
s = input().strip()

ans = 1
cur = 0
open = 0
for c in s:
    # print(c, ans, open, cur)
    if c == "B":
        if open%2 == 0:
            open += 1
            cur = 1
        else:
            if open == 0:
                print(0)
                sys.exit()
            ans *= open
            ans %= MOD
            open -= 1
            cur = 0

    else:
        if open%2 == 1:
            open += 1
            cur = 0
        else:
            if open == 0:
                print(0)
                sys.exit()
            ans *= open
            ans %= MOD
            open -= 1
            cur = 0

if open != 0:
    print(0)
    sys.exit()
print((ans * factorial(n)) % MOD)

Submission status: Time Limit Exceeded

Solution code:
import math
n=int(input())
S=list(input())
x="B"
y=-1
L=[]
for i in S:
  if i==x:
    y*=-1
    L.append(y)
  else:
    x=i
    L.append(y)
ans=1
count=0
for i in range(2*n):
    if L[i]==-1:
      ans=ans*(i-count*2)
      count+=1
print(ans*math.factorial(n)%1000000007 if count==n else 0)

Submission status: Time Limit Exceeded

Solution code:
import math
n=int(input())
S=list(input())
x="B"
y=-1
L=[]
for i in S:
  if i==x:
    y*=-1
    L.append(y)
  else:
    x=i
    L.append(y)
ans=1
count=0
if L.count(1)!=n:
  ans=0
else:
  for i in range(2*n):
    if L[i]==-1:
      ans=ans*(i-count*2)
      count+=1
print(ans*math.factorial(n)%1000000007)

Submission status: Time Limit Exceeded

Solution code:


N = int(input())

S = input()

now = 0

ans = 1

for i in range(2*N):

    #print (S[i],ans,now)

    if i == 0 and S[i] == "W":
        ans = 0
        break

    if i == 0 and S[i] == "B":
        now += 1
        continue

    if S[i] == "W":

        if now % 2 != 0:

            now += 1

        else:

            ans *= now
            now -= 1

    if S[i] == "B":

        if now % 2 != 0:

            ans *= now

            now -= 1

        else:

            now += 1


    if now < 0:
        ans = 0
        break

    #print (S[i],ans,now)

if now != 0:
    ans = 0

fac = 1
for i in range(N):

    i += 1
    fac = (fac * i) % (10 ** 9 + 7)

print ((fac * ans) % (10 ** 9 + 7) )

Submission status: Time Limit Exceeded

Solution code:
import math


N = int(input())

S = input()

now = 0

ans = 1

for i in range(2*N):

    #print (S[i],ans,now)

    if i == 0 and S[i] == "W":
        ans = 0
        break

    if i == 0 and S[i] == "B":
        now += 1
        continue

    if S[i] == "W":

        if now % 2 != 0:

            now += 1

        else:

            ans *= now
            now -= 1

    if S[i] == "B":

        if now % 2 != 0:

            ans *= now

            now -= 1

        else:

            now += 1


    if now < 0:
        ans = 0
        break

    #print (S[i],ans,now)

if now != 0:
    ans = 0

print ((math.factorial(N) * ans) % (10 ** 9 + 7) )

Submission status: Accepted

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

n = int(input())
S = [s=="W" for s in input().rstrip()]
B = []
l, r = 0, 0
ans = 1
for i in range(n):
  ans *= i+1
  ans %= mod
for s in S:
  if (l+r+s)%2:
    if l == r or r == n:
      print(0)
      exit()
    ans *= (l-r)
    ans %= mod
    r += 1
  else:
    if l == n:
      print(0)
      exit()
    l += 1
print(ans)

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7

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

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

right = [True] * (2 * N)
for i in range(1, 2 * N):
    if S[i] == S[i - 1]:
        right[i] = (not right[i - 1])
    else:
        right[i] = right[i - 1]
    
if right.count(True) != N:
    print(0)
    exit()

ans = 1
for i in range(2, N+1):
    ans *= i
    ans %= MOD
current_lines = 0
for r in right:
    if r:
        current_lines += 1
    else:
        ans *= current_lines
        ans %= MOD
        current_lines -= 1

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
s=input()
s=[int(x=='B') for x in s]
mod=10**9+7
# sの要素をすべて0にする
d=[-1]*(2*n-1)
for i in range(2*n-1):
    if s[i]==s[i+1]:
        d[i]=1
    else:
        d[i]=0
op=[True]
# True:Left
for x in d:
    if x:
        op.append(not op[-1])
    else:
        op.append(op[-1])
if s[0]==0 or s[-1]==0 or op[-1] or sum(op)!=n:
    print(0)
    exit()
ans=1
lcnt=0
for i,x in enumerate(op):
    if x:
        lcnt+=1
    else:
        ans*=lcnt
        ans%=mod
        lcnt-=1
for i in range(1,n+1):
    ans*=i
    ans%=mod
print(ans)

Submission status: Accepted

Solution code:
#各マスがちょうど 1 回ずつ選ばれる
n=int(input())
s=input()
d=[False]
for i in range(1,n*2):
    d.append((s[i]==s[i-1])^d[-1])
from collections import Counter
cd =Counter(d)
if not cd[True] or cd[0]!=cd[1] or s[0]=="W":
    print(0)
    exit()
st=d.index(True)
l=st
ans=1;mod=10**9+7
for i in range(st,2*n):
    if d[i]:
        ans*=l
        l-=1
        ans%=mod
    else:
        l+=1
for i in range(1,n+1):
    ans*=i
    ans%=mod

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

ans = 1
p = 0
m = 0
for si in s:
    if((p-m)%2==0):
        if(si=='B'):
            p += 1
        else:
            ans *= (p-m)
            ans %= mod
            m += 1
    else:
        if(si=='W'):
            p += 1
        else:
            ans *= (p-m)
            ans %= mod
            m += 1

if(p!=m):
    ans = 0

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

print(ans)

Submission status: Accepted

Solution code:
MOD = 10**9 + 7
import sys
input = sys.stdin.readline
N = int(input())
S = input().strip()

LR = []
d = 0
for s in S:
    if s == 'B':
        if d % 2:
            LR.append('R')
            d -= 1
        else:
            LR.append('L')
            d += 1
    else:
        if d % 2:
            LR.append('L')
            d += 1
        else:
            LR.append('R')
            d -= 1
    if d < 0:
        print(0)
        exit()
if not d == 0:
    print(0)
    exit()

ans = 1
d = 0
for m in LR:
    if m == 'L':
        d += 1
    else:
        ans *= d
        ans %= MOD
        d -= 1

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

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:
    l = [None]*(2*N)
    l[0] = 0
    for i in range(1, 2*N):
        l[i] = (0 if l[i-1] else 1) if S[i]==S[i-1] else (1 if l[i-1] else 0)

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

    ans = 0
    if sum(l)==N:
        b = 0
        ans = facN
        for i in l[::-1]:
            if i:
                b += 1
            else:
                ans *= b
                ans %= MOD
                b -= 1
    print(ans)

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:
    l = [0]*(2*N)
    for i in range(1, 2*N):
        if S[i]==S[i-1]:
            l[i] = 0 if l[i-1] else 1
        else:
            l[i] = 1 if l[i-1] else 0
    pair = sum(l)

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

    ans = 0
    if pair==N:
        buf = 0
        ans = facN
        for i in l[::-1]:
            if i:
                buf += 1
            else:
                ans *= buf
                ans %= MOD
                buf -= 1
    print(ans)

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:
    l = [0]*(2*N)
    for i in range(1, 2*N):
        if S[i]==S[i-1]:
            l[i] = 1 if l[i-1]==0 else 0
        else:
            l[i] = 0 if l[i-1]==0 else 1
    pair = sum(l)

    fac = [None]*(N+1)
    fac[1] = 1
    for i in range(2, N+1):
        fac[i] = fac[i-1] * i
        fac[i] %= MOD

    ans = 0
    if pair==N:
        buf = 0
        ans = 1
        for i in l[::-1]:
            if i:
                buf += 1
            else:
                ans *= buf
                ans %= MOD
                buf -= 1
        
        ans *= fac[N]
        ans %= MOD
    print(ans)

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
s = input()
s = list(s)
l = []
M = 10**9+7
prv = "L"
l.append(prv)
if not (s[0]==s[-1]=="B"):
    ans = 0
else:
    for i in range(1,2*n-1):
        if s[i-1]==s[i]:
            l.append("R")
            s[i] = "W" if s[i]=="B" else "B"
        elif s[i-1]!=s[i]:
            l.append("L")
        else:
            ans = 0
            break
    else:
        l.append("R")
        if sum(item=="R" for item in l)!=n:
            ans = 0
        else:
            num = 0
            ans = 1
            for item in l[::-1]:
                if item=="R":
                    num += 1
                else:
                    ans *= num
                    ans %= M
                    num -= 1
            for i in range(1, n+1):
                ans *= i
                ans %= M
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
n*=2
A=list(input())
mod=10**9+7
if A[0]=="W" or A[-1]=="W": print(0);exit()

A=[i=="B" for i in A]
LR=[""]*n
LR[0]="L"
for i  in range(n-1):
    LR[i+1]=LR[i] if A[i]!=A[i+1] else ["L","R"][LR[i]=="L"]
from collections import Counter
#print(LR)
C=Counter(LR)
if C["L"]!=C["R"]:print(0);exit()
if LR[-1]=="L": print(0);exit()

r=0
ans=1
n//=2
for s in range(2*n-1,-1,-1):
    if LR[s]=="R":
        r+=1
    else:
        ans*=r
        ans%=mod
        r-=1
for i in range(1,n+1):
    ans*=i
    ans%=mod
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
s=input()
if s[0]=="W":
    exit(print(0))
t=[1]
for i in range(1,2*n):
    if s[i]==s[i-1]:
        t.append(-t[-1])
    else:
        t.append(t[-1])
now=1
for i in range(1,2*n):
    now+=t[i]
    if now<0:
        exit(print(0))
if now!=0:
    exit(print(0))
#左は確実に余ってるので右がきたら組み合わせる方向性で
ans=1
mod=10**9+7
ca=0
for i in range(2*n):
    if t[i]==1:
        ca+=1
    else:
        ans*=ca
        ans%=mod
        ca-=1
#この時点のansは組み合わせの数のみその順番を考慮していない
for i in range(1,n+1):
    ans*=i
    ans%=mod
print(ans)

Submission status: Accepted

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

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

answer=1
for i in range(2,N+1):
  answer*=i
  answer%=MOD
  
lrlist=["L"]
for i in range(1,2*N):
  if S[i]==S[i-1]:
    if lrlist[-1]=="L":
      lrlist.append("R")
    else:
      lrlist.append("L")
  else:
    lrlist.append(lrlist[-1])
#print(lrlist)

if lrlist.count("L")!=lrlist.count("R"):
  print(0)
  sys.exit(0)

num_L=num_R=0
for i in range(2*N):
  x=lrlist[i]
  if x=="R":
    #print(num_L,num_R,num_L-num_R)
    answer*=num_L-num_R
    answer%=MOD
    num_R+=1
  else:
    num_L+=1
    
print(answer)

Submission status: Accepted

Solution code:
import sys

mod = 10 ** 9 + 7

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

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

d = {'L':'R', 'R':'L'}

T = 'L'
for i in range(2 * N-1):
    if S[i] == S[i+1]:
        T += d[T[-1]]
    else:
        T += T[-1]

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

ans = 1
cnt = 0

for i in range(2 * N):
    if T[i] == 'L':
        cnt += 1
    else:
        ans *= cnt
        ans %= mod
        cnt -= 1

def factorial(n, mod):
    fact = 1
    for integer in range(1, n + 1):
        fact *= integer
        fact %= mod
    return fact

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

print(ans)

Submission status: Accepted

Solution code:
mod=10**9+7
n=int(input())
s=input()
if s[0]=='W' or s[-1]=='W':
  print(0)
  exit()
arr=['']*(2*n)
arr[0]='L'
arr[-1]='R'
cnt=1
for i in range(1,n):
  if (cnt==0 and s[i]=='B') or (cnt==1 and s[i]=='W'):
    arr[i]='L'
    cnt=(cnt+1)%2
  else:
    arr[i]='R'
    cnt=(cnt+1)%2
cnt=1
for i in range(2*n-2,n-1,-1):
  if (cnt==0 and s[i]=='B') or (cnt==1 and s[i]=='W'):
    arr[i]='R'
    cnt=(cnt+1)%2
  else:
    arr[i]='L'
    cnt=(cnt+1)%2
if arr.count('L')!=n:
  print(0)
else:
  ans=1
  cnt=0
  for char in arr[::-1]:
    if char=='R':
      cnt+=1
    else:
      ans*=cnt
      ans%=mod
      cnt-=1
  for i in range(1,n+1):
    ans*=i
    ans%=mod
  print(ans)

Submission status: Accepted

Solution code:
#from collections import deque,defaultdict
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7
#R = 998244353

def ddprint(x):
  if DBG:
    print(x)

n = inn()
s = ins()
cnt = 1
out = 0
for i in range(2*n):
    if s[i]=='B' and out%2==0 or s[i]=='W' and out%2==1:
        out += 1
    else:
        if out==0:
            print(0)
            exit()
        cnt = (cnt*out)%R
        out -= 1
    #ddprint(f"{i=} {cnt=} {out=}")
if out!=0:
    print(0)
    exit()
for i in range(2,n+1):
    cnt = (cnt*i)%R
print(cnt)

Submission status: Accepted

Solution code:
# problem 7
# cell inversion
N = int(input())
S = input()
if S[0]=="W":
    print(0)
    exit()
mod = 10**9 + 7
D = [-1]  # left -1 right 1
for i in range(2*N-1):
    if S[i] != S[i+1]:
        D.append(D[-1])
    else:
        D.append(D[-1]*(-1))
left = []
for i in range(2*N):
    if D[i] < 0:
        left.append(i)
sums = [0 for i in range(2*N)]
for i in range(2*N):
    if D[i] > 0:
        sums[i] += 1
for i in range(2*N-2, -1, -1):
    sums[i] += sums[i+1]
ans = 1
for i in range(2, N+1):
    ans *= i
    ans %= mod
if len(left)!=N:
    print(0)
    exit()
for i in range(N):
    ans *= sums[left[i]]-(N-1-i)
    ans %= mod
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict, deque, Counter
import math

# import copy
from bisect import bisect_left, bisect_right
import heapq

# sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline

getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = 10 ** 20
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)


def nck(n, k, kaijyo):
    return (npk(n, k, kaijyo) * divide(kaijyo[k])) % MOD


def npk(n, k, kaijyo):
    if k == 0 or k == n:
        return n % MOD
    return (kaijyo[n] * divide(kaijyo[n-k])) % MOD


def kaijyo(n):
    ret = [1]
    for i in range(1, n + 1):
        ret.append((ret[-1] * i)% MOD)
    return ret

def solve():
    n = getN()
    S = getS()
    rev = 0
    ans = 1
    for c in S:
        if c == "W":
            if rev == 0:
                print(0)
                return
            if rev % 2 == 0:
                ans *= rev
                ans %= MOD
                rev -= 1
            else:
                rev += 1
        else:
            if rev % 2 == 1:
                ans *= rev
                ans %= MOD
                rev -= 1
            else:
                rev += 1
    # print(ans)
    if rev == 0:
        print((ans * kaijyo(n)[-1]) % MOD)
    else:
        print(0)

def main():
    n = getN()
    for _ in range(n):
        solve()


if __name__ == "__main__":
    # main()
    solve()

Submission status: Accepted

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

crr = 0
lst= []
for i in range(2*n):
    if s[i] == 'B':
        if crr%2 == 1:
            lst.append(-1)
            crr -= 1
        else:
            lst.append(1)
            crr += 1
    else:
        if crr%2 == 1:
            lst.append(1)
            crr += 1
        else:
            lst.append(-1)
            crr -= 1

if crr!=0 or lst[0]!=1 or lst[-1]!=-1:
    print(0)
    exit()

plus = []
pcnt = 0
minus = []
mcnt = 0
where = []
for i in range(2*n):
    if lst[i] == 1:
        pcnt += 1
    else:
        mcnt += 1
        where.append(i)
    plus.append(pcnt)
    minus.append(mcnt)

ans = 1
for i in where:
    ans *= plus[i] - minus[i] + 1
    ans %= mod

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

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import *

N = int(input())
S = list(input()[:-1])

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

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

for i in range(2*N):
    if S[i]=='W':
        w += 1
    else:
        ans *= w
        w -= 1
        ans %= MOD

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

print(ans)

Submission status: Accepted

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

# 操作でLとなるべき石と、Rとなるべき石は確定できる
# 左端は必ずLかつB、右端は必ずRかつBである
# 隣り合う石が同じであれば、L->R,R->Lとなる
# 隣り合う石が異なれば、L->L,R->Rとなる

N = int(readline())
S = readline().rstrip()
DIV = 10 ** 9 + 7

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

D = [None] * (2 * N)

D[0] = "L"
for i in range(1,len(S)):
  if S[i] != S[i - 1]:
    D[i] = D[i - 1]
  else:
    if D[i - 1] == "R":
      D[i] = "L"
    else:
      D[i] = "R"

if D.count("L") != N:
  print(0)
  exit(0)

# 先頭から順にLの数をカウントする
# Rに遭遇したら、そこまでに遭遇したLの数を掛け合わせる
# ただし一回計算したら、選べるLの候補は1減る。
# 選べるLの候補が0になっていたらその時点で0である(掛け算で0になるので実質考慮不要)

L = 0
R = 0
ans = 1
for d in D:
  if d == "L":
    L += 1
    continue
  ans *= L
  ans %= DIV
  L -= 1

# 組み合わせに対して、操作の順番がN!通りある
for i in range(1, N + 1):
  ans *= i
  ans %= DIV
  
print(ans)

Submission status: Accepted

Solution code:
import sys
n=int(input())
s=input()
MOD=10**9+7
if s[0]=='W' or s[-1]=='W':
  print(0)
  sys.exit()
a=[-1]*(2*n)
current=1
for i in range(2*n-1):
  a[i]=current
  if s[i]==s[i+1]:
    current=1-current
if current==1:
  print(0)
  sys.exit()
a[2*n-1]=0
if sum(a)!=n:
  print(0)
  sys.exit()
ans=1
current=0
for i in range(2*n):
  if a[i]==1:
    current+=1
  else:
    current-=1
  if current<0:
    print(0)
    sys.exit()
current=0
for i in range(2*n):
  if a[2*n-1-i]==0:
    current+=1
  else:
    current-=1
  if current<0:
    print(0)
    sys.exit()
current=0
for i in range(2*n):
  if a[2*n-1-i]==0:
    current+=1
  else:
    ans=(ans*current)%MOD
    current-=1
for i in range(1,n+1):
  ans=(ans*i)%MOD
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
s=input()
cnt=0
r=[""]*(2*n)
d={"B":1,"W":0}
for i in range(2*n):
    if d[s[i]]^cnt%2:
        cnt+=1
        r[i]="L"
    else:
        cnt-=1
        r[i]="R"
    if cnt<=-1 or cnt>=n+1:print(0);exit()
if cnt!=0:print(0);exit()
ans=1
mod=10**9+7
for i in range(1,n+1):
    ans*=i
    ans%=mod
lcnt=0
for i in range(2*n):
    if r[i]=="L":
        lcnt+=1
    if r[i]=="R":
        ans*=lcnt
        ans%=mod
        lcnt-=1
print(ans)

Submission status: Accepted

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

if s[0] == "W":
    print(0)
    sys.exit()

sg = 1
ans = 1
now = 0
for i in range(1, n*2):
    if s[i] == s[i-1]:
        now = (now+1)%2
    if now == 0:
        sg += 1
    else:
        ans = (ans * sg) % mod
        sg -= 1
    if sg < 0 or sg > n:
        ans = 0
        break
    # print(i,sg)

if sg != 0:
    print(0)
    sys.exit()

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

Submission status: Accepted

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

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

d = {"B": "W", "W": "B"}


def flip(x):
    return d[x]


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

if sum(lr) != n:
    ans = 0

else:
    l_cnt = 0
    ans = 1
    for e in lr:
        if e:
            l_cnt += 1
        else:
            ans *= l_cnt
            ans %= mod
            l_cnt -= 1

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

print(ans)

Submission status: Accepted

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

N = int(input())
S = input().rstrip()
mod = 10**9 + 7
cnt = 0
ans = 1
for c in S:
    if (c == 'W') ^ (cnt % 2 == 1):
        ans = ans * cnt % mod
        cnt -= 1
    else:
        cnt += 1
if cnt > 0:
    ans = 0
for i in range(1, N+1):
    ans = ans * i % mod
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import *

N = int(input())
S = input()[:-1]

if S[0]=='W':
    print(0)
    exit()
    
l = [0]
ans = 1
MOD = 10**9+7

for i in range(1, 2*N):
    if S[i]==S[i-1]:
        l.append(1^l[-1])
    else:
        l.append(l[-1])

if l.count(0)!=N:
    print(0)
    exit()
    
zero = 0

for li in l:
    if li==0:
        zero += 1
    else:
        ans *= zero
        ans %= MOD
        zero -= 1
        
for i in range(1, N+1):
    ans *= i
    ans %= MOD

print(ans)

Submission status: Accepted

Solution code:
import sys
from math import factorial

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline
MOD = 10 ** 9 + 7


def solve():
    N = int(rl())
    S = rl().rstrip()
    
    if S[0] == 'W' or S[-1] == 'W':
        print(0)
        return
    
    flip = [0] * (2 * N)
    cntl, cntr = 1, 0
    ans = 1
    for i in range(1, 2 * N):
        if S[i] == S[i - 1]:
            flip[i] = flip[i - 1] ^ 1
        else:
            flip[i] = flip[i - 1]
        if flip[i] == 0:
            cntl += 1
        else:
            ans = ans * (cntl - cntr) % MOD
            cntr += 1
    
    if cntl != cntr:
        print(0)
    else:
        ans = ans * factorial(N) % MOD
        print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate
N = int(input())
S = input()
if S[0]=='W' or S[-1]=='W':
  print(0)
  sys.exit()
MOD = 10**9+7
p = 1
ls = [p]
for i in range(1,2*N):
  if S[i]==S[i-1]:
    p = (p+1)%2
    ls.append(p)
  else:
    ls.append(p)
if p!=0:
  print(0)
  sys.exit()
if ls.count(1)!=N:
  print(0)
  sys.exit()
A = list(accumulate(ls))
m = 0
ans = 1
for i in range(1,N+1):
  ans *= i
  ans %= MOD
for i in range(2*N):
  if ls[i]==0:
    ans *= A[i]-m
    ans %= MOD
    m += 1
print(ans)

Submission status: Accepted

Solution code:

from collections import defaultdict
con = 10 ** 9 + 7; INF = float("inf")

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

#処理内容
def main():
	N = int(input())
	S = input()
	LR = [None] * (2 * N)
	LR[0] = "L"
	for i in range(1, 2 * N):
		if S[i] == S[i - 1]:
			if LR[i - 1] == "L":
				LR[i] = "R"
			else:
				LR[i] = "L"
		else:
			if LR[i - 1] == "L":
				LR[i] = "L"
			else:
				LR[i] = "R"

	Lcnt = LR.count("L")
	Rcnt = LR.count("R")
	if Lcnt != Rcnt:
		print(0)
		return
	if S[0] == "W" or S[-1] == "W":
		print(0)
		return

	ans = 1; lcnt = 0; rcnt = 0
	for i in range(2 * N):
		if LR[i] == "L":
			lcnt += 1
		else:
			if lcnt - rcnt >= 1:
				ans *= lcnt - rcnt
				ans %= con
				rcnt += 1
			else:
				ans = 0

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

	print(ans)


if __name__ == '__main__':
	main()