Harryxun/stf_run huggingface dataset:
A = input()
B = input()
C = input()

def next(X, i):
    if X[i] == 'a':
        return A[i+1]
    elif X[i] == 'b':
        return B[i+1]
    else:
        return C[i+1]

xa = 0
xb = 0
xc = 0

k = next(A, xa)
xa += 1

while xa < len(A)-1 and xb < len(B)-1 and xc < len(C)-1:
    if k == 'a':
        k = next(A, xa)
        xa += 1
    elif k == 'b':
        k = next(B, xb)
        xb += 1
    else:
        k = next(C, xc)
        xc += 1

print(str.upper(k))


### FIXED CODE ###

#【註】入力受け取り部分 …… そのまま用いています。
A = input()
B = input()
C = input()

#【註】現在 A, B, C がカードを何枚目まで切っているかを示す変数 …… そのまま用いています。
xa = 0
xb = 0
xc = 0

#【註】関数 next は、単純に A[xa] や B[xb] および C[xc] を用いることで
# 複雑な処理を行うことなく次の手番が誰になるかを確認できるため、今回の
# 解答となるコードからは削除しました。

#【註】最初の A の手番の処理
h = 'A'
k = A[xa] #【註】 next 関数を削除し、A[xa] を用いて A の 0 枚目のカードを参照するように変更しました。
xa += 1

#【註】このゲームの勝敗が決まるタイミングに着目します。
# このゲームは、「場に出たカードに書かれているプレイヤー」のカードが
# 残り 0 枚だったとき、そのプレイヤーが勝利するようになっています。
# そのため、ループ構造は「カードを場に出す」→「もしもそのプレイヤーが勝つならループを抜ける、そうでなければ
# 次のカードを場に出させる（ループを続ける）」という形になるのが適切です。
# カードを場に出した際にループが続くか・ループから抜けるかが決まるため、while 文は
# 条件式を True とし、ループから抜ける処理が走るまでループさせ続けるとよいでしょう。
while True:

    #【註】場に出たカードに書かれている文字（ k ）に注目 … この if 文の構造はそのまま用いています。
    if k == 'a':
        h = 'A'  #【註】h（誰の手番になったのか）を更新 …… そのまま用いています。

        #【註】もし次に参照するべきカードの順番：xa がカードの枚数：len(A) より小さければ、
        # A に 1 枚カードを出させる（k に A[xa] を代入し、xa に 1 を足す）処理をします。
        if xa < len(A): 
            k = A[xa]
            xa += 1
        #【註】そうでなければ、A はもうカードを持っていないことになりますから、このループを抜けることができます。
        else:
            break

    elif k == 'b':
        h = 'B'
        xb += 1
        if xb < len(B):
            k = B[xb]
            xb += 1
        else:
            break
    else:
        h = 'C'
        xc += 1
        if xc < len(C):
            k = C[xc]
            xc += 1
        else:
            break

