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:
N = int(input())
S = input()
count = 0
ans = 1
m = 10**9 + 7
 
for i in range(N):
  if S[2*i] == "W":
    ans *= ((2*i) - (count*2))
    count += 1
  if S[2*i + 1] == "B":
    ans *= ((2*i + 1) - (count*2))
    count += 1

if count != N:
  print(0)
else:
  for o in range(1, N+1):
    ans *= o
    ans %= m
  print(ans % m)

Submission status: Time Limit Exceeded

Solution code:
M = 10**9+7
N = int(input())
S = list(input())
s = [0]*(2*N)

#0ならW、1ならB
for i in range(2*N):
    if S[i] == "B":
        s[i] = 1

#端が0なら0を返す
if s[0] == 0 or s[2*N-1] == 0:
    print(0)
    exit()

ans = 0
lis = [0]+[1]*(2*N-1) #0なら左、1なら右
#全て0にする

for j in range(1,2*N):
    if s[j-1] ^ s[j] == 1:
        lis[j] = lis[j-1]
    else:
        lis[j] = lis[j-1] ^ 1

#左と右の数が違ったら0を返す
if lis.count(0) != lis.count(1):
    print(0)
    exit()

#"右"が選べる"左"の選択肢を掛けていく
cnt = 1
ans = 1
for k in range(1,2*N):
    if lis[k] == 0:
        cnt += 1
    else:
        ans *= cnt
        cnt -= 1

#N!をかける
for l in range(1,N+1):
    ans *= l
    ans %= M
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,s=open(0)
n=int(n)
a=l=s[0]<'W'>s[-2]
r=f=0
for b,c in zip(s,s[1:-1]):f^=b==c;a*=(l-r)**f;r+=f;l+=f^1
while n:a=a*n%(10**9+7);n-=1
print(a*(l==r))

Submission status: Time Limit Exceeded

Solution code:
n,s=open(0)
n=int(n)
a=s[0]<'W'>s[-2]
while n:a*=n;n-=1
l=1
r=f=0
for b,c in zip(s,s[1:-1]):f^=b==c;a=a*(l-r)**f%(10**9+7);r+=f;l+=f^1
print(a*(l==r))

Submission status: Time Limit Exceeded

Solution code:

def main():
    import sys
    def input():
        return sys.stdin.readline()[:-1]

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

    if S[0]!='B' or S[-1]!='B':
        print(0)
        exit()

    mod = 10**9 + 7
    cnt = 1
    pre = 'B'
    d = 1 #1がleft
    ans = 1

    for i in range(1,N*2):
        if S[i-1]==S[i]:
            if d:
                d = 0
                ans *= cnt%mod
                cnt -= 1
            else:
                d = 1
                cnt += 1
        else:
            if d:
                cnt += 1
            else:
                ans *= cnt%mod
                cnt -= 1

    for i in range(1,N+1):
        ans *= i
        ans %= mod
    if cnt!=0:
        print(0)
        exit()

    print(ans)

if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input()
count = 0
ans = 1
m = 10**9 + 7
 
for i, s in enumerate(S):
  if ((s == "W") & (i%2 == 0)) or ((s == "B") & (i%2 == 1)):
    ans *= (i - (count*2))
    count += 1
if count != N:
  print(0)
else:
  for o in range(1, N+1):
    ans *= o
    ans %= m
  print(ans % m)

Submission status: Time Limit Exceeded

Solution code:

def main():
    import sys
    def input():
        return sys.stdin.readline()[:-1]

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

    if S[0]!='B' or S[-1]!='B':
        print(0)
        exit()

    mod = 10**9 + 7
    cnt = 1
    pre = 'B'
    d = 1 #1がleft
    ans = 1

    for i in range(1,N*2):
        if S[i-1]==S[i]:
            if d:
                d = 0
                ans *= cnt%mod
                cnt -= 1
            else:
                d = 1
                cnt += 1
        else:
            if d:
                cnt += 1
            else:
                ans *= cnt%mod
                cnt -= 1

    for i in range(1,N+1):
        ans *= i
        ans %= mod
    if cnt!=0:
        print(0)
        exit()

    print(ans)

