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:
"""
N = int(input())
A, B = map(int,input().split())
lst = [list(map(int,input().split())) for i in range(M)]
A = list(map(int,input().split()))
"""

import math

mod = int(1e9+7)

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

""" 
##for test
N = 100000
S = 'B'*(2*N)
#print(S)
"""

rest = 0
cnt = 1
for i in range(2*N):
  if (i%2 == 0 and S[i]=='B') or (i%2 == 1 and S[i]=='W'): ## 続行
    rest += 1
  else: ## 枝を一つ繋げる
    if rest < 1: ## 繋げる枝がない場合
      print(0)
      exit()
    else:
      cnt = (cnt * rest) % mod
      rest -= 1
else:
  if rest != 0: ## 繋ぐことのできなかった枝が残っている場合
    print(0)
    exit()

ans = cnt * (math.factorial(N) % mod) % mod
print(ans)

Submission status: Accepted

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

ans = int(S[0]==S[-1]=="B")

n = 1
for s in S[1:]:
    if n==0 and s=="W":
        ans = 0
        break
    if (s=="B") ^ (n%2 == 0):
        ans = ans*n%mod
        n -= 1
    else:
        n += 1
if n!=0 : ans = 0
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

fib = [1]
for i in range(1, n+1):
    f = fib[i-1] * i % mod
    fib.append(f)

memo = [i%2 for i in range(2*n)]
for i, si in enumerate(s):
    if si == "B":
        memo[i] += 1
        memo[i] %= 2

ans = 1
count = 0
for i in range(2*n):
    if memo[i] == 1:
        count += 1
    else:
        ans *= count
        ans %= mod
        count -= 1
if count != 0:
    print(0)
else:
    print(ans * fib[n] % mod)

Submission status: Accepted

Solution code:
N = int(input())
S = [0 if _ == 'W' else 1 for _ in input()]
array = [0] * N
if S[0] == 0 or S[-1] == 0:
    print(0)
    exit()
cl = 1
ans = [0]
for i in range(1, 2 * N):
    if S[i] == S[i - 1]:
        ans += [1]
        S[i] = 1 - S[i]
    else:
        ans += [0]
x = 1
c = 0
mod = 10**9 + 7
for a in ans:
    if a:
        x *= c
        x %= mod
        c -= 1
    else:
        c += 1
if c == 0:
    for i in range(2, N + 1):
        x *= i
        x %= mod
    print(x)
else:
    print(0)

Submission status: Accepted

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

t = ["" for i in range(2*n)]
cntr, cntl = 0, 0

for i in range(2*n):
  if i%2==0 and s[i]=='B':
    t[i] = "R"
    cntr += 1
  elif i%2==0 and s[i]=='W':
    t[i] = "L"
    cntl += 1
  elif i%2==1 and s[i]=='B':
    t[i] = "L"
    cntl += 1
  elif i%2==1 and s[i]=='W':
    t[i] = "R"
    cntr += 1
if cntl!=cntr:
  print(0)
  exit()

cur = 1
rs, ls = 0, 0
for i in range(2*n-1, -1, -1):
  if t[i]=="L":
    ls += 1
  else:
    cur = (cur*(max(0, ls-rs)))%MOD
    rs += 1

MAX = 2*10**5+1
fact = [0 for i in range(MAX)]
inv = [0 for i in range(MAX)]
invfact = [0 for i in range(MAX)]