print(h)
a,b=map(int,input().split())
print(a*b//2)

### FIXED CODE ###

a,b,c=map(int,input().split())
print(a*b//2)
import math
a,b=[int(i) for i in input().split()]
def lcm(x,y):
    return int((x*y) / math.gcd(x,y))

  
  
m=lcm(a,b) 
print(m)

### FIXED CODE ###

A, B=[int(i) for i in input().split()]

def gcd(a, b):
	while b:
		a, b = b, a % b
	return a
def lcm(a, b):
	return a * b // gcd (a, b)
  
print(lcm(A,B))
import sys
sys.setrecursionlimit(10**7)
mo=10**9+7

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

def P(n,k,mo):
    rt=1
    for i in range(k):
        rt*=(n-i)
        rt%=mo
    return rt

g=[[] for i in range(1+n)]
v=[0]*(1+n)
for i in range(n-1):
    a,b=map(int,input().split())
    g[a].append(b)
    g[b].append(a)

def dfs(cur):
    c=len(g[c])-1 #sum([v[i]!=1 for i in g[cur]])
    if c==0:
        return
    v[cur]=1
    ans[0]*=P(k-2,c,mo)
    for nb in g[cur]:
        if v[nb]!=1:
            dfs(nb)
v[1]=1
ans=[P(k,1+len(g[1]),mo)]

for j in g[1]:
    c=sum([v[i]!=1 for i in g[j]])
    ans*=P(k-2,c,mo)
    dfs(j)
print(ans[0]%mo)


### FIXED CODE ###

mo=10**9+7
n,k=map(int,input().split())

def P(n,k,mo):
    rt=1
    for i in range(k):
        rt*=(n-i)
        rt%=mo
    return rt

g=[[] for i in range(1+n)]
v=[0]*(1+n)

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

def dfs(cur):
    q=[]
    q.append(cur)

    while q:
        cur=q.pop()
        v[cur]=1
        c=len(g[cur])-1
        ans[0]*=P(k-2,c,mo)
        
        for nb in g[cur]:
            if v[nb]!=1:
                q.append(nb)
v[1]=1
ans=[P(k,1+len(g[1]),mo)]

for j in g[1]:
    dfs(j)
print(ans[0]%mo)
a ,b = map(int, input().split()) 
print(int(a*b))

### FIXED CODE ###

from math import floor
from fractions import Fraction
a, b = input().split()
a = int(a)
b = Fraction(b)
print(floor(a * b))
N,A,B=map(int,input().split())
s = input().rstrip()
count = 0
countB = 0
for i in range(N):
  if A+B <= count:
    print('No')
  else:
    if s[i] == 'a':
      print('Yes')
      count += 1
    elif s[i] =='b'"
      if countB <= B:
        print('Yes')
        countB += 1
        count += 1
      else:
        print('No')
    else:
      print('No')

### FIXED CODE ###

N,A,B=map(int,input().split())
s = input().rstrip()
count = 0
countB = 0
for i in range(N):
  if A+B <= count:
    print('No')
  else:
    if s[i] == 'a':
      print('Yes')
      count += 1
    elif s[i] =='b':
      if countB < B:
        print('Yes')
        countB += 1
        count += 1
      else:
        print('No')
    else:
      print('No')
N = int(input())
S = list(map(int, input().split()))
S = S[::-1]
S.append(S[-1])

for i in range(1, N):
    if S[i] <= S[i-1]:
        cnt += S[i]
    else:
        cnt += S[i-1]
        S[i] = S[i-1]

print(sum(S))



### FIXED CODE ###

N = int(input())
S = list(map(int, input().split()))
S = [10**5+1] + S + [10**5+1]
ans = []
for i in range(1, N+1):
    ans.append(min(S[i-1], S[i]))
print(sum(ans))
N, M = map(int, input().split())
A = [input() for _ in range(N)]
B = [input() for _ in range(M)]

for i in range(N - M + 1):
  for j in range(N - M + 1):
    ok = True
    if A[i + j][j:j + M] != B[k]:
      ok = False
      break
    if ok:
      print("Yes")
      exit()
print("No")

### FIXED CODE ###

N, M = map(int, input().split())
A = [input() for _ in range(N)]
B = [input() for _ in range(M)]
ans = "No"

for i in range(N - M + 1):
  for j in range(N - M + 1):
    if [a[j:j+M] for a in A[i:i+M]] == B:
      ans = "Yes"
print(ans)
r = int(input().split)
print("%.5f %.5f" %(r**2*3.14, 2*r*3.14))


### FIXED CODE ###

#
# 4b
#
import math


def main():
    r = float(input())
    S = r * r * math.pi
    L = 2 * r * math.pi
    print(f"{S:.6f} {L:.6f}")


if __name__ == '__main__':
    main()
from collections import deque

H, W = map(int, input().split())
B = deque()
check = [[False for _ in range(W)] for _ in range(H)]
for h in range(H):
    a = input()
    if a.count("#") > 0:
        b = [(h, w) for w, e in enumerate(a) if e == "#"]
        B += b
for bx, by in B:
    check[bx][by] = 0

move = [(1, 0), (-1, 0), (0, 1), (0, -1)]

while B:
    x, y = B.pop()
    for dx, dy in move:
        nx, ny = x + dx, y + dy
        if -1 < nx < H and -1 < ny < W:
            if check[nx][ny] == False:
                lx, ly = nx, ny
                check[nx][ny] = check[x][y] + 1
                B.appendleft((nx, ny))
print(check[lx][ly])

### FIXED CODE ###

from collections import deque

H, W = map(int, input().split())
B = deque()
check = [[H*W for _ in range(W)] for _ in range(H)]
for h in range(H):
    a = input()
    if a.count("#") > 0:
        b = [(h, w) for w, e in enumerate(a) if e == "#"]
        B += b
        for bx, bw in b:
            check[bx][bw] = 0

move = [(1, 0), (-1, 0), (0, 1), (0, -1)]

while B:
    x, y = B.pop()
    for dx, dy in move:
        nx, ny = x + dx, y + dy
        if -1 < nx < H and -1 < ny < W:
            if check[nx][ny] > check[x][y] + 1:
                check[nx][ny] = check[x][y] + 1
                B.appendleft((nx, ny))
print(max(max(c) for c in check))
import sys
sys.setrecursionlimit(10 ** 9)

n = int(input())
x = input()

p = [-1 for _ in range(2*(10**7)+1)]
cnt = x.count('1')

def calc(a):
  #print('a=',a)
  if p[a] != -1:
    return p[a]
  else:
    if a == 0:
      ret = 0
    else:
      b = bin(a).count('1')
      ret = 1+calc(a%b)
    p[a] = ret
    return ret

x0 = int(x,2)%(cnt-1)
x1 = int(x,2)%(cnt+1)
xx0 = [1]
for i in range(n+1):
  xx0.append((xx0[-1]*2)%(cnt-1))
xx1 = [1]
for i in range(n+1):
  xx1.append((xx1[-1]*2)%(cnt+1))

y = list(x)  
for i in range(n):
  if y[i] == '0':
    xx = xx1[n-i-1]
    print(calc((x1+xx)%(cnt+1))+1)
  else:
    xx = xx0[n-i-1]
    print(calc((x0-xx)%(cnt-1))+1)
  

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 9)

n = int(input())
x = input()

p = [-1 for _ in range(2*(10**7)+1)]
cnt = x.count('1')

def calc(a):
  #print('a=',a)
  if 0 <= a <= 2*(10**7) and  p[a] != -1:
    return p[a]
  else:
    if a == 0:
      ret = 0
    else:
      b = bin(a).count('1')
      ret = 1+calc(a%b)
    if 0 <= a <= 2*(10**7):
      p[a] = ret
    return ret

if cnt > 1:
  x0 = int(x,2)%(cnt-1)
  xx0 = [1]
  for i in range(n+1):
    xx0.append((xx0[-1]*2)%(cnt-1))
x1 = int(x,2)%(cnt+1)
xx1 = [1]
for i in range(n+1):
  xx1.append((xx1[-1]*2)%(cnt+1))

y = list(x)  
for i in range(n):
  if y[i] == '0':
    xx = xx1[n-i-1]
    print(calc((x1+xx)%(cnt+1))+1)
  else:
    if cnt == 1:
      print(0)
    else:
      xx = xx0[n-i-1]
      print(calc((x0-xx)%(cnt-1))+1)
import numpy as np
N,K = (int(i) for i in input().split())  
AB = [[int(i) for i in input().split()] for i in range(N-1)] 

j = 0
point = AB[0][0]
answer = K

d = []

count = 1
for i in range(len(AB)):
    if point in AB[j]:
        AB[j].pop(AB[j].index(point))
        d.append([AB[j][0], count])
        AB.pop(j)
        count += 1
    else:
        j += 1
point = d[0][0]
answer = answer * (K-d[0][1]) % (int(10**9)+7)
d.pop(0)

while len(AB) > 0 and stop:
    j = 0
    count = 2
    for i in range(len(AB)):
        if point in AB[j]:
            AB[j].pop(AB[j].index(point))
            d.append([AB[j][0], count])
            AB.pop(j)
            count += 1
        else:
            j += 1
        stop += 1
    point = d[0][0]
    answer = answer * (K-d[0][1]) % (int(10**9)+7)
    d.pop(0)
print(answer)

### FIXED CODE ###

import numpy as np
from collections import deque

N,K = (int(i) for i in input().split())  
AB = [[int(i) for i in input().split()] for i in range(N-1)] 

Tree = [[] for _ in range(N+1)]
d = deque()

for i in range(N-1):
    a, b = AB[i]
    Tree[a].append(b)
    Tree[b].append(a)

answer = K

for i in range(len(Tree[1])):
    answer = (answer * (K - 1 - i))%(int(10**9)+7)
    d.append([1, Tree[1][i]])

Tree[1] = []

while d != deque():
    for i in range(len(d)):
        parent, child = d[0]
        Tree[child].pop(Tree[child].index(parent))
        for j in range(len(Tree[child])):
            d.append([child, Tree[child][j]])
            answer = (answer * (K - 2 - j))%(int(10**9)+7)
        d.popleft()
print(answer)
S = input().split()
if S[0] - S[1] <= 0:
  print('0')
else:
  print(S[0] - S[1])


### FIXED CODE ###

l = list(map(int, input().split()))
if l[0] - l[1] <= 0:
  print('0')
else:
  print(l[0] - l[1])
ans=0
runrun = 0
i =0
while runrun = K:
    if i < 10:
        runrun +=1
    else:
        a = list(map(int,str(i)))
        for j in range(1,len(a)):
            tmp = 0
            if abs(a[j]-a[j-1])<=1:
                tmp +=1
        if tmp == len(a)-1:
            runrun +=1
            ans = i
    i +=1
print(ans)

                


### FIXED CODE ###

k=int(input())
cand=[[1,2,3,4,5,6,7,8,9]]
for _ in range(9): #上記の操作を9回繰り返せば10^5個以上のルンルン数を列挙できる
 tmp=[]
 for val in cand[-1]:
   if val%10!=0: #末尾が0のときは(末尾-1)を付け加えた数はルンルン数にならない
     tmp.append(val*10+(val%10-1))
   tmp.append(val*10+(val%10))
   if val%10!=9: #末尾が9のときは(末尾+1)を付け加えた数はルンルン数にならない
     tmp.append(val*10+(val%10+1))
 cand.append(tmp)
ans=[]
for i in range(len(cand)):
 for val in cand[i]:
   ans.append(val)
ans=sorted(ans)
print(ans[k-1])
N = int(input())
a = list(map(int, input().split(' ')[:-1]))
b = [0 for _ in range(N)]

a.insert(0, 0)
b.insert(0, 0)

n = int(N/2)

for i in range(N, 0, -1):
    nums = 0

    for ii in range(2, int(N/i)):
        nums += b[i*ii - 1]

    if nums % 2 != a[i]:
        b[i] += 1

sum_b = sum(b)
print(sum_b)

flag = True
for i, bb in enumerate(b):
    if i == 0:
        continue

    if bb != 0:
        flag = False
        print(i, end=' ')

if flag:
    print()


### FIXED CODE ###

N = int(input())
a = list(map(int, input().split(' ')))
b = [0 for _ in range(N)]

a.insert(0, 0)
b.insert(0, 0)

n = int(N/2)

for i in range(N, 0, -1):
    nums = 0
    for ii in range(2, int(N/i)+1):
        nums += b[i*ii]

    if nums % 2 != a[i]:
        b[i] += 1

sum_b = sum(b)
print(sum_b)

flag = False
for i, bb in enumerate(b):
    if i == 0:
        continue

    if bb != 0:
        flag = True
        print(i, end=' ')

if flag:
    print()
#El Patron
S = list(input())

pre_list = []
tar_list = [S[0]]
count = 1
a = 1
try:
	while a < len(S):
		pre_list = tar_list 
		tar_list = []
		tar_list.append(S[i])
		a += 1
	
		while tar_list == pre_list:
			tar_list.append(S[i])
			a += 1
	
		count += 1

except IndexError:
	pass
print(count)


### FIXED CODE ###

S = list(input())

pre_list = []
tar_list = [S[0]]
count = 1
i = 1
try:
	while i < len(S):
		pre_list = tar_list 
		tar_list = []
		tar_list.append(S[i])
		i += 1
		
		while tar_list == pre_list:
			tar_list.append(S[i])
			i += 1
	
		count += 1

except IndexError:
	pass
print(count)
s=input()
lst=[]
cnt=1
for i in range(n-2):
  if s[i]=s[i+1]:
    cnt+=1
  else:
    lst.append(cnt)
    cnt-=(cnt-1)
totl=0
if s[0]=='<':
  for j in range(len(lst)):
    if j%2==0:
      totl+=(lst[j]*(lst[j]-1))//2
      totl+=max(lst[j],lst[min(j+1,len(lst)-1)])
    else:
      totl+=(lst[j]*(lst[j]-1))//2
  print(totl)
else:
  totl+=lst[0]
  for j in range(len(lst)):
    if j%2==1:
      totl+=(lst[j]*(lst[j]-1))//2
      totl+=max(lst[j],lst[min(j+1,len(lst)-1)])
    else:
      totl+=(lst[j]*(lst[j]-1))//2
  print(totl)

      
      
      
      
      
  


### FIXED CODE ###

s=input()
n=len(s)
lst=[]
cnt=1

if n==2:
  print(1)
  
for i in range(n-1):
  if s[i]==s[i+1]:
    cnt+=1
  else:
    lst.append(cnt)
    cnt-=(cnt-1)

if s[n-2]!=s[n-1]:
  lst.append(1)
else:
  lst.append(cnt)
    
totl=0
l=len(lst)
if s[0]=='<':
  for j in range(l):
    if j%2==0:
      totl+=(lst[j]*(lst[j]-1))//2
      totl+=max(lst[j],lst[min(j+1,l-1)])
    else:
      totl+=(lst[j]*(lst[j]-1))//2
  print(totl)
else:
  totl+=lst[0]
  for j in range(len(lst)):
    if j%2==1:
      totl+=(lst[j]*(lst[j]-1))//2
      totl+=max(lst[j],lst[min(j+1,l-1)])
    else:
      totl+=(lst[j]*(lst[j]-1))//2
  print(totl)
n = int(input())
nums = [int(num) for num in input().split()]

num_min = nums[0]
num_max = nums[0]
for item in nums:
  if item < num_min:
    num_min = item
  else item > num_max:
    num_max = item

print(num_max - num_min)

### FIXED CODE ###

n = int(input())
nums = [int(num) for num in input().split()]

num_min = nums[0]
num_max = nums[0]
for item in nums:
  if item < num_min:
    num_min = item
  if item > num_max:
    num_max = item

print(num_max - num_min)
j = 0
for n in s:
  if n == "a":
    if i + j < a + b:
      i += 1
      print("Yes")
    else:
      print("No")
  elif n == "b":
    if (i + j < a + b) and j < b:
      j += 1
      print("Yes")
    else:
      print("No")
  else:
    print("No")


### FIXED CODE ###

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

i = 0
j = 0
for n in s:
  if n == "a":
    if i + j < a + b:
      i += 1
      print("Yes")
    else:
      print("No")
  elif n == "b":
    if (i + j < a + b) and j < b:
      j += 1
      print("Yes")
    else:
      print("No")
  else:
    print("No")
a,b,import numpy as np
import itertools
n, m, x = map(int, input().split())
a = np.dot([i for i in itertools.product([0, 1], repeat = n)],
           [list(map(int, input().split())) for _ in range(n)])
b = np.prod(a[:, 1:(m + 1)] >= x, axis = 1, dtype = bool)
print(min(a[:, 0][b]) if b.sum() else '-1')


### FIXED CODE ###

import numpy as np
import itertools
n, m, x = map(int, input().split())
a = np.dot([i for i in itertools.product([0, 1], repeat = n)],
           [list(map(int, input().split())) for _ in range(n)])
b = np.prod(a[:, 1:(m + 1)] >= x, axis = 1, dtype = bool)
print(min(a[:, 0][b]) if b.sum() else '-1')
import sys
input = sys.stdin.readline
from collections import deque
import numba

@njit
n = int(input())
a = list(map(int,input().split()))
n += 2
ls = [0 for i in range(n*n)]
for i in range(n):
  for j in range(n):
    ls[i*n+j] = min(i,j,n-1-i,n-1-j)-1
ans = 0
st = [0]*(n*n)
for i in a:
  x,y = divmod(i-1,n-2)
  i = (x+1)*n+(y+1)
  ans += ls[i]
  st[i]=1
  q = deque([i])
  while q:
    j = q.popleft()
    for k in (j-n,j+n,j+1,j-1):
      if st[j]:
        if ls[j] < ls[k]:
          ls[k] = ls[j]
          q.append(k)
      elif ls[j]+1 < ls[k]:
        ls[k] = ls[j]+1
        q.append(k)
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
from collections import deque
n = int(input())
a = list(map(int,input().split()))
n += 2
ls = [0 for i in range(n*n)]
for i in range(n):
  for j in range(n):
    ls[i*n+j] = min(i,j,n-1-i,n-1-j)-1
ans = 0
st = [0]*(n*n)
for i in a:
  x,y = divmod(i-1,n-2)
  i = (x+1)*n+(y+1)
  ans += ls[i]
  st[i]=1
  q = deque([i])
  while q:
    j = q.popleft()
    for k in (j-n,j+n,j+1,j-1):
      if st[j]:
        if ls[j] < ls[k]:
          ls[k] = ls[j]
          q.append(k)
      elif ls[j]+1 < ls[k]:
        ls[k] = ls[j]+1
        q.append(k)
print(ans)
n = list(map(int, input().split()))
if n[1] = n[2]:
  print(min(n[1], n[2]), max(0, n[1] + n[2] - n[0]))


### FIXED CODE ###

n = list(map(int, input().split()))
print(min(n[1], n[2]), max(0, n[1] + n[2] - n[0]))
n = input()

print(n**3)

### FIXED CODE ###

n = int(input())

print(n**3)
n, m = map(int, input().split())
sub_ls = []
for i in range(m):
    p, s = list(map(str, input().split()))
    p = int(p)
    sub_ls.append([p,s])
ac_cnt = []
wa_cnt = []
for i in range(n):
    ac_cnt.append(0)
    wa_cnt.append(0)
#print(ac_cnt, wa_cnt)
for i in range(m):
    if ac_cnt[sub_ls[i][0]-1] == 0:
        #print(sub_ls[i][1], ac_cnt[i])
        if sub_ls[i][1] == "AC":
            ac_cnt[sub_ls[i][0]-1] = 1
        else:
            wa_cnt[i-1]+=1
ac_sum = 0
wa_sum = 0
for i in range(n):
    if ac_cnt[i] == 1:
        ac_sum+=1
    wa_sum+=wa_cnt[i]
print(ac_sum, wa_sum)


### FIXED CODE ###

n, m = map(int, input().split())
sub_ls = []
for i in range(m):
    p, s = list(map(str, input().split()))
    p = int(p)-1
    sub_ls.append([p,s])
ac_cnt = []
wa_cnt = []
for i in range(n):
    ac_cnt.append(0)
    wa_cnt.append(0)
#print(ac_cnt, wa_cnt)
for i in range(m):
    if ac_cnt[sub_ls[i][0]] == 0:
        #print(sub_ls[i][1], ac_cnt[i])
        if sub_ls[i][1] == "AC":
            ac_cnt[sub_ls[i][0]] = 1
        else:
            wa_cnt[sub_ls[i][0]]+=1
ac_sum = 0
wa_sum = 0
for i in range(n):
    #print(ac_cnt[i], wa_cnt[i])
    ac_sum+=ac_cnt[i]
    if ac_cnt[i] == 1:
        wa_sum+=wa_cnt[i]
print(ac_sum, wa_sum)
print(["NO","YES"][eval(input().replace(" ","*"))])

### FIXED CODE ###

print(["NO","YES"][eval(input().replace(" ","*"))==175])
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)