if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit((10 ** 5) * 2)
 
def kai(a):
  if a == 1:
    return 1
  else:
    return a*kai(a-1)
  
N = int(input())
S = input()
count = 0
ans = 1
 
for i, s in enumerate(S):
  if ((s == "W") & (i%2 == 0)) or ((s == "B") & (i%2 == 1)):
    ans *= (i - (count*2))
    count += 1
if count != N:
  print(0)
else:
  print((ans*kai(N))%(10**9 + 7))

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    def input():
        return sys.stdin.readline()[:-1]

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

    if S[0]!='B' or S[-1]!='B':
        print(0)
        exit()

    mod = 10**9 + 7
    cnt_l = 1
    cnt = 1
    pre = 'B'
    d = 1 #1がleft
    ans = 1

    for i in range(1,N*2):
        if S[i-1]==S[i]:
            if d:
                d = 0
                ans *= cnt%mod
                cnt -= 1
            else:
                d = 1
                cnt_l += 1
                cnt += 1
        else:
            if d:
                cnt_l += 1
                cnt += 1
            else:
                ans *= cnt%mod
                cnt -= 1

    for i in range(1,N+1):
        ans *= i
        ans %= mod
    if cnt_l!=N:
        print(0)
        exit()

    print(ans)

if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
n=int(input())
s=list(input())
m=10**9+7
if s[0]=='W' or s[2*n-1]=='W':
  print(0)
  sys.exit()
side=[]
l=['L','R']
for i in range(2*n):
  if i==0:
    side.append('L')
  else:
    if s[i-1]==s[i]:
      side.append(l[(l.index(side[i-1])+1)%2])
    else:
      side.append(l[l.index(side[i-1])])
ctL=0;ctR=0;ans=1
for i in range(2*n):
  if side[i]=='L':
    ctL+=1
  else:
    ans=ans*(ctL-ctR)
    ctR+=1
if ctL!=ctR:
  print(0)
  sys.exit()
for i in range(1,n+1):
  ans*=i
  ans%=m
print(ans)

Submission status: Time Limit Exceeded

Solution code:
M = 10**9+7
N = int(input())
#S = list(input())
#s = [0]*(2*N)
s = list(map(int, input().replace("B","1").replace("W","0")))

#0ならW、1ならB
""" for i in range(2*N):
    if S[i] == "B":
        s[i] = 1 """

#端が0なら0を返す
if s[0] == 0 or s[2*N-1] == 0:
    print(0)
    exit()


lis = [0]+[1]*(2*N-1) #0なら左、1なら右
#全て0にする

cnt_0 = 1
cnt_1 = 0
ans = 1

#"右"が選べる"左"の選択肢を掛けていく
for j in range(1,2*N):
    if s[j-1] ^ s[j] == 1:
        lis[j] = lis[j-1]
    else:
        lis[j] = lis[j-1] ^ 1

    if lis[j] == 0:
        cnt_0 += 1
    else:
        ans *= cnt_0 - cnt_1
        cnt_1 += 1

#左と右の数が違ったら0を返す
if lis.count(0) != N:
    print(0)
    exit()

#N!をかける
for l in range(1,N+1):
    ans = ans*l %M

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    def input():
        return sys.stdin.readline()[:-1]

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

    if S[0]!='B' or S[-1]!='B':
        print(0)
        exit()

    mod = 10**9 + 7
    cnt_l = 1
    cnt_r = 0
    pre = 'B'
    pre_d = 1 #1がleft
    ans = 1

    for i in range(1,N*2):
        if S[i-1]==S[i]:
            if pre_d:
                pre_d = 0
                ans *= (cnt_l - cnt_r)%mod
                cnt_r += 1
            else:
                pre_d = 1
                cnt_l += 1
        else:
            if pre_d:
                cnt_l += 1
            else:
                ans *= (cnt_l - cnt_r)%mod
                cnt_r += 1

    for i in range(1,N+1):
        ans *= i
        ans %= mod
    if cnt_l!=N:
        print(0)
        exit()

    print(ans)

