Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

N = int(input())
ans = float("inf")


def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors


for i in make_divisors(N):
    for j in make_divisors(N):
        if i * j == N:
            x = i - 1
            y = j - 1

            ans = min(ans, (i-1)+(j-1))
print(ans)


### FIXED CODE ###

N = int(input())


def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    # divisors.sort()
    return divisors


div = make_divisors(N)

if div[-1] ** 2 == N:
    print(div[-1]*2 - 2)

else:
    x = div[-2] - 1
    y = div[-1] - 1

    print(x + y)
### BUGGY CODE ###

import math
import sys

X,Y,Z,K=map(int,input().split())

x=sorted(list(map(int,input().split())),reverse=True)
y=sorted(list(map(int,input().split())),reverse=True)
z=sorted(list(map(int,input().split())),reverse=True)



"""
if X*Y*Z<=3000:
    ans=[]
    for i in range(X):
        for j in range(Y):
            for k in range(Z):  ans.append(x[i]+y[j]+z[k])
    ans.sort()
    for i in range(min(3000,X*Y*Z)):
        print(ans[i])
    sys.exit()
"""

yz=[]
for i in range(Y):
    yz=sorted(yz+[ y[i]+z[j] for j in range(Z)],reverse=True)

if len(yz)>3000:
    yz=yz[:3000]


n=len(yz)
ans=[]

for i in range(X):
    tmp=[yz[j]+x[i] for j in range(len(yz))]
    ans =sorted(ans+tmp,reverse=True)


for i in range(K):
    print(ans[i])

### FIXED CODE ###

import math
import sys

X,Y,Z,K=map(int,input().split())

x=sorted(list(map(int,input().split())),reverse=True)
y=sorted(list(map(int,input().split())),reverse=True)
z=sorted(list(map(int,input().split())),reverse=True)



"""
if X*Y*Z<=3000:
    ans=[]
    for i in range(X):
        for j in range(Y):
            for k in range(Z):  ans.append(x[i]+y[j]+z[k])
    ans.sort()
    for i in range(min(3000,X*Y*Z)):
        print(ans[i])
    sys.exit()
"""

ans=[]
for i in range(min(X,K)):
    tmp1=math.ceil(K/(i+1))
    for j in range(min(Y,tmp1)):
        tmp2=math.ceil(tmp1/(j+1))
        for k in range(min(Z,tmp2)):
            ans.append(x[i]+y[j]+z[k])

ans.sort(reverse=True)
for i in range(K):
    print(ans[i])
### BUGGY CODE ###

# coding: utf-8
n = int(input())
ans = 0

