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

Solution code:
when NimMajor == 0 and NimMinor <= 18: import future
else: import sugar

# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
from sequtils import map, mapIt, toSeq
from strutils import split, parseInt, parseFloat, parseBool, parseEnum
when NimMajor == 0 and NimMinor >= 14: from strutils import parseUint

import macros
# headaux macro -- https://stackoverflow.com/questions/31948131/unpack-multiple-variables-from-sequence
# unpack (toTuple) macro  -- https://chy72.hatenablog.com/entry/2017/12/16/214708
macro unpack*(input: array|seq|tuple; count: static[int]): untyped =
  var t = genSym()
  result = quote do: (let `t` = `input`; ())
  when NimMajor == 0 and NimMinor <= 17:
    for i in 0..<count: result[0][1].add quote do: `t`[`i`]
  else:
    for i in 0..<count: result[1].add quote do: `t`[`i`]

template input*(typ: static[typedesc]): seq =
  when typ is char:
    toSeq(stdin.readLine.items)
  elif typ is string:
    stdin.readLine.split
  else:
    stdin.readLine.split.map(`parse typ`)

# 2引数の input() は通常こちらが呼ばれる
template input*(typ: static[typedesc]; count: static[int]): untyped =
  input(typ).unpack(count)

# input(typ, [some integer].Positive) と指定しないとこちらは呼ばれない
template input*(typ: static[typedesc]; lineCount: Positive): untyped =
  (1..lineCount).mapIt(input(typ))

template input*(typ: static[typedesc]; count: static[int] = 1; lineCount: Positive): untyped =
  (1..lineCount).mapIt(input(typ, count))

macro inputs*(body: untyped): untyped =
  result = newNimNode(nnkStmtList)

  var letSection = newNimNode(nnkLetSection)

  var vars = newSeq[NimNode](body.len)
  for i, _ in vars:
    if body[i][0].len > 1: # (var1, var2, ...): int | float | string
      vars[i] = newNimNode(nnkVarTuple)
      for ident in body[i][0]:
        vars[i].add(ident)
      vars[i].add(newEmptyNode())
      vars[i].add(newNimNode(nnkCall)
                    .add(ident("input"))
                    .add(body[i][1][0])
                    .add(newLit(body[i][0].len))
                 )
    elif body[i][1][0].len == 0: # variable: int | float | string
      vars[i] = newIdentDefs(
        body[i][0],
        newEmptyNode(),
        newNimNode(nnkCall)
          .add(ident("input"))
          .add(body[i][1][0])
          .add(newLit(1))
      )
    elif body[i][1][0][0].len > 0: # variable: tuple[field1, field2, ...: T]
      var tupleIdents = newNimNode(nnkIdentDefs)
      for ident in body[i][1][0][0]:
        tupleIdents.add(ident)
      let tuplety = newNimNode(nnkTupleTy).add(tupleIdents)

      vars[i] = newIdentDefs(
        body[i][0],
        tuplety,
        newNimNode(nnkCall)
          .add(ident("input"))
          .add(body[i][1][0][0][^2])
          .add(newLit(body[i][1][0][0].len - 2))
      )
    elif body[i][1][0][0].len == 0: # seq
      if body[i][1][0].len == 2: # variable: seq[int | float | string | char]
        vars[i] = newIdentDefs(
          body[i][0],
          newEmptyNode(),
          newNimNode(nnkCall)
            .add(ident("input"))
            .add(body[i][1][0][1])
        )
      elif body[i][1][0].len == 3 and body[i][1][0][2].len == 0: # variable: seq[N, int | float | string | char]
        vars[i] = newIdentDefs(
          body[i][0],
          newEmptyNode(),
          newNimNode(nnkCall)
            .add(ident("input"))
            .add(body[i][1][0][2])
            .add(newLit(1))
            .add(body[i][1][0][1])
        )
      elif body[i][1][0][2].len == 2: # variable: seq[lineCount, seq[int | float | string | char]]
        vars[i] = newIdentDefs(
          body[i][0],
          newEmptyNode(),
          newNimNode(nnkCall)
            .add(ident("input"))
            .add(body[i][1][0][2][1])
            .add(newNimNode(nnkDotExpr)
              .add(body[i][1][0][1])
              .add(ident("Positive"))
            )
        )
      else: # variable: seq[lineCount, tuple[field1, field2, ...: T]]
        var tupleIdents = newNimNode(nnkIdentDefs)
        for ident in body[i][1][0][2][0]:
          tupleIdents.add(ident)
        let tuplety = newNimNode(nnkTupleTy).add(tupleIdents)

        vars[i] = newIdentDefs(
          body[i][0],
          newNimNode(nnkBracketExpr).add(body[i][1][0][0]).add(tuplety),
          newNimNode(nnkCall)
            .add(ident("input"))
            .add(body[i][1][0][2][0][^2])
            .add(newLit(body[i][1][0][2][0].len - 2))
            .add(body[i][1][0][1])
        )
    else:
      discard

  for `var` in vars:
    letSection.add(`var`)

  result.add(letSection)

# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
proc `//=`*(x: var SomeInteger; y: SomeInteger) = x = x div y
proc `%=`*(x: var SomeInteger; y: SomeInteger) = x = x mod y
proc `<?=`*[T](x: var T; y: T) = x = min(x, y)
proc `>?=`*[T](x: var T; y: T) = x = max(x, y)

# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
from sequtils import concat

template flatten*[T](s: seq[T]): untyped =
  when T is seq: flatten(s.concat)
  else: s
proc flatten*[T](s: seq[T]; recLevel: static[Natural]): auto =
  when recLevel == 0: s
  elif T is seq: flatten(s.concat, recLevel - 1)
  else: s

# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
proc indexed*[T](s: openArray[T]): seq[tuple[i: int, v: T]] =
  (0..s.high).mapIt((it, s[it]))

# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
template countIt*[T](a: openArray[T]; pred: untyped): int =
  var result = 0
  for it {.inject.} in items(a):
    if pred: result.inc
  result

# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
from sequtils import newSeqWith, allIt

template newSeqWithImpl[T](lens: seq[int]; init: T; currentDimension, lensLen: static[int]): auto =
  when currentDimension == lensLen:
    newSeqWith(lens[currentDimension - 1], init)
  else:
    newSeqWith(lens[currentDimension - 1], newSeqWithImpl(lens, init, currentDimension + 1, lensLen))

template newSeqWith*[T](lens: varargs[int]; init: T): untyped =
  static: assert(lens.allIt(it > 0))
  newSeqWithImpl(@lens, init, 1, lens.len)

# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
template stderrEcho*(x: varargs[string, `$`]) =
  for v in x:
    stderr.write(v)
  stderr.writeLine ""

template stderrEcho*[T](x: seq[seq[T]]) =
  for v in x: stderrEcho v

template stderrEcho*(x: seq[string]) =
  for v in x: stderrEcho v

# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
type ModComb* = ref object of RootObj
  modFacs: seq[int]
  modFacInvs: seq[int]
  MOD: int

proc modPow(n, p, m: int): int =
  if p == 0:
    1
  elif p mod 2 == 0:
    let half = modPow(n, p div 2, m)
    half * half mod m
  else:
    n * modPow(n, p - 1, m) mod m

proc newModComb*(size = 10_000_000; MOD = 1_000_000_007): ModComb =
  result = ModComb(modFacs: newSeq[int](size + 1), modFacInvs: newSeq[int](size + 1), MOD: MOD)
  result.modFacs[0] = 1
  result.modFacInvs[0] = 1

  for i in 1..size:
    result.modFacs[i] = result.modFacs[i - 1] * i mod MOD

  result.modFacInvs[size] = modPow(result.modFacs[size], MOD - 2, MOD)
  for i in countdown(size - 1, 0):
    result.modFacInvs[i] = result.modFacInvs[i + 1] * (i + 1) mod MOD

proc C*(this: ModComb; n, r: int): int =
  if r < 0 or n < r:
    0
  else:
    this.modFacs[n] * (this.modFacInvs[r] * this.modFacInvs[n - r] mod this.MOD) mod this.MOD

proc P*(this: ModComb; n, r: int): int =
  if r < 0 or n < r:
    0
  else:
    this.modFacs[n] * this.modFacInvs[n - r] mod this.MOD

proc H*(this: ModComb; n, r: int): int =
  if r == 0:
    1
  else:
    this.C(n + r - 1, r)

# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
const MOD = 1_000_000_007

inputs:
  N: int
  S: string

var facN = 1
for i in 2..N:
  facN *= i
  facN %= MOD

var
  count = 0
  derus = newSeq[bool](2 * N)
for i, c in S:
  if c == 'B':
    if count mod 2 == 0:
      derus[i] = true
      count.inc
    else:
      derus[i] = false
      count.dec
  else:
    if count mod 2 == 0:
      derus[i] = false
      count.dec
    else:
      derus[i] = true
      count.inc

if derus.countIt(it) != derus.countIt(not it):
  echo 0
  quit()

count = 0
var result = 1
for i in countdown(2*N - 1, 0):
  if derus[i]:
    result *= count
    result %= MOD
    count.dec
  else:
    count.inc