if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():

    M = 10**9+7
    N = int(input())
    #S = list(input())
    #s = [0]*(2*N)
    s = list(map(int, input().replace("B","1").replace("W","0")))

    #0ならW、1ならB
    """ for i in range(2*N):
        if S[i] == "B":
            s[i] = 1 """

    #端が0なら0を返す
    if s[0] == 0 or s[2*N-1] == 0:
        print(0)
        exit()

    ans = 0
    lis = [0]+[1]*(2*N-1) #0なら左、1なら右
    #全て0にする

    for j in range(1,2*N):
        if s[j-1] ^ s[j] == 1:
            lis[j] = lis[j-1]
            continue
        else:
            lis[j] = lis[j-1] ^ 1

    #左と右の数が違ったら0を返す
    if lis.count(0) != N:
        print(0)
        exit()

    #"右"が選べる"左"の選択肢を掛けていく
    cnt_0 = 1
    cnt_1 = 0
    ans = 1
    for k in range(1,2*N):
        if lis[k] == 0:
            cnt_0 += 1
            continue
        else:
            ans *= cnt_0 - cnt_1
            cnt_1 += 1

    #N!をかける
    for l in range(1,N+1):
        ans = ans*l %M
    
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    def input():
        return sys.stdin.readline()[:-1]

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

    if S[0]!='B' or S[-1]!='B':
        print(0)
        exit()

    mod = 10**9 + 7
    cnt_l = 1
    cnt_r = 0
    pre = 'B'
    pre_d = 1 #1がleft
    ans = 1

    for i in range(1,N*2):
        if S[i-1]==S[i]:
            if pre_d:
                pre_d = 0
                ans *= cnt_l - cnt_r
                cnt_r += 1
            else:
                pre_d = 1
                cnt_l += 1
        else:
            if pre_d:
                cnt_l += 1
            else:
                ans *= cnt_l - cnt_r
                cnt_r += 1

    for i in range(1,N+1):
        ans *= i
        ans %= mod
    if cnt_l!=N:
        print(0)
        exit()

    print(ans)

if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    def input():
        return sys.stdin.readline()[:-1]

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

    if S[0]!='B' or S[-1]!='B':
        print(0)
        exit()

    mod = 10**9 + 7
    cnt_l = 1
    cnt_r = 0
    pre = 'B'
    pre_d = 1 #1がleft
    ans = 1

    for i in range(1,N*2):
        s = S[i]
        pre = S[i-1]
        if pre==s:
            if pre_d:
                pre_d = 0
                ans *= cnt_l - cnt_r #ここまでに出てきたLeftの総数 - ここまでに出てきたrightの総数
                cnt_r += 1
            else:
                pre_d = 1
                cnt_l += 1
        else:
            if pre_d:
                cnt_l += 1
            else:
                ans *= cnt_l - cnt_r #ここまでに出てきたLeftの総数 - ここまでに出てきたrightの総数
                cnt_r += 1

    for i in range(1,N+1):
        ans *= i
        ans %= mod
    if cnt_l!=N:
        print(0)
        exit()

    print(ans)