def divisor(n):
    i = 1
    table = []
    while i * i <= n:
        if n%i == 0:
            table.append(i)
            table.append(n//i)
        i += 1
    table = list(set(table))
    return table

for i in range(n):
    ans = ans + (1 + i) * len(divisor(i + 1))
print(ans)


### FIXED CODE ###

# coding: utf-8
n_input = int(input())
ans = 0
for i in range(1, n_input + 1):
    n = n_input // i
    ans += n * (1 + n) * i // 2
print(ans)
### BUGGY CODE ###

h, n = map(int, input().split())

a = [0] * n
b = [0] * n

for i in range(n):
    a[i], b[i] = map(int, input().split())

magic = [float("inf")] * (h + 1)
magic[0] = 0

for i in range(n):
    for j in range(0, h + 1):
        if j + a[i] <= h:
            magic[j + a[i]] = min(magic[j + a[i]], magic[j] + b[i])
        else:
            magic[h] = min(magic[h], magic[j] + b[i])

print(magic[h])

### FIXED CODE ###

h, n = map(int, input().split())

a = [0] * n
b = [0] * n

for i in range(n):
    a[i], b[i] = map(int, input().split())

magic = [float("inf")] * (h + 1)
magic[0] = 0

for i in range(n):
    for j in range(0, h + 1):
        if j + a[i] <= h:
            magic[j + a[i]] = min(magic[j + a[i]], magic[j] + b[i])
        else:
            magic[h] = min(magic[h], magic[j] + b[i])

print(magic[h])
### BUGGY CODE ###

n,k,q=map(int,input().split())

a=[]
for i in range(q):
    
    a.append(int(input()))
             
for i in range(1,n+1):
    
             
             
    if q-a.count(i)<k:
        print("Yes")
    else:
        print("No")
        


### FIXED CODE ###

n,k,q=map(int,input().split())
a=[0 for i in range(n+1)]
for i in range(q):
    a[int(input())]+=1
for i in range(1,n+1):
    if q-a[i]<k:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

import sys
import copy
import math
import itertools
#import numpy as np
import re

N = int(input())
A = [int(input()) for c in range(N)]
ans = []
cnt=0
for i in range(N):
    if ans.count(A[i])%2==0:
        cnt+=1
    else:
        cnt-=1
    ans.append(A[i])


print(cnt)

### FIXED CODE ###

N = int(input())
A = [int(input()) for c in range(N)]
A = sorted(A)

tmp = 1
cnt = 0
for i in range(N):    
    if i+1<N:
        if A[i] == A[i+1]:
            tmp += 1
        else:
            cnt += tmp%2
            tmp = 1
    else:
        cnt += tmp%2

print(cnt)
### BUGGY CODE ###

import sys
def main():
    input = sys.stdin.readline
    N = int(input())
    S = [list(input().rstrip()) for _ in range(N)]

    uf = UnionFindTree(N*2)
    for i in range(N):
        for j in range(i+1,N):
            if S[i][j] == '1':
                uf.union(i, j+N)
                uf.union(i+N, j)
    
    for i in range(N):
        if uf.same(i, i+N):
            print(-1)
            exit()

    D = [[10**9] * N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            if i == j: D[i][j] = 0
            elif S[i][j] == '1': D[i][j] = 1

    for k in range(N):
        for i in range(N):
            for j in range(N):
                D[i][j] = min(D[i][j], D[i][k] + D[k][j])
    d_max = max(max(s) for s in D)
    print(d_max+1)

class UnionFindTree:
    def __init__(self, n):
        self.parent = [-1] * n

    def find(self, x):
        p = self.parent
        while p[x] >= 0: x, p[x] = p[x], p[p[x]]
        return x

    def union(self, x, y):
        x, y, p = self.find(x), self.find(y), self.parent
        if x == y: return
        if p[x] > p[y]: x, y = y, x
        p[x], p[y] = p[x] + p[y], x

    def same(self, x, y): return self.find(x) == self.find(y)
    def size(self, x): return -self.parent[self.find(x)]

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
def main():
    input = sys.stdin.readline
    N = int(input())
    S = [list(input().rstrip()) for _ in range(N)]

    uf = UnionFindTree(N*2)
    for i in range(N):
        for j in range(i+1,N):
            if S[i][j] == '1':
                uf.union(i, j+N)
                uf.union(i+N, j)
    
    for i in range(N):
        if uf.same(i, i+N):
            print(-1)
            exit()

    D = [[10**9] * N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            if i == j: D[i][j] = 0
            elif S[i][j] == '1': D[i][j] = 1

    for k in range(N):
        for i in range(N):
            for j in range(N):
                D[i][j] = min(D[i][j], D[i][k] + D[k][j])
    d_max = max(max(s) for s in D)
    print(d_max+1)

class UnionFindTree:
    def __init__(self, n):
        self.parent = [-1] * n

    def find(self, x):
        p = self.parent
        while p[x] >= 0: x, p[x] = p[x], p[p[x]]
        return x

    def union(self, x, y):
        x, y, p = self.find(x), self.find(y), self.parent
        if x == y: return
        if p[x] > p[y]: x, y = y, x
        p[x], p[y] = p[x] + p[y], x

    def same(self, x, y): return self.find(x) == self.find(y)
    def size(self, x): return -self.parent[self.find(x)]

if __name__ == '__main__':
    main()
### BUGGY CODE ###

n = int(input())
s = [input() for i in range(n)]
l = set(s)
l = list(sorted(l))
ans = 0
ans_l = []
for i in l:
    if s.count(i) > ans:
      ans_l = [i]
      ans = s.count(i)
    elif s.count(i) == ans:
      ans_l.append(i)
print("\n".join(ans_l))

### FIXED CODE ###

from collections import Counter

n = int(input())
S = [input() for i in range(n)]

s = Counter(S)
max_cnt = max(s.values())
names = [name for name, cnt in s.items() if cnt == max_cnt]
names.sort()

print("\n".join(names))
### BUGGY CODE ###

def main():
    D = int(input())
    c_list = list(map(int, input().split()))
    s_list = [list(map(int, input().split())) for _ in range(D)]
    t_list = [int(input()) for _ in range(D)]

    #res_list = []
    M = int(input())
    for m in range(M):
        d,q = map(int, input().split())
        t_list[d-1] = q
        res = 0
        
        last_open = [0] * 26
        for i in range(D):
            t = t_list[i]
            res += s_list[i][t-1]

            # TODO: ここは毎回26ループ回す必要がないところになりうるので改善可能かも(なおすだけで20回分の処理が消せる)
            bad = 0
            last_open[t-1] = i+1
            for ci in range(26):
                bad += c_list[ci]*(i+1 - last_open[ci])

            res -= bad

        print(res)

if __name__ == "__main__":
    main()

### FIXED CODE ###


def main():
    D = int(input())
    c_list = list(map(int, input().split()))
    s_list = [list(map(int, input().split())) for _ in range(D)]
    t_list = [int(input()) for _ in range(D)]

    basic_bad = sum(c_list)
    #res_list = []
    M = int(input())
    for m in range(M):
        d,q = map(int, input().split())
        t_list[d-1] = q
        res = 0
        
        bad = 0
        last_open = [0] * 26
        for i in range(D):
            t = t_list[i]
            res += s_list[i][t-1]

            # TODO: ここは毎回26ループ回す必要がないところになりうるので改善可能かも(なおすだけで20回分の処理が消せる)
            # bad = 0
            # for ci in range(26):
            #     bad += c_list[ci]*(i+1 - last_open[ci])
            bad += basic_bad - (i+1 - last_open[t-1]) * c_list[t-1]
            last_open[t-1] = i+1

            res -= bad

        print(res)

if __name__ == "__main__":
    main()
### BUGGY CODE ###

#!/usr/bin/env python3

import math
def gcd(x, y):
    while y != 0:
        x, y = y, x % y
    return x

def fact(n):
    r = [1]
    if n % 2 == 0:
        r.append(2)
    while n % 2 == 0:
        n = n // 2
    i = 3
    while i < n:
        if n % i == 0:
            r.append(i)
        while n % i == 0:
            n = n // i
        i += 2
    if n not in r:
        r.append(n)
    return r

def main():
    A, B = map(int, input().split())
    cf = []
    t = gcd(A, B)
    if t % 2 == 0:
        cf.append(2)
    print(len(fact(t)))


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3

import math
def gcd(x, y):
    while y > 0:
        x, y = y, x % y
    return x

def fact(n):
    r = [1]
    if n % 2 == 0:
        r.append(2)
        while n % 2 == 0:
            n //= 2
    i = 3
    k = int(math.sqrt(n))
    while i <= k:
        if n % i == 0:
            r.append(i)
            while n % i == 0:
                n //= i
            k = int(math.sqrt(n))
        i += 2
    if n > 1:
        r.append(n)
    return r

def main():
    A, B = map(int, input().split())
    t = gcd(A, B)
    print(len(fact(t)))


if __name__ == '__main__':
    main()
### BUGGY CODE ###

import sys
N = int(input())
A = [int(i) for i in input().split()]
B = list(set(A))
B.sort(reverse=True)
ls = []
for x in B:
    num = A.count(x)
    if num >= 2:
        ls.append(x)
        if len(ls) == 2:
            break
        if num >= 4:
            print(x**2)
            sys.exit()
if len(ls) == 2:
    print(ls[0]*ls[1])
else:
    print(0)

### FIXED CODE ###

from collections import defaultdict
N = int(input())
A = [int(i) for i in input().split()]
A.sort(reverse=True)
d = defaultdict(int)
ls = []
for x in A:
    d[x] += 1
    if d[x] == 2:
        ls.append(x)
        if len(ls) == 2:
            break
    elif d[x] == 4:
        ls.append(x)
        break
if len(ls) == 2:
    print(ls[0]*ls[1])
else:
    print(0)
### BUGGY CODE ###

import math

N,K = map(int, input().split())
A = list(map(int, input().split()))
epsilon = 10**(-9)
#A = [a-epsilon for a in A]

_min = 0
_max = max(A)

while _max - _min > epsilon:
  new = (_min+_max)/2
  if _min < int(new):
    new = int(new)
  times = sum([math.ceil(a/new)-1 for a in A])
  #print(_min, new, _max, times, [math.ceil(a/new)-1 for a in A])
  
  if times <= K:
    _max = new
  else:
    _min = new
  #print(_min, _max)

if  sum([math.ceil(a/_max)-1 for a in A]) <= K:
  print(math.ceil(_max))
else:
  print(math.ceil(_min))

### FIXED CODE ###

import math

N,K = map(int, input().split())
A = list(map(int, input().split()))
epsilon = 10**(-5)
#A = [a-epsilon for a in A]

_min = 0
_max = max(A)

while _max - _min > epsilon:
  new = (_min+_max)/2
  if _min < int(new):
    new = int(new)
  times = sum([math.ceil(a/new)-1 for a in A])
  #print(_min, new, _max, times, [math.ceil(a/new)-1 for a in A])
  
  if times <= K:
    _max = new
  else:
    _min = new
  #print(_min, _max)

if  sum([math.ceil(a/_max)-1 for a in A]) <= K:
  print(math.ceil(_max))
else:
  print(math.ceil(_min))
### BUGGY CODE ###

N, M, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

# print(N, M, K)
# print(A)
# print(B)

def cuml(li):
    rlis = [0]

    for i in range(len(li)):
        rlis.append(rlis[-1] + li[i])

    return rlis


A_cuml = cuml(A)
B_cuml = cuml(B)

res = 0

for a in range(len(A_cuml)):
    if A_cuml[a] > K:
        break
    for b in range(len(B_cuml)):
        if A_cuml[a] + B_cuml[b] > K:
            break
        
        res = max(res, a + b)

print(res)

### FIXED CODE ###

import bisect

N, M, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

# print(N, M, K)
# print(A)
# print(B)

def cuml(li):
    rlis = [0]

    for i in range(len(li)):
        rlis.append(rlis[-1] + li[i])

    return rlis


A_cuml = cuml(A)
B_cuml = cuml(B)

res = 0

for a in range(len(A_cuml)):
    rest = K - A_cuml[a]
    if rest < 0:
        break
    # for b in range(len(B_cuml)):
    #     if A_cuml[a] + B_cuml[b] > K:
    #         break

    # bisect search
    b = bisect.bisect_right(B_cuml, K - A_cuml[a])

    res = max(res, a + b - 1)

print(res)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
def solve():
    N = int(input())
    A = dict()
    for a in map(int, input().split()):
        A[a] = A.get(a,0) + 1
    a = list(A)[0]
    if A[a] == 1:
        A.pop(a)
    else:
        A[a] -= 1

    for b in A:
        B = A.copy()
        c_, c = a, b
        while c in B:
            if B[c] == 1:
                B.pop(c)
            else:
                B[c] -= 1
            c_, c = c, c_^c
        if B == dict() and c == a:
            return 'Yes'
    return 'No'
if __name__ == '__main__':
    print(solve())

### FIXED CODE ###

# -*- coding: utf-8 -*-
def solve():
    N = int(input())
    A = dict()
    for a in map(int, input().split()):
        A[a] = A.get(a,0) + 1
    if N % 3:
        if 0 in A and A[0] == N:
            return 'Yes'
        else:
            return 'No'
    else:
        if 0 in A and A[0] == N:
            return 'Yes'
        elif 0 in A and A[0] == N//3:
            if len(A) == 2:
                return 'Yes'
            else:
                return 'No'
        elif len(A) == 3:
            if len(set(A.values())) == 1:
                a,b,c = A.keys()
                if c == a^b:
                    return 'Yes'
                else:
                    return 'No'
            else:
                return 'No'
        else:
            return 'No'

if __name__ == '__main__':
    print(solve())
### BUGGY CODE ###

def main():
    import fractions
    import sys
    input = sys.stdin.readline
    N = int(input())
    a = list(map(int,input().split()))
    MOD = 10**9+7
    g1 = 1
    for t in a[:N//2]:
        g1 = divmod(g1*t,fractions.gcd(g1,t))[0]

    g2 = 1
    for t in a[N//2:]:
        g2 = divmod(g2*t,fractions.gcd(g2,t))[0]
    res = 0
    g = fractions.gcd(g1,g2)

    r1 = (g2//g)%MOD
    for t in a[:N//2]:
        res += divmod(g1,t)[0]%MOD
    res = res*r1%MOD

    res2 = 0
    r2 = (g1//g)%MOD
    for t in a[N//2:]:
        res2 += divmod(g2,t)[0]%MOD
    res2 = res2*r2%MOD
    print((res+res2)%MOD)
if __name__ == '__main__':
    main()


### FIXED CODE ###

import fractions
import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int,input().split()))
g = 1
res = 0
MOD = 10**9+7
for elem in a:
    tmp = g*elem//fractions.gcd(g,elem)
    res *= tmp//g
    g = tmp
    res += g//elem
print(res%MOD)
### BUGGY CODE ###

n,a,b=map(int,input().split())
count=0

if a==0:
  print('0')
  exit()
else:
  while n>=a:
    n=n-a
    count+=1
    if n>=b:
      n=n-b
    elif n<b:
      n=0
      

ball=a*count+n

print(ball)

### FIXED CODE ###

n,a,b=map(int,input().split())

kosuu=n//(a+b)
amari=n%(a+b)

if a>amari:
  print(a*kosuu+amari)
else:
  print(a*kosuu+a)
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
ans=sum(A)
s=N+1
j=s

for i in range(100000):
    if  A==sorted(A):
        break
    x=max(A[:s])
    s=A.index(x)
    A[s:j]=[x]*len(A[s:j])
    j=s

print(sum(A)-ans)

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
ans=sum(A)

for i in range(1,N):
    if A[i-1] > A[i]:
        A[i]=A[i-1]

print(sum(A)-ans)
### BUGGY CODE ###

import collections
import math


def combinations_count(n, r):
    return (n*(n-1)//2)
    # return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


N = int(input())
A = list(map(int, input().split()))
Ay = list(set(A))
c = collections.Counter(A)
cnt = 0
ansx = []
ansy = []
ansy2 = []


for x, y in c.items():
    ansy.append(combinations_count(y, 2))
    ansy2.append(y-1)
    ansx.append(x)
sumall = sum(ansy)

for i in A:
    print(sumall - ansy2[ansx.index(i)])


### FIXED CODE ###

import collections
import math

N = int(input())
A = list(map(int, input().split()))
c = collections.Counter(A)
cnt = 0


sumall = 0
for x, y in c.items():
    sumall += (y*(y-1)//2)

for i in range(N):
    print(sumall - c[A[i]] + 1)
### BUGGY CODE ###

N = int(input())
ans = 1
A = list(map(int, input().split()))

for i in range(N):
  ans = ans * A[i]
  if ans == 0:
    break

if ans > 10 ** 18:
  print('-1')
else:
  print(ans)

### FIXED CODE ###

N = int(input())
ans = 1
A = list(map(int, input().split()))
flag = 0

for j in range(len(A)):
  if A[j] == 0:
    flag = 1
    ans = 0

if flag == 0:
  for i in range(N):
    ans = ans * A[i]
    if ans > 10 ** 18:
      break


if ans > 10 ** 18:
  print('-1')
else:
  print(ans)
### BUGGY CODE ###

import collections
n,k = map(int, raw_input().split(' '))
ais = map(int ,raw_input().split(' '))
prev = ais
for _ in range(k):

	segments = []
	for i,d in enumerate(ais):
		u = i+1
		segments.append([u-d, u+d])

	for u in range(1, n+1):
		ais[u-1] = 0
		for uu,vv in segments:
			if uu <= u <=vv:
				ais[u-1] += 1
for e in ais:print e,


### FIXED CODE ###

import collections
n,k = map(int, raw_input().split(' '))
ais = map(int ,raw_input().split(' '))

prev = ais[::]
for _ in range(k):

	h = collections.Counter()
	for i,d in enumerate(ais):
		u = i+1
		h[max(1, u - d)] += 1
		h[u + d + 1] -= 1

	cumul = 0
	for u in range(1, n+1):
		cumul += h[u]
		ais[u - 1] = cumul
	if prev == ais[::]:
		break
	prev = ais[::]


for e in ais:print e,
### BUGGY CODE ###

import sys
import numpy as np


class Square:
    def __init__(self, num, x, y):
        self.num = num
        self.x = x
        self.y = y
        self.adj = {self.num: 0}

    def merge(self, other):
        dist = abs(self.x - other.x) + abs(self.y - other.y)
        for k, m in other.adj.items():
            self.adj[k] = dist + m


def main():
    h, w, d = [int(x) for x in input().split()]
    dic = {}
    for i in range(h):
        line = [int(x) for x in input().split()]
        for j, a in enumerate(line):
            dic[a] = Square(a, i, j)
    for a in range(h*w, 0, -1):
        if a + d <= h*w:
            dic[a].merge(dic[a+d])
    q = int(input())
    for k in range(q):
        l, r = [int(x) for x in input().split()]
        print(dic[l].adj[r])


main()


### FIXED CODE ###

import sys
import numpy as np


def main():
    h, w, d = [int(x) for x in input().split()]
    dic = {}
    for i in range(h):
        line = [int(x) for x in input().split()]
        for j, a in enumerate(line):
            dic[a] = (a, i, j)
    magic = [[0] for _ in range(d + 1)]
    for k in range(1, d + 1):
        for m in range(1, h * w):
            if k + (m * d) > h * w:
                break
            magic[k].append(magic[k][m - 1] +
                            abs(dic[k + (m * d)][1] - dic[k + ((m - 1) * d)][1]) +
                            abs(dic[k + (m * d)][2] - dic[k + ((m - 1) * d)][2]))
    q = int(input())
    for _ in range(q):
        l, r = [int(e) for e in input().split()]
        k = d if l % d == 0 else l % d
        print(magic[k][(r - 1) // d] - magic[k][(l - 1) // d])


main()
### BUGGY CODE ###

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

ok = 0
ng = N // 2 + 1

while ng - ok > 1:
    m = (ok + ng) // 2
    if any(S[i : i + m] in S[i + m :] for i in range(N - 2 * m + 1)):
        ok = m
    else:
        ng = m

print(ok)

### FIXED CODE ###

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

dp = [[0 for _ in range(N)] for _ in range(N)]

ans = 0
for i in range(N):
    for j in range(i + 1, N):
        if S[i] == S[j]:
            tmp = 1
            if i > 0:
                tmp += dp[i - 1][j - 1]
            if j - i < tmp:
                continue
            dp[i][j] = tmp
        ans = max(ans, dp[i][j])
print(ans)
### BUGGY CODE ###

N = int(input())
o_lst=[]
lst = list(map(int, input().split()))
for i in lst:
    idx = lst.index(min(lst))
    print(idx+1,end=" ")
    #o_lst.append(idx+1)
    lst[idx]=N+1

### FIXED CODE ###

N = int(input())
lst = list(map(int, input().split()))
a = [0]*N
for i,j in enumerate(lst):
    a[j-1] = str(i+1)

print(" ".join(a))
### BUGGY 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)

### FIXED 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
        ans %= mod
        L -= 1

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