### FIXED CODE ###

from itertools import groupby
import heapq

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

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

inverse=[pow(fact[i],mod-2,mod) for i in range(2*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:
    if rest==0:
        print(ans)
    else:
        print(0)
N, K = map(int, input().split())
L = [1 for i in range(N)]
for k in range(K):
  d = int(input())
  A = list(map(int, input().spit()))
  for i in range(d):
    L[A[i] - 1] = 0
print(sum(L))

### FIXED CODE ###

N, K = map(int, input().split())
L = [1 for i in range(N)]
for k in range(K):
  d = int(input())
  A = list(map(int, input().split()))
  for i in range(d):
    L[A[i] - 1] = 0
print(sum(L))
a = int(input())
b = int(input())
print('Odd' if a%2!=0 and b%2!=0 else 'Even')

### FIXED CODE ###

a,b = map(int,input().split())
print('Odd' if a%2!=0 and b%2!=0 else 'Even')
import sys

N = int(input())
A = list(map(int, input().split()))
A = sorted([A[k]-(k+1) for k in range(N)])

for k in range((N-2)//2 + 1, N-1):
  if A[k] < A[k+1]:
    b = k
    break
  if k == N-2:
    print(0)
    sys.exit()
print(sum([abs(A[k]-A[b]) for k in range(N)]))

### FIXED CODE ###

import sys

N = int(input())
A = list(map(int, input().split()))
A = sorted([A[k]-(k+1) for k in range(N)])

if N == 1:
  print(0)
  sys.exit()

for k in range((N-2)//2 + 1, N-1):
  if A[k] < A[k+1]:
    b = k
    break
  if k == N-2:
    print(0)
    sys.exit()
print(sum([abs(A[k]-A[b]) for k in range(N)]))
N = int(input())
S = [input().split() for i in range(N)]

if N >= 1 and N <=100:
	def S.islower():
	if True:
      T = S[0:N / 2 - 1]
    else:

if (T + T in s):
  print('Yes')
else:
  print('No')


### FIXED CODE ###

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

T = S[0:int(N) // 2]
W = S[int(N) // 2:int(N) + 1] 

if T == W:
	print('Yes')
else:
	print('No')
S = input()
if S.couut("a") == S.count("b") == S.count("c"):
  print("Yes")
else:
  print("No")

### FIXED CODE ###

S = sorted(input())
if S == ["a", "b", "c"]:
  print("Yes")
else:
  print("No")
N = int(input())
A = input().split()
flag = 1

for j in range(N):
	for i in range(N):
		if i+j+1<N:
			if A[j] == A[i+j+1]:
				flag = 0
				break
if flag==0:
	print('NO')
elif flag==1:
	print('YES')



### FIXED CODE ###

s,t = input().split()
a,b = map(int,input().split())
#print(s,t)
#print(a,b)
u = input()
#print(u)

if s == u :
	a = a - 1
elif t == u:
	b = b - 1

print(a, b)
N,M=map(int,input().split())
a=[0]
for _ in range(M):
    a.append(int(input()))

b=[]
b.append(a[1]-a[0]-1)
for i in range(1,M):
    if a[i+1]-a[i]==1:
        b.append(0)
    else:
        b.append(a[i+1]-a[i]-2)
b.append(N-a[M]-1)

num=max(b)

mod=1000000007

def fib(n,num):
    fib=[0 for i in range(num+10)]
    fib[0]=1
    fib[1]=1
    for i in range(2,num+1):
        fib[i]=fib[i-1]+fib[i-2]
    return fib[n]
p=1
for j in range(M+1):
    p*=fib(b[j],num)

if 0 in b[1:]:
    print(0)
else:
    print(p%mod)

### FIXED CODE ###

N,M=map(int,input().split())
a=[0]
for _ in range(M):
    a.append(int(input()))

b=[]
num=0
if len(a)>1:
    b.append(a[1]-a[0]-1)
    for i in range(1,M):
            b.append(a[i+1]-a[i]-2)
    b.append(N-a[M]-1)
else:
    b.append(N)

num=max(b)


mod=1000000007

def fib(n,num):
    fib=[0 for i in range(num+10)]
    fib[0]=1
    fib[1]=1
    for i in range(2,num+1):
        fib[i]=fib[i-1]+fib[i-2]
    return fib[n]

if -1 in b:
    print(0)
else:
    p=1
    for j in range(M+1):
        p*=fib(b[j],num)
    print(p%mod)