if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():

    M = 10**9+7
    N = int(input())
    S = list(input())
    s = [0]*(2*N)

    #0ならW、1ならB
    for i in range(2*N):
        if S[i] == "B":
            s[i] = 1

    #端が0なら0を返す
    if s[0] == 0 or s[2*N-1] == 0:
        print(0)
        exit()

    ans = 0
    lis = [0]+[1]*(2*N-1) #0なら左、1なら右
    #全て0にする

    for j in range(1,2*N):
        if s[j-1] ^ s[j] == 1:
            lis[j] = lis[j-1]
        else:
            lis[j] = lis[j-1] ^ 1

    #左と右の数が違ったら0を返す
    if lis.count(0) != lis.count(1):
        print(0)
        exit()

    #"右"が選べる"左"の選択肢を掛けていく
    cnt_0 = 1
    cnt_1 = 0
    ans = 1
    for k in range(1,2*N):
        if lis[k] == 0:
            cnt_0 += 1
        else:
            ans *= cnt_0 - cnt_1
            cnt_1 += 1

    #N!をかける
    for l in range(1,N+1):
        ans *= l
        ans %= M
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:

M = 10**9+7
N = int(input())
S = list(input())
s = [0]*(2*N)

#0ならW、1ならB
for i in range(2*N):
    if S[i] == "B":
        s[i] = 1

#端が0なら0を返す
if s[0] == 0 or s[2*N-1] == 0:
    print(0)
    exit()

ans = 0
lis = [0]+[1]*(2*N-1) #0なら左、1なら右
#全て0にする

for j in range(1,2*N):
    if s[j-1] ^ s[j] == 1:
        lis[j] = lis[j-1]
    else:
        lis[j] = lis[j-1] ^ 1

#左と右の数が違ったら0を返す
if lis.count(0) != lis.count(1):
    print(0)
    exit()

#"右"が選べる"左"の選択肢を掛けていく
cnt_0 = 1
cnt_1 = 0
ans = 1
for k in range(1,2*N):
    if lis[k] == 0:
        cnt_0 += 1
    else:
        ans *= cnt_0 - cnt_1
        cnt_1 += 1

#N!をかける
for l in range(1,N+1):
    ans *= l
    ans %= M
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]

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

if S[0]!='B' or S[-1]!='B':
    print(0)
    exit()

mod = 10**9 + 7
cnt_l = 1
cnt_r = 0
pre_s = 'B'
pre_d = 1 #1がleft
ans = 1

for i,s in enumerate(S[1:]):
    if pre_s==s:
        if pre_d:
            pre_d = 0
            ans *= cnt_l - cnt_r #ここまでに出てきたLeftの総数 - ここまでに出てきたrightの総数
            cnt_r += 1
        else:
            pre_d = 1
            cnt_l += 1
    else:
        if pre_d:
            cnt_l += 1
        else:
            ans *= cnt_l - cnt_r #ここまでに出てきたLeftの総数 - ここまでに出てきたrightの総数
            cnt_r += 1
    pre_s = s

for i in range(1,N+1):
    ans *= i
    ans %= mod
if cnt_l!=N:
    print(0)
    exit()

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]

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

if S[0]!='B' or S[-1]!='B':
    print(0)
    exit()

mod = 10**9 + 7
cnt_l = 1
cnt_r = 0
pre_s = 'B'
pre_d = 1 #1がleft
ans = 1

for i in range(1,N*2):
    s = S[i]

    if pre_s==s:
        if pre_d:
            pre_d = 0
            ans *= cnt_l - cnt_r #ここまでに出てきたLeftの総数 - ここまでに出てきたrightの総数
            cnt_r += 1
        else:
            pre_d = 1
            cnt_l += 1
    else:
        if pre_d:
            cnt_l += 1
        else:
            ans *= cnt_l - cnt_r #ここまでに出てきたLeftの総数 - ここまでに出てきたrightの総数
            cnt_r += 1
    pre_s = s

for i in range(1,N+1):
    ans *= i
    ans %= mod
if cnt_l!=N:
    print(0)
    exit()

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]

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

if S[0]!='B' or S[-1]!='B':
    print(0)
    exit()

mod = 10**9 + 7
cnt_l = 1
cnt_r = 0
pre_s = 'B'
pre_d = 1 #1がleft
ans = 1