def comb_build(n):
  fact[0] = inv[0] = invfact[0] = 1
  fact[1] = inv[1] = invfact[1] = 1
  for i in range(2, n):
    fact[i] = fact[i-1]*i%MOD
    inv[i] = inv[MOD%i]*(MOD-MOD//i)%MOD
    invfact[i] = invfact[i-1]*inv[i]%MOD

comb_build(MAX)
print((cur*fact[n])%MOD)

Submission status: Accepted

Solution code:
from collections import Counter
N=int(input())
mod=10**9+7
factl=[1]
for i in range(1,N+1):
    factl.append(factl[-1]*i%mod)
invl=[pow(factl[-1],mod-2,mod)]
for i in range(N,0,-1):
    invl.append(invl[-1]*i%mod)
invl.reverse()
def Comb(a,b):
    return factl[a]*invl[a-b]*invl[b]

S=list(input())
RS=S[::-1]
L=[0]*2*N
r=0
for i in range(N):
    if r%2==0 and S[i]=='B':
        L[i]=1
        r+=1
    elif r%2==1 and S[i]=='W':
        L[i]=1
        r+=1
    else:
        r-=1
r=0
L=L[::-1]
S=S[::-1]
for i in range(N):
    if r%2==0 and S[i]=='B':
        r+=1
    elif r%2==1 and S[i]=='W':
        r+=1
    else:
        r-=1
        L[i]=1
L=L[::-1]
Cnt=Counter(L)
if Cnt[0]!=Cnt[1]:
    print(0)
    exit()
l=0
ans=1
for i in range(2*N):
    if L[i]==1:
        l+=1
    else:
        ans*=l
        ans%=mod
        l-=1
ans=ans*factl[N]%mod
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
S=input()
x=0
r=1
m=10**9+7
for s in S:
    if s=='W':
        if x%2==1:
            x+=1
        elif x>0:
            r=(r*x)%m
            x-=1
        else:
            r=-1
            break
    else:
        if x%2==0:
            x+=1
        else:
            r=(r*x)%m
            x-=1
if r==-1 or x>0:
    print(0)
else:
    a=1
    for i in range(N):
        a=a*(i+1)%m
    print((r*a)%m)

Submission status: Accepted

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
        ans %= MOD

    return ans % MOD

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

ans = 1

open = 0
for c in s:
    # print(c, ans, open, cur)
    if c == "B":
        if open%2 == 0:
            open += 1

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


    else:
        if open%2 == 1:
            open += 1

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


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

Submission status: Accepted

Solution code:
import sys, math
from collections import deque

readline = sys.stdin.readline

N = int(readline())
S = readline().strip()

P = 10 ** 9 + 7

d = 0
count = 1
for c in S:
    if d % 2 == 0:
        if c == 'B':
            d += 1
        else:
            count *= d
            count %= P
            d -= 1
    else:
        if c == 'B':
            count *= d
            count %= P
            d -= 1

        else:
            d += 1
    if d < 0:
        print(0)
        exit(0)

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

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

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
s = input()
lr = ["" for i in range(2*n)]
sm = 0
for i in range(2*n):
    if s[i] == "W":
        if sm%2 == 0:
            lr[i] = "R"
            sm -= 1
        else:
            lr[i] = "L"
            sm += 1
    else:
        if sm%2 == 0:
            lr[i] = "L"
            sm += 1
        else:
            lr[i] = "R"
            sm -= 1
    if sm < 0:
        print(0)
        exit()
if sm != 0:
    print(0)
    exit()

def f(x,y):
    r = 1
    for i in range(y):
        r = (r * (x-i))%(10**9+7)
    return r


suml = 0
sumr = 0
sp = "R"
ans = 1
lr.append("L")
for i in range(2*n+1):
    if sp == "R" and lr[i] == "L":
        ans = (ans * f(suml,sumr)) % (10**9+7)
        suml = suml - sumr
        sumr = 0
    if lr[i] == "L":
        suml += 1
    elif lr[i] == "R":
        sumr += 1
    sp = lr[i]

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

Submission status: Accepted

Solution code:
mod = 10**9+7

def frac(limit):
    frac = [1]*limit
    for i in range(2,limit):
        frac[i] = i * frac[i-1]%mod
    fraci = [None]*limit
    fraci[-1] = pow(frac[-1], mod -2, mod)
    for i in range(-2, -limit-1, -1):
        fraci[i] = fraci[i+1] * (limit + i + 1) % mod
    return frac, fraci
frac, fraci = frac(200000)

def count(S):
    res = 1
    cnt = 0
    for s in S:
        if s:
            cnt += 1
        else:
            res = (res*cnt)%mod
            cnt -= 1
        if cnt < 0:
            return 0
    return res
N = int(input())
S = [1 if s == 'B' else 0 for s in input().strip()]
L = 2*N
S = [(S[i] + i)%2 for i in range(L)]
if sum(S) != N:
    print(0)
else:
    print(count(S)*frac[N]%mod)

Submission status: Accepted

Solution code:
n = int(input())
s = input()

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

    elif s[i] == 'W':
        if i % 2 == 0:
            r.append(i)
        else:
            l.append(i)

if len(r) != len(l):
    print(0)
else:
    from bisect import bisect_left
    ans = 1
    counter = 0
    for i in reversed(range(len(l))):
        _l = l[i]
        idx = bisect_left(r, _l)

        ans *= max((len(r) - counter - idx), 0)
        ans = ans % (10 ** 9 + 7)
        counter += 1

        # print(idx + counter)
    from math import factorial

    ans *= factorial(len(r))
    print(ans % (10 ** 9 + 7))

Submission status: Accepted

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

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

for i in range(2*N):
    if S[i]=="B":
        S[i]=0
    else:
        S[i]=1

    if i%2==1:
        S[i]=(S[i]+1)%2


ones=0
ANS=1

if S.count(1)!=S.count(0):
    print(0)
    sys.exit()

for i in range(2*N-1,-1,-1):
    if S[i]==1:
        ones+=1

    else:
        ANS=ANS*ones%mod
        ones-=1


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


print(ANS)

Submission status: Accepted

Solution code:
n = int(input())
s = input()

m = 1

for i in range(1,n+1):
    m*=i
    m%=10**9+7

if s[0]=='B' and s[-1]=='B':
    if s.count('B')%2==0:
        l = [1]
        for i in range(1,len(s)):
            if s[i-1]!=s[i] and l[-1]==1:
                l.append(1)
            elif s[i-1]==s[i] and l[-1]==0:
                l.append(1)
            else:
                l.append(0)
        x = [1]
        for i in range(1,len(l)):
            if l[i]==1:
                x.append(x[-1]+1)
            else:
                x.append(x[-1]-1)
        if x[-1]!=0:
            print(0)
            exit()
        ans = 1
        for i in range(len(l)):
            if l[i]==0:
                ans *= x[i-1]
                ans %= 10**9+7
        print(m*ans%(10**9+7))
        exit()
print(0)

Submission status: Accepted

Solution code:
n = int(input())
s = input()

sf = []
mod = 1000000007

if(s[0]=='W'):
    sf.append(999999999)
else:
    sf.append(0)
for i in range(2*n-1):
    if(s[i]==s[i+1]):
        sf.append(1-sf[-1])
    else:
        sf.append(sf[-1])

if(sum(sf)==n):
    count=0
    ans=1
    for i in range(2*n):
        if(sf[2*n-1-i]==1):
            count+=1
        else:
            ans= (ans*count)%mod
            count-=1
    for i in range(n):
        ans = (ans*(i+1))%mod
    print(ans)
else:
    print(0)

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7

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

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

    dir = [0] * (2*n)

    for i in range(1,2*n):
        if s[i] != s[i-1]:
            dir[i] = dir[i-1]
        else:
            dir[i] = (dir[i-1] + 1) % 2

    c = 0

    for x in dir:
        if x == 0:
            c += 1
    
    #print(c)
    #print(dir)
    if c != n:
        print(0)
    
    else:
        ans = 1
        count = 0

        for i in range(2*n):
            if dir[i] == 0:
                count += 1
            else:
                ans = (ans * count) % MOD
                count -= 1
        
        for k in range(1,n+1):
            ans = (ans * k) % MOD
        
        print(ans)

Submission status: Accepted

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

ans = 1
mul = 0
for i in range(n * 2):
    if s[i] == "B":
        if mul % 2 == 0:
            mul += 1
        else:
            ans *= mul
            ans %= mod
            mul -= 1
    else:
        if mul % 2 == 1:
            mul += 1
        else:
            ans *= mul
            ans %= mod
            mul -= 1
for i in range(n):
    ans *= (i + 1)
    ans %= mod
if mul != 0:
    ans = 0
print(ans)

Submission status: Accepted

Solution code:
import sys
mod = 10**9 + 7
N=int(input())
S = input()
leftL = 0
leftR = 0
ISR = []
for s in S:
  if s=="B":#leftL-leftRと同符号
    isR = abs(leftL-leftR)
  else:
    isR = int(not bool(abs(leftL-leftR)))
  if isR:
    leftR = (leftR+1)%2
  else:
    leftL = (leftL+1)%2
  ISR.append(isR)

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

zanki = 0
ans = 1
for i in ISR:
  if zanki<0:
    print(0)
    sys.exit()
  if i:#Rの場合
    ans *= zanki
    zanki -= 1
  else:
    zanki += 1
  ans %= mod

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

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
s = list(input())

a = [0]*(2*n)
cnt = 0
for i in range(2*n):
    if s[i] == 'B':
        if cnt % 2 == 0:
            a[i] = 1
            cnt += 1
        else:
            a[i] = -1
            cnt -= 1

    else:
        if cnt % 2 == 0:
            a[i] = -1
            cnt -= 1
        else:
            a[i] = 1
            cnt += 1

pl = 0
judge = False
mod = 10**9+7
#print(a)

res = 1
for e in a:
    if e > 0:
        pl += 1
    else:
        if pl <= 0:
            judge = True
            break
        res = res*pl%mod
        pl -= 1

if judge or pl != 0:
    print(0)
    exit()

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

Submission status: Accepted

Solution code:
import math
mod = 10**9+7
N = int(input())
S = input()
cnt = 0
ans = 1
for i in range(N*2):
    if S[i]=='W':
        if cnt%2 == 0:
            ans*=cnt
            ans%=mod
            cnt-=1
        else:
            cnt+=1
    else:
        if cnt%2 == 0:
            cnt+=1
        else:
            ans*=cnt
            ans%=mod
            cnt-=1
if cnt==0:
    for i in range(1, N+1):
        ans*=i
        ans%=mod
    print(ans)
else:
    print(0)

Submission status: Accepted

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 = (ans * now) % (10 ** 9 + 7)
            now -= 1

    if S[i] == "B":

        if now % 2 != 0:

            ans = (ans * now) % (10 ** 9 + 7)

            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: Accepted

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

r = 1
for i in range(2, n + 1):
    r = (r * i) % m
p = 0
for i, c in enumerate(s):
    if int(c == 'W') == i % 2:
        p += 1
    else:
        r = (r * p) % m
        p -= 1
print(r if p == 0 else 0)

Submission status: Accepted

Solution code:
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
# input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools


def main():
    num = int(input())
    data = list(input())

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

    dp = [0 for i in range(2 * num)]
    now_plus = 0
    for i in range(2 * num):
        now_str = data[i]
        # print(now_plus, now_str)
        if now_plus % 2 == 0 and now_str == 'B':
            dp[i] = 1
            now_plus += 1
        elif now_plus % 2 == 0 and now_str == 'W':
            dp[i] = 0
            now_plus -= 1
        elif now_plus % 2 == 1 and now_str == 'B':
            dp[i] = 0
            now_plus -= 1
        elif now_plus % 2 == 1 and now_str == 'W':
            dp[i] = 1
            now_plus += 1


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

    mod = 10 ** 9 + 7

    # print(dp)


    count1 = 0
    ans = 1
    for i in range(2 * num):
        if dp[i]:
            count1 += 1
        else:
            ans *= count1
            ans %= mod
            count1 -= 1

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

    print(ans)





if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
S = input()
MOD = 10**9 + 7
threads = 0
M = 1
for s in S:
    if (threads + int(s=='B')) % 2:
        threads += 1
    else:
        M *= threads
        M %= MOD
        threads -= 1

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

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

print((M*K)%MOD)

Submission status: Accepted

Solution code:
import os
import sys

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

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


def factorial(n):
    ret = 1
    for a in range(2, n + 1):
        ret = ret * a % MOD
    return ret


def solve(S):
    S = np.array(list(S)) == 'B'
    # 右にするか左にするか
    LR = np.zeros_like(S, dtype=str)
    LR[::2][S[::2] == 0] = 'R'
    LR[::2][S[::2] == 1] = 'L'
    LR[1::2][S[1::2] == 0] = 'L'
    LR[1::2][S[1::2] == 1] = 'R'
    if (LR == 'R').sum() != len(LR) // 2:
        return 0
    l_cnt = (LR == 'L').cumsum()
    ans = 1
    r = 0
    for i, lr in enumerate(LR):
        if lr == 'R':
            l = l_cnt[i] - r
            if l <= 0:
                return 0
            ans = ans * l % MOD
            r += 1
    return ans * factorial(len(LR) // 2) % MOD


ans = solve(S)
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline #文字列入力のときは注意
 
n = int(input())
#n,k = [int(i) for i in readline().split()]
#a = [int(i) for i in readline().split()]
s = input()

#1: 大きいのとつながる 

res = [(i&1)^(1 if c == "B" else 0) for i,c in enumerate(s)]
#print(res)

ans = 1
num = 0
MOD = 10**9+7
for i in res:
    if i: num += 1
    else:
        ans = ans*num%MOD
        num -= 1
if num != 0: ans = 0


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

print(ans)

Submission status: Accepted

Solution code:
from math import factorial
MOD = 10**9 + 7

n = int(input())
s = input()
a = [0] * (n * 2)
for i in range(n*2):
    if s[i] == "B":
        a[i] = 1
        
prevbit = 0
prevlr = 0
lr = [0] * (n*2)
for i in range(n*2):
    if a[i] != prevbit:
        lr[i] = prevlr
    else:
        lr[i] = (prevlr + 1) % 2
    prevlr = lr[i]
    prevbit = a[i]
    
#print(lr)
    
ans = 1
if sum(lr) != n:
    ans = 0
else:
    suml = 0
    for i in range(n*2):
        if lr[i] == 1:
            ans = (ans * suml) % MOD
            suml -= 1
            if suml < 0:
                ans = 0
                break
        else:
            suml += 1
            
print((ans*factorial(n))%MOD)

Submission status: Accepted

Solution code:
N = int(input())

S = input()

mod = 10**9+7

count_l = 0
count_r = 0
ans = 1
for i in range(2*N):
        if count_l-count_r==0:
                if S[i]=="W":
                        ans=0
                        break
                else:
                        count_l+=1
        else:
                if S[i]=="W":
                        if (count_l-count_r)%2==1:
                                count_l+=1
                        else:
                                ans*=(count_l-count_r)
                                ans%=mod
                                count_r+=1
                else:
                        if (count_l-count_r)%2==1:
                                ans*=(count_l-count_r)
                                ans%=mod
                                count_r+=1
                        else:
                                count_l+=1

if count_l-count_r!=0:
        print(0)
else:
        for i in range(1,N+1):
                ans*=i
                ans%=mod


        print(ans)

Submission status: Accepted

Solution code:
import bisect

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

small = []
large = []
for i in range(N * 2):
    if S[i] == 'B':
        if i % 2 == 0:
            small.append(i)
        else:
            large.append(i)
    else:
        if i % 2 == 0:
            large.append(i)
        else:
            small.append(i)

if len(small) != len(large):
    print(0)
else:
    ans = 1
    for i in range(N):
        large_i = large[i]
        smaller = bisect.bisect_left(small, large_i)
        ans = (ans * (smaller - i)) % mod
    for i in range(1, N + 1):
        ans = (ans * i) % mod
    print(ans)

Submission status: Accepted

Solution code:
n = int(input())
raw = input()
if raw[0] == 'B':
  imos = [1]
else:
  imos = [0]
for i in range(1,2*n):
  if raw[i-1] == raw[i]:
    imos.append(0)
  else:
    imos.append(1)
#print(imos)
ans = 1
mod = 10 ** 9 + 7
l = 0
att = 0
for i in range(2*n):
  if imos[i] ^ att == 0:
    if l == 0:
      print(0)
      break
    ans *= l
    ans %= mod
    l -= 1
    att = 1
  else:
    l += 1
    att = 0
  #print(ans,l,att)
else:
  if l != 0:
    print(0)
  else:
    for j in range(1,n+1):
      ans *= j
      ans %= mod
    print(ans)

Submission status: Accepted

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

LARGE = 10 ** 9 + 7

res = 1
arrows = 0

for i in range(2 * N):
    if arrows == 0 and S[i] == "W":
        res = 0
        break
    if S[i] == "B" and arrows % 2 == 0:
        arrows += 1
    elif S[i] == "W" and arrows % 2 == 1:
        arrows += 1
    else:
        res *= arrows
        res %= LARGE
        arrows -= 1

if arrows > 0:
    res = 0


for i in range(1, N + 1):
    res *= i
    res %= LARGE

if __name__ == "__main__":
    print(res)

Submission status: Accepted

Solution code:
n = int(input())
s = list(input().replace("B","0").replace("W","1"))
s = list(map(int,s))
mod = 10**9+7
stock = 0
ans = 1
for x in s:
    if x != stock%2:
        if stock == 0:
            print(0)
            exit()
        ans *= stock
        ans %= mod
        stock -= 1
    else:
        stock += 1
if stock:
    print(0)
    exit()
ta = 1
for i in range(1,n+1):
    ta = ta*i%mod
print(ta*ans%mod)

Submission status: Accepted

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

now = 0
result = 1
for i in range(2 * n):
    if s[i] == 'B':
        if now % 2 == 0:
            now += 1
        else:
            result = (result * now) % mod
            now -= 1
    else:
        if now % 2 == 0:
            result = (result * now) % mod
            now -= 1
        else:
            now += 1
if now != 0:
    result = 0
print((result * math.factorial(n)) % mod)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(300000)

MOD = 1000000007  # type: int

def solve(N: int, S: str):
    tmp = 0
    p = 1
    for c in S:
        if c == 'B':
            if tmp % 2 == 0:
                tmp += 1
            elif tmp > 0:
                p *= tmp
                p %= MOD
                tmp -= 1
            else:
                print(0)
                return
        if c == 'W':
            if tmp % 2 == 1:
                tmp += 1
            elif tmp > 0:
                p *= tmp
                p %= MOD
                tmp -= 1
            else:
                print(0)
                return
    if tmp > 0:
        print(0)
        return

    ret = 1
    for i in range(1, N + 1):
        ret *= i
        ret %= MOD
    ret *= p
    ret %= MOD
    print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    S = next(tokens)  # type: str
    solve(N, S)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

MOD = 10**9 + 7

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

is_left = [(i%2 == 0) ^ (x == 'W') for i,x in enumerate(S)]

answer = 1
left = 0
for bl in is_left:
    if bl:
        left += 1
    else:
        answer *= left
        left -= 1
        answer %= MOD
if left != 0:
    answer = 0

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

print(answer)

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

N = inp()
S = list(input())

dp = [0]*(2*N)

cnt = 0
ans = 1
for i in range(2*N):
    s = S[i]
    if s == 'B':
        if cnt%2 == 0:
            cnt += 1
            ans *= cnt
        else:
            cnt -= 1
    elif s == 'W':
        if cnt%2 == 0:
            cnt -= 1
        else:
            cnt += 1
            ans *= cnt
    ans %= mod


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

if cnt != 0 or S[0]=='W' or S[-1]=='W':
    print(0)
else:
    print(ans%mod)

Submission status: Accepted

Solution code:
N = int(input())
A = [1 if a == "B" else 0 for a in input()]
P = 10 ** 9 + 7
k = 0
ans = 1
for i in range(N):
    ans = (ans * (i+1)) % P
for i in range(N * 2):
    if k == 0:
        if A[i] == 0:
            ans = 0
            break
        else:
            k += 1
    elif (k + A[i]) % 2 == 0:
        ans = (ans * k) % P
        k -= 1
    else:
        k += 1
if k == 0:
    print(ans)
else:
    print(0)

Submission status: Runtime Error

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
for i in range(N):
    ans *= sums[left[i]]-(N-1-i)
    ans %= mod
print(ans)

Submission status: Runtime Error

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: Runtime Error

Solution code:
from itertools import groupby
import heapq

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

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

inverse=[pow(fact[i],mod-2,mod) for i in range(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:
    print(ans)

Submission status: Runtime Error

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

kaijyo = [1]
for i in range(n):
	x = (kaijyo[i] * (i+1)) % MOD
	kaijyo.append(x)


if (s[0] == 'B') and (s[-1] == 'B'):
	string = []
	cnt = 1
	for i in range(2*n-1):
		if s[i] == s[i+1]:
			cnt += 1
		else:
			string.append(cnt)
			cnt = 1
		if i == 2*n-2:
			string.append(cnt)
	m = (len(string)-1)//2
	if len(string) % 2 == 0:
		print(0)
	elif string[m] % 2 == 1:
		print(0)
	else:
		l = []
		for i in range(m):
			if string[i] != 1:
				k = (string[i] - 1)//2
				for _ in range(k):
					l.append(i+1)
		for j in range(m+1, len(string)):
			if string[j] != 1:
				k = (string[j] - 1)//2
				for _ in range(k):
					l.append(len(string)-j)
	ans = (kaijyo[n] * kaijyo[m+1]) % MOD
	for i in range(len(l)):
		ans = (ans * l[i]) % MOD
	print(ans)

				
else:
	print(0)

Submission status: Runtime Error

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%2==0:
		print(0)
		return 0
	ans=1
	for i in range(lx//2):
		if x[i]%2==0:
			ans=0
		else:
			ans=ans*pow(i+1,x[i]//2,mod)%mod
	if x[lx//2]%2==1:
		ans=0
	else:
		ans=ans*pow(lx//2+1,x[lx//2]//2,mod)%mod
	for i in range(lx//2+1,lx):
		if x[i]%2==0:
			ans=0
		else:
			ans=ans*pow(lx-i,x[i]//2+1,mod)%mod
	for i in range(2,n+1):
		ans=ans*i%mod
	if ans==0:
		print(ans/0)
main()

Submission status: Runtime Error

Solution code:
def calcfact2(n):
  seki = 1
  if n % 2 == 0:
    for i in range(1,(n+2)//2):
      seki *= i*(n+1-i)
  else:
    for j in range(1,(n+1)//2):
      seki *= (i+1)*(n+1-i)
  return seki

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

ans = 0
if S[0] != "W" or S[-1] != "W":

  LRlist = [""]*len(S)
  LRlist[0] = "L"
  for i in range(1,len(S)):
    if S[i-1] == S[i]:
      if LRlist[i-1] == "L":
        LRlist[i] = "R"
      else:
        LRlist[i] = "L"
    else:
      LRlist[i] = LRlist[i-1]
      
  if LRlist.count("L") == LRlist.count("R"):

    countL = 0
    selectedL = 0
    numOfComb = 1
    for j in range(len(LRlist)):
      if LRlist[j] == "R":
        numOfComb *= (countL - selectedL)
        selectedL += 1
      else:
        countL += 1

    ans = numOfComb * calcfact2(N)
    
print(ans % defi)