echo result * facN mod MOD

Submission status: Runtime Error

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

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

kai = [1 for _ in range(n+1)]
for i in range(1, n+1):
    kai[i] = (kai[i-1] * i) % MOD

ans = 1
count = 0
pre = ""
for i in range(2*n):
    if s[i] == pre:
        count += 1
    else:
        count += 1
        ans *= kai[count]
        ans %= MOD
        count = 0
    pre = s[i]
ans *= kai[n]
ans %= MOD
print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
S = input()
A = [i+1 for i in range(N)]
A = A + A[::-1]

B = [1]*(N)
B[1] = 2

for i in range(2,N) :
    B[i] = (i+1)
B = B + B[::-1]

ans = 1
for i,s in enumerate(S) :
    if i < N :
        if s == "B" :
            if i % 2 == 0 :
                ans *= B[i]
            else :
                if i > 0 :
                    ans *= B[i-1]
                else :
                    ans = 0
        else :
            if i % 2 != 0 :
                ans *= B[i]
            else :
                if i > 0 :
                    ans *= B[i-1]
                else :
                    ans = 0

    else :
        if s == "B" :
            if i % 2 != 0 :
                ans *= B[i]
            else :
                if i < 2*N-1 :
                    ans *= B[i+1]
                else :
                    ans = 0
        else :
            if i % 2 == 0 :
                ans *= B[i]
            else :
                if i < 2*N-1 :
                    ans *= B[i+1]
                else :
                    ans = 0
    #print(ans)
ans %= 10**9+7
print(ans)

Submission status: Runtime Error

Solution code:
n=int(input())
s=input()
count=0
now=s[0]
for i in s:
    if i!=now:
        count+=1
        now=i
ans=math.factorial(n) * math.factorial(s.count('W')) // math.factorial(count//2)
if count%2==1 or s[0]!='B' or s[-1]!='B':ans=0
print(ans%(10**9+7))

Submission status: Runtime Error

Solution code:
import math

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

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

flag = [0 for _ in range(2*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:
      flag[k] = outcounter
  else:
    if k % 2 == 1:
      outcounter += 1
    else:
      flag[k] = outcounter

counter = 0
output = math.factorial(N)
for i in range(2*N):
  k = 2 + N - i - 1
  if flag[k] != 0:
    output *= (flag[k] - counter)
    counter += 1
print(output)

Submission status: Runtime Error

Solution code:
from bisect import *
N = int(input())
S = input()

swapleft = []
swapright = []

for i in range(N):
    if S[i] == "B":
        if (i+1) % 2 == 0:
            swapright.append(i+1)
    else:
        if (i+1) % 2 == 1:
            swapright.append(i+1)

for i in range(N, 2*N):
    if S[i] == "B":
        if (i+1) % 2 == 1:
            swapleft.append(i+1)
    else:
        if (i+1) % 2 == 0:
            swapleft.append(i+1)

swapleft = set(swapleft)
swapright = set(swapright)

swapleft |= set([i for i in range(1, N+1)]) - swapright
swapright = set([i for i in range(1, 2*N+1)]) - swapleft
swapleft = list(swapleft)
swapleft.sort(reverse = True)
lmax = max(swapleft)
swapright = list(swapright)
swapright.sort()

ans = 1

for i in range(N):
    ans *= (N - bisect_left(swapright, swapleft[i]) - i)
    ans %= 1000000007


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

print(ans)

Submission status: Runtime Error

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(10000)

def count(S):
    res = 1
    cnt = 0
    for s in S:
        if s:
            cnt += 1
        else:
            res = (res*cnt)%mod
            cnt -= 1
    
    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)]
print(count(S)*frac[N]%mod)

Submission status: Runtime Error

Solution code:
from functools import lru_cache

N = int(input())
S = input()
mod = 10 ** 9 + 7
x = 0
for i in range(len(S)):
    if S[i] == 'B':
        x += 2**i

@lru_cache(maxsize=10**10)
def func(now, remain=tuple(range(2*N))):
    if len(remain) == 0:
        if now == 0:
            return 1
        else:
            return 0
        
    ret = 0
    for i in range(len(remain)):
        for j in range(i+1, len(remain)):
            temp = list(remain)
            temp.pop(j)
            temp.pop(i)
            ret += func(now ^ ((2**(remain[j]+1)-1)-(2**remain[i]-1)), tuple(temp))
            ret %= mod
    return ret

print(func(x) % mod)

Submission status: Runtime Error

Solution code:
from math import factorial
iMOD = 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)