for i in range(1,N*2):
    s = S[i]

    if pre_s==s:
        if pre_d==1:
            d = 0
            ans *= cnt_l - cnt_r #ここまでに出てきたLeftの総数 - ここまでに出てきたrightの総数
            cnt_r += 1
        else:
            d = 1
            cnt_l += 1
    else:
        if pre_d==1:
            d = 1
            cnt_l += 1
        else:
            d = 0
            ans *= cnt_l - cnt_r #ここまでに出てきたLeftの総数 - ここまでに出てきたrightの総数
            cnt_r += 1
    pre_s = s
    pre_d = d

for i in range(1,N+1):
    ans *= i
    ans %= mod
if cnt_l!=N:
    print(0)
    exit()

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]

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

if S[0]!='B' or S[-1]!='B':
    print(0)
    exit()

mod = 10**9 + 7
cnt_l = 1
pre_s = 'B'
pre_d = 1 #1がleft
ans = 1

for i in range(1,N*2):
    s = S[i]

    if pre_s==s:
        if pre_d==1:
            d = 0
            ans *= (cnt_l*2 - i)%mod #ここまでに出てきたLeftの総数 - ここまでに出てきたrightの総数
        else:
            d = 1
            cnt_l += 1
    else:
        if pre_d==1:
            d = 1
            cnt_l += 1
        else:
            d = 0
            ans *= (cnt_l*2 - i)%mod #ここまでに出てきたLeftの総数 - ここまでに出てきたrightの総数
    pre_s = s
    pre_d = d

for i in range(1,N+1):
    ans *= i
    ans %= mod
if cnt_l!=N:
    print(0)
    exit()

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]

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

if S[0]!='B' or S[-1]!='B':
    print(0)
    exit()

mod = 10**9 + 7
cnt_l = 1
pre_s = 'B'
pre_d = 1 #1がleft
ans = 1

for i in range(1,N*2):
    s = S[i]

    if pre_s==s:
        if pre_d==1:
            d = 0
            ans *= (cnt_l*2 - i)%mod #ここまでに出てきたLeftの総数 - ここまでに出てきたrightの総数
        else:
            d = 1
            cnt_l += 1
    else:
        if pre_d==1:
            d = 1
            cnt_l += 1
        else:
            d = 0
            ans *= (cnt_l*2 - i)%mod #ここまでに出てきたLeftの総数 - ここまでに出てきたrightの総数
    pre_s = s
    pre_d = d
import math
k = math.factorial(N)
if cnt_l!=N:
    print(0)
    exit()

print(ans*k%mod)

Submission status: Time Limit Exceeded

Solution code:
import math
n = int(input())
s = input()
mod = 10**9 +7
if s[0] == "W" or s[-1] == "W":
    print(0)
else:
    d = "L"
    for i in range(1,2*n):
        if s[i-1] == s[i]:
            if d[-1] == "L":
                d += "R"
            else: d+= "L"
        else:
            if d[-1] == "L":
                d += "L"
            else: d += "R"

    count_l = 0
    count_r = 0
    prob = []
    for i in d:
        if i == "L":
            count_l += 1
            prob.append(0)
        else:
            if count_l - count_r <= 0:
                print(0)
                break
            else:
                prob.append(count_l - count_r)
            count_r += 1
    else:
        if count_l != count_r:
            print(0)
        else:
            count = 1
            for i in prob: # di= Rとなる各マスについて、Li - Ri通りの選択肢があり、それらの積が操作の場合の数になる。
                if i > 0:
                    count = count * i

            ans = count * math.factorial(n) % mod
            print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
n = int(input())
s = input()
mod = 10**9 +7
if s[0] == "W" or s[-1] == "W":
    print(0)
else:
    d = "L"
    for i in range(1,2*n):
        if s[i-1] == s[i]:
            if d[-1] == "L":
                d += "R"
            else: d+= "L"
        else:
            if d[-1] == "L":
                d += "L"
            else: d += "R"
    count_l = 0
    count_r = 0
    prob = []
    for i in d:
        if i == "L":
            count_l += 1
            prob.append(0)
        else:
            if count_l - count_r <= 0:
                print(0)
                break
            else:
                prob.append(count_l - count_r)
            count_r += 1
    else:
        if count_l != count_r:
            print(0)
        else:
            count = 1
            for i in prob: # di= Rとなる各マスについて、Li - Ri通りの選択肢があり、それらの積が操作の場合の数になる。
                if i > 0:
                    count = count * i
            ans = count * math.factorial(n) % mod
            print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math, string, itertools, fractions, heapq, collections, re, array, bisect, copy, functools, random
import sys
from collections import deque, defaultdict, Counter; from heapq import heappush, heappop
from itertools import permutations, combinations, product, accumulate, groupby
from bisect import bisect_left, bisect_right, insort_left, insort_right
from operator import itemgetter as ig
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20; INF = float("INF"); ans = 1; tmp = 0; cnt = 0; ansli = []; tmpli = []; candili = []; stillset = set()
eps = 1.0 / 10 ** 10; mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]; ddn = dd + [(-1, 1), (1, 1), (1, -1), (-1, -1)]; ddn9 = ddn + [(0, 0)]
"""for dx, dy in dd:
        nx = j + dx; ny = i + dy
            if 0 <= nx < w and 0 <= ny < h:"""
def wi(): return list(map(int, sys.stdin.readline().split()))
def wip(): return [int(x) - 1 for x in sys.stdin.readline().split()]#WideIntPoint
def ws(): return sys.stdin.readline().split()
def i(): return int(sys.stdin.readline())
def s(): return input()
def s_list(): return list(input())
def hi(n): return [i() for _ in range(n)]
def hs(n): return [s() for _ in range(n)]#HeightString
def mi(n): return [wi() for _ in range(n)]#MatrixInt
def num_grid(n): return [[int(i) for i in sys.stdin.readline().split()[0]] for _ in range(n)]#NumberGrid
def mip(n): return [wip() for _ in range(n)]
def ms(n): return [ws() for _ in range(n)]
def grid(n): return [s_list() for _ in range(n)]

n = i()
s = s()
new_s = ""
for i in range(2 * n):
    if (2 * n - i - 1) % 2 == 0:
        new_s += s[i]
    else:
        new_s += "W" if s[i] == "B" else "B"

lr = ""
for i in range(2 * n):
    if new_s[i] == "B":
        lr += "R"
    else:
        lr += "L"

if lr.count("R") != n:
    print(0)
    exit()

lcount = 0
for i in range(2 * n):
    if lr[i] == "L":
        lcount += 1
    else:
        ans *= lcount
        ans %= mod
        lcount -= 1

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = str(input())
mod = 10**9 +7
if s[0] == "W" or s[-1] == "W":
    print(0)
else:
    count_l = 0
    count_r = 0
    d = ""
    for i in range(2*n): # diを、i番目のマスを左側として選ぶべきならL、右側として選ぶべきならRとする。
        if i == 0:
            d += "L"
            count_l += 1
        else:
            if s[i-1] == s[i]:
                if d[-1] == "L":
                    d += "R"
                    count_r += 1
                else:
                    d += "L"
                    count_l += 1
            else:
                if d[-1] == "L":
                    d += "L"
                    count_l += 1
                else:
                    d += "R"
                    count_r += 1
    if count_l != count_r:
        print(0)
    else:
        probab = []
        count_l = 0
        count_r = 0
        for i in d:
            if i == "L":
                count_l += 1
            else:
                probab.append(count_l - count_r)
                count_r += 1
        count = 1
        for i in probab: # di= Rとなる各マスについて、Li - Ri通りの選択肢があり、それらの積が操作の場合の数になる。
            count = count * i
        for i in range(n): # 操作は必ずN回行うので、操作の順番を入れ替えた場合も考慮する
            count = count * (i+1)

        ans = count % mod
        print(ans)

Submission status: Time Limit Exceeded

Solution code:
mod = 10**9 + 7

def factorial(n):
    res = 1
    for p in range(2,n+1):
        res *= p
        res %= mod
    return res

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

T = "L"

L = 0
R = 0

for i in range(1,2*N):
    if S[i] == "W":
        if (L - R + 1) % 2 == 0:
            R += 1
            T += "R"
        else:
            L += 1
            T += "L"
    else:
        if (L - R + 1) % 2 == 0:
            L += 1
            T += "L"
        else:
            R += 1
            T += "R"

if T[-1] == "L" or T.count("L") > N:
    print(0)
    exit()

L = 0
ans = 1

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

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

Submission status: Time Limit Exceeded

Solution code:
import math

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

left = 0
ret = 1
for i in range(len(S)):
    if S[i] == 'W':
        if left % 2 == 1:
            left += 1
        else:
            if left > 0:
                ret *= left
                left -= 1
            else:
                print(0)
                exit()
    else:
        if left % 2 == 1:
            ret *= left
            left -= 1
        else:
            left += 1

if left > 0:
    print(0)
    exit()
            
for i in range(1, N+1):
    ret *= i
    ret %= mod
print(ret)

Submission status: Time Limit Exceeded

Solution code:
import math
import sys
from copy import copy
import numpy as np
from collections import defaultdict, deque, Counter 
from itertools import accumulate, product, permutations,combinations, combinations_with_replacement
from operator import itemgetter
from bisect import bisect_left,bisect
from heapq import heappop,heappush
from fractions import gcd

max_value = 1000000000
min_value = -1000000000
sys.setrecursionlimit(max_value)

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

count = 0


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

LR_list = ['' for i in range(2*n)]
LR_list[0] = 'L'

for i in range(1,len(LR_list)):
    if s[i] == s[i-1]:
        if LR_list[i-1] == 'R':
            LR_list[i] = 'L'
        else:
            LR_list[i] = 'R'
    else:
        if LR_list[i-1] == 'R':
            LR_list[i] = 'R'
        else:
            LR_list[i] = 'L'

values = []

if LR_list.count('L') != LR_list.count('R'):
    print(0)
    sys.exit()
for i in range(len(LR_list)):
    if LR_list[i] == 'R':
        li = LR_list[:i].count('L')
        ri = LR_list[:i].count('R')
        values.append(li-ri)
print(np.array(values).prod()*math.factorial(n))

Submission status: Time Limit Exceeded

Solution code:
def main():
  import math
  import sys
  imput=sys.stdin.readline
  a=int(input())
  b=input()
  R=0
  L=0
  ans=1
  mod=10**9+7
  if b[0]=="W" or b[-1]=="W":
    print(0)
    exit()
  for i in range(2*a):
    if i==0:
      L+=1
      fr="L"
    else:
      if b[i]==b[i-1]:
        if fr=="L":
          ans=ans*(L-R)
          R+=1
          fr="R"
        else:
          L+=1
          fr="L"
      else:
        if fr=="L":
          L+=1
        else:
          ans=ans*(L-R)
          R+=1
    
  if L!=R:
    print(0)
    exit()


  
  print(ans*math.factorial(a)%mod)
  

if __name__ == '__main__':  
  main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()
MOD = 10**9 + 7
li = []
for i in range(2*n):
    if i % 2 == 0 and s[i] == "B":
        li.append("W")
    elif i % 2 == 0 and s[i] == "W":
        li.append("B")
    elif i % 2 == 1 and s[i] == "B":
        li.append("B")
    elif i % 2 == 1 and s[i] == "W":
        li.append("W")
        
cnt = 0
ans = 1
for string in li:
    if string == "W":
        cnt += 1
    else:
        if cnt <= 0:
            print(0)
            exit()
        ans *= cnt
        cnt -= 1

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

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9+7
N = int(input())
S = input()
 
if S[0] == "W" or S[-1] == "W":
  print(0)
  exit()

counter = 0
output = 1

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

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
a=int(input())
b=input()
R=0
L=0
ans=1
mod=10**9+7
if b[0]=="W" or b[-1]=="W":
  print(0)
  exit()
for i in range(2*a):
  if i==0:
    L+=1
    fr="L"
  else:
    if b[i]==b[i-1]:
      if fr=="L":
        ans=ans*(L-R)
        R+=1
        fr="R"
      else:
        L+=1
        fr="L"
    else:
      if fr=="L":
        L+=1
      else:
        ans=ans*(L-R)
        R+=1
    
if L!=R:
  print(0)
  exit()


  
print(ans*math.factorial(a)%mod)

Submission status: Time Limit Exceeded

Solution code:
import math
n=int(input())
cell = list(map(lambda x: {"B": True, "W": False}[x], input()))
section = 0
ans = 1
flag = True
for val in cell:
    buf = val if section % 2 == 0 else not val
    if buf:
        section += 1
    else:
        if section > 0:
            ans *= section
            section -= 1
        else:
            flag = False
            break
if section== 0 and flag:
    print((math.factorial(n)*ans)%(10**9+7))
else:
    print(0)

Submission status: Time Limit Exceeded

Solution code:
import math
a=int(input())
b=input()
R=[]
L=0
mod=10**9+7
if b[0]=="W" or b[-1]=="W":
  print(0)
  exit()
for i in range(2*a):
  if i==0:
    L+=1
    fr="L"
  else:
    if b[i]==b[i-1]:
      if fr=="L":
        R.append(L)
        fr="R"
      else:
        L+=1
        fr="L"
    else:
      if fr=="L":
        L+=1
      else:
        R.append(L)
    
if L!=len(R):
  print(0)
  exit()

ans=1
for i,k in enumerate(R):
  ans=ans*(k-i)
  
print(ans*math.factorial(a)%mod)

Submission status: Time Limit Exceeded

Solution code:
import math

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

if s[0] == 'W' or s[-1] == 'W':
    print(0)
else:    
    s_lr = 'L'
    for i in range(len(s)-1):
        if s[i+1] == s[i]:
            if s_lr[-1] == 'L':
                s_lr += 'R'
            else:
                s_lr += 'L'
        else:
            if s_lr[-1] == 'L':
                s_lr += 'L'
            else:
                s_lr += 'R'    
    l_cnt = 0
    r_cnt = 0
    lst = []
    for i in s_lr:
        if i == 'L':
            l_cnt += 1
            lst.append(0)
        else:
            if l_cnt - r_cnt <= 0:
                print(0)
                break
            else:
                lst.append(l_cnt - r_cnt)
            r_cnt += 1
    else:
        if l_cnt != r_cnt:
            print(0)
        else:
            res = 1
            for i in lst:
                if i > 0:
                    res = res * i % (10**9 + 7)
            print(res * math.factorial(n) % (10**9 + 7) )

Submission status: Time Limit Exceeded

Solution code:
MOD = int(1e9+7)
N = int(input())
S = input()
LR = [0]*(2*N)
LR[0] = 0
l, r = 1, 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] = 0 if LR[i-1] == 1 else 1
    else:
        LR[i] = LR[i-1]
    if LR[i] == 0:
        l += 1
    else:
        r += 1
if l != r:
    print(0)
    exit()
L = 0
R = 0
count = 1
for w in LR:
    if w == 0:
        L += 1
    else:
        count *= L - R
        R += 1
for i in range(1, N+1):
    count = count * i % MOD
print(count)

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 = list(map(lambda c: c == 'W', input())) # W: True, B: False
  if S[0] or S[2 * N - 1]: return 0

  D = [ True ] * (2 * N) # L: True, R: False
  d = True
  for i in range(1, N * 2):
    if S[i] == S[i - 1]: d = not d
    D[i] = d

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

  return mult(factorial(N), C) if c == 0 else 0

print(solve())

Submission status: Time Limit Exceeded

Solution code:
MOD = int(1e9+7)
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
for i in range(1, N+1):
    count = count * i % MOD
print(count)