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

s=input()+'T'
x,y=map(int,input().split())
if 'T' in s:
  pos=s.index('T')
  x-=pos
  s=s[pos+1:]
arr=s.split('T')
xarr=[]
yarr=[]
for i in range(len(arr)):
  l=len(arr[i])
  if l==0:
    continue
  if i%2==0:
    yarr.append(l)
  else:
    xarr.append(l)
x+=sum(xarr)
y+=sum(yarr)
if x%2==1 or y%2==1:
  print('No')
else:
  #DP for xarr,yarr
  xdp=[0]*8005
  xdp[0]=1
  for val in xarr:
    for i in range(8004,-1,-1):
      if i-val<0:
        break
      if xdp[i-val]==1:
        xdp[i]=1
  ydp=[0]*8005
  ydp[0]=1
  for val in yarr:
    for i in range(8004,-1,-1):
      if i-val<0:
        break
      if ydp[i-val]==1:
        ydp[i]=1
  if xdp[x//2]==0:
    print('No')
  else:
    if ydp[y//2]==0:
      print('No')
    else:
      print('Yes')

### FIXED CODE ###

s=input()+'T'
x,y=map(int,input().split())
if 'T' in s:
  pos=s.index('T')
  x-=pos
  s=s[pos+1:]
arr=s.split('T')
xarr=[]
yarr=[]
for i in range(len(arr)):
  l=len(arr[i])
  if l==0:
    continue
  if i%2==0:
    yarr.append(l)
  else:
    xarr.append(l)
x+=sum(xarr)
y+=sum(yarr)
if x%2==1 or y%2==1:
  print('No')
else:
  #DP for xarr,yarr
  xdp=[0]*8005
  xdp[0]=1
  for val in xarr:
    for i in range(8004,-1,-1):
      if i-val<0:
        break
      if xdp[i-val]==1:
        xdp[i]=1
  ydp=[0]*8005
  ydp[0]=1
  for val in yarr:
    for i in range(8004,-1,-1):
      if i-val<0:
        break
      if ydp[i-val]==1:
        ydp[i]=1
  if xdp[x//2]==0:
    print('No')
  else:
    if ydp[y//2]==0:
      print('No')
    else:
      print('Yes')
### BUGGY CODE ###

n=int(input())
li=list(map(int,input().split()))
ans=1
for i in li:
    ans=ans*i
if ans<=10**18:
    print(ans)
else:
    print("-1")

### FIXED CODE ###

n=int(input())
li=list(map(int,input().split()))
if 0 in li:
    print(0)
    exit()
ans=1

for i in li:
    ans=ans*i
    if ans>10**18:
        print(-1)
        exit()
print(ans)
### BUGGY CODE ###

import itertools
def main():

    N, M, R = map(int, input().split())
    r = list(map(int, input().split()))
    r = [v-1 for v in r]

    dist = [[float('inf') for _ in range(N)] for _ in range(N)]
    for i in range(N): dist[i][i] = 0
    for _ in range(M):
        a, b, c = map(int, input().split())
        dist[a-1][b-1] = c
        dist[b-1][a-1] = c

    for k in range(N):
        for i in range(N):
            for j in range(N):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

    path = itertools.permutations(r)
    ans = float('inf')
    for p in path:
        d = 0
        for i in range(len(p)-1):
            d += dist[p[i]][p[i+1]]
        ans = min(ans, d)

    return ans

if __name__ == '__main__':
    print(main())

### FIXED CODE ###

import itertools
def main():

    N, M, R = map(int, input().split())
    r = list(map(int, input().split()))
    r = [v-1 for v in r]

    dist = [[float('inf') for _ in range(N)] for _ in range(N)]
    for i in range(N): dist[i][i] = 0
    for _ in range(M):
        a, b, c = map(int, input().split())
        dist[a-1][b-1] = c
        dist[b-1][a-1] = c

    for k in range(N):
        for i in range(N):
            for j in range(N):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

    path = itertools.permutations(r)
    ans = float('inf')
    for p in path:
        d = 0
        for i in range(len(p)-1):
            d += dist[p[i]][p[i+1]]
        ans = min(ans, d)

    return ans

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

N = int(input())
T = [[] for i in range(N+1)]
for _ in range(N-1):
    a, b, c = map(int, input().split())
    T[a].append([b,c])
    T[b].append([a,c])

Q, K = map(int, input().split())
shortest_path = [0 for _ in range(N+1)]
queue = [t + [K] for t in T[K]]

while len(queue) > 0:
    v = queue.pop(0)
    shortest_path[v[0]] = v[1]
    queue += [[u[0], u[1] + v[1], v[0]] for u in T[v[0]] if u[0] != v[2]]

for _ in range(Q):
    x, y = map(int, input().split())
    print(shortest_path[x] + shortest_path[y])

### FIXED CODE ###

from collections import deque

N = int(input())
T = [{} for i in range(N+1)]
for _ in range(N-1):
    a, b, c = map(int, input().split())
    T[a][b] = c
    T[b][a] = c

Q, K = map(int, input().split())
shortest_path = [0 for _ in range(N+1)]
queue = deque([[v, T[K][v], K] for v in T[K].keys()])
for _ in range(N-1):
    v = queue.popleft()
    shortest_path[v[0]] = v[1]
    queue.extend([[u, T[v[0]][u] + v[1], v[0]] for u in T[v[0]].keys() if u != v[2]])

for _ in range(Q):
    x, y = map(int, input().split())
    print(shortest_path[x] + shortest_path[y])
### BUGGY CODE ###

S = input()
r, ans = 0, 0
for l in range(len(S)):
    while r < len(S):
        if int(S[l:r+1]) % 2019 == 0:
            ans += 1
            break
        r += 1
    r = l + 1
print(ans)


### FIXED CODE ###

import sys
from collections import deque
def input():
    return sys.stdin.readline()[:-1]

S = deque(map(int, list(input())))
num = 0
dict = {}
dict[0] = 1
ans = 0

for i in range(len(S)):
    num += S.pop() * pow(10,i,2019)
    cand = num % 2019
    if cand in dict.keys():
        dict[cand] += 1
    else:
        dict[cand] = 1

for key in dict.keys():
    ans += dict[key] * (dict[key] - 1) // 2
print(ans)
### BUGGY CODE ###

n=int(input())
l=list()
for i in range(n):
    k=input()
    q=k in l
    if q==False:
        l.append(k)
print(len(l))

### FIXED CODE ###

n=int(input())
l=set()
for i in range(n):
    k=input()
    q=k in l
    if q==False:
        l.add(k)
print(len(l))
### BUGGY CODE ###

def d170(n,a):
    count=0
    sa=sorted(list(set(a)))
    t=set([x for x in set(a) if a.count(x)>1])
    if sa[0]==1:
        if 1 in t:
            return 0
        else:
            return 1
    else:
        for i in range(len(sa)) :
            if i>=len(sa):
                break
            else:
                p=sa[i]
                k=[]
                for j in range(i+1,len(sa)):
                     if sa[j]%p==0:
                        k.append(sa[j])
                sa=sorted(list(set(sa)-set(k)))
        return len(set(sa)-t)
    
n=int(input())
a= list(map(int, input().split()))    
print(d170(n,a))
            

### FIXED CODE ###

def d170(n,a):
    k=max(a)+1
    count=0
    dp=[0 for i in range(k)]
    for x in a:
        if dp[x]!=0:
                dp[x]=2
                
        else:
            for j in range(x,k,x):
                     dp[j]+=1
    for x in a:
        if dp[x]==1:
            count+=1
    return count
    
n=int(input())
a=list(map(int, input().split()))    
print(d170(n,a))
### BUGGY CODE ###

import numpy as np
from collections import deque

n, m = list(map(int, input().split()))
a = np.zeros((m,), dtype=np.int)
b = np.zeros((m,), dtype=np.int)
for i in range(m):
    a[i], b[i] = list(map(int, input().split()))
a -= 1
b -= 1

is_visited = np.zeros((n,), dtype=np.bool)
parent = np.zeros((n,), dtype=np.int)

q = deque()
q.append(0)
is_visited[0] = True
while len(q) != 0:
    node = q.popleft()
    for i in np.where(a == node)[0]:
        child = b[i]
        if not is_visited[child]:
            is_visited[child] = True
            parent[child] = node
            q.append(child)
    for i in np.where(b == node)[0]:
        child = a[i]
        if not is_visited[child]:
            is_visited[child] = True
            parent[child] = node
            q.append(child)

parent += 1

print('Yes')
for node in parent[1:]:
    print(node)

### FIXED CODE ###

from collections import deque
import numpy as np

n, m = list(map(int, input().split()))
edge = {}
for i in range(m):
    ai, bi = list(map(int, input().split()))
    if ai in edge:
        edge[ai].append(bi)
    else:
        edge[ai] = [bi,]
    if bi in edge:
        edge[bi].append(ai)
    else:
        edge[bi] = [ai,]
# print(edge)

is_visited = np.zeros((n+1,), dtype=np.bool)
parent = np.zeros((n+1,), dtype=np.int)

q = deque()
q.append(1)
is_visited[1] = True
while len(q) != 0:
    node = q.popleft()
    for child in edge[node]:
        if not is_visited[child]:
            is_visited[child] = True
            parent[child] = node
            q.append(child)

print('Yes')
print('\n'.join(list(map(str, list(parent[2:])))))
### BUGGY CODE ###

n,q=map(int,input().split())
s=input()
slis=[]
for i in range(len(s)-1):
	slis.append(s[i]+s[i+1])
for j in range(q):
	l,r=map(int,input().split())
	print(slis[l-1:r-1].count("AC"))

### FIXED CODE ###

N,Q=map(int,input().split())
S=input()
count=[0]*N
for i in range(1,N):
    count[i]+=count[i-1]
    if S[i-1:i+1]=="AC":count[i]+=1
for i in range(Q):
    l,r=map(int,input().split())
    print(count[r-1]-count[l-1])
### BUGGY CODE ###

A, B = map(int, input().split())
result = [i for i in range(A, B + 1)]
for index, i in enumerate(range(A, B + 1)):
    if index == 0:
        continue
    result[index] = result[index-1] ^ result[index]
print(result[len(result) - 1])


### FIXED CODE ###

A, B = map(int, input().split())

def calc(n):
    mod = n % 4
    if mod == 0:
        return n
    elif mod == 1:
        return n ^ (n-1) 
    elif mod == 2:
        return n ^ 1
    elif mod == 3:
        return 0
a = calc(A - 1)
b = calc(B)

print(a ^ b)
### BUGGY CODE ###

s = list(input())
s.reverse()
nb = s.count("B")
l = len(s)
ret = 0 
for i in range(nb):
    for j in range(l-i):
        if s[j+i]=="B":
            ret += j
            s[j+i]="W"
            break
print(ret)

### FIXED CODE ###

s = list(input())
s.reverse()
wl = 0 
rwl = 0 
ret = 0 
l = len(s)
for i in range(l):
    if s[i] == "W":
        wl += 1
    else:
        ret += rwl + wl
        rwl += wl
        wl = 0 
print(ret)
### BUGGY CODE ###

x,y = map(int,input().split())
i = 1
if x == y:
  print(-1)
else:
  while True:
    if (i*x)%y != 0:
      print(i*x)
      exit()
    else:
      i += 1

### FIXED CODE ###

x,y = map(int,input().split())
if x%y == 0:
  print(-1)
else:
  print(x)
### BUGGY CODE ###

K,S = map(int,input().split())

ans = 0
for a in range(K+1):
  for b in range(K+1):
    for c in range(K+1):
      if a+b+c == S:
        ans += 1

print(ans)

### FIXED CODE ###

K,S = map(int,input().split())

ans = 0
for a in range(K+1):
  for b in range(K+1):
    if 0 <= S-a-b <= K:
        ans += 1

print(ans)
### BUGGY CODE ###

n = int(input())
l = []
for _ in range(n):
    a = int(input())
    l.append(a)

memo = []

for i in range(n):
    if l[i] not in memo:
        memo.append(l[i])
    else:
        memo.remove(l[i])

print(len(memo))

### FIXED CODE ###

n = int(input())
l = []
 
for _ in range(n):
    a = int(input())
    l.append(a)

l.sort()

ans = 0
cnt = 1
tmp = l[0]
for i in range(1,len(l)):
    if tmp == l[i]:
        cnt += 1
        tmp = l[i]
    else:
        if cnt%2 != 0:
            ans += 1
            cnt = 1
            tmp = l[i]
        else:
            cnt = 1
            tmp = l[i]
if cnt%2 != 0:
    ans += 1

print(ans)
### BUGGY CODE ###

n, p = map(int, input().split())
s = input()

if 10%p==0:
    ans = 0
    for r in range(n):
        if int(s[r])%p == 0:
            ans += r+1
    print(ans)
    exit()

d = [0]*(n+1)
ten = 1

for i in range(n-1, -1, -1):
    a = int(s[i])*ten%p
    d[i] = (d[i+1]+a)%p
    ten *= 10
    #ten %= p

cnt = [0]*p
ans = 0
for i in range(n, -1, -1):
    ans += cnt[d[i]]
    cnt[d[i]] += 1
print(ans)

### FIXED CODE ###

n, p = map(int, input().split())
s = input()

if 10%p==0:
    ans = 0
    for r in range(n):
        if int(s[r])%p == 0:
            ans += r+1
    print(ans)
    exit()

d = [0]*(n+1)
ten = 1

for i in range(n-1, -1, -1):
    a = int(s[i])*ten%p
    d[i] = (d[i+1]+a)%p
    ten *= 10
    ten %= p

cnt = [0]*p
ans = 0
for i in range(n, -1, -1):
    ans += cnt[d[i]]
    cnt[d[i]] += 1
print(ans)
### BUGGY CODE ###

import sys
import numpy as np
input = sys.stdin.readline
h, w = map(int, input().split())
grid = []
bias_inf = 2000
for i in range(h):
    k = list(map(int, input().split()))
    grid.append(k)
for i in range(h):
    k = list(map(int, input().split()))
    for j in range(w):
        grid[i][j] = abs(grid[i][j] - k[j])

dp = np.full((h,w,bias_inf*2), False)
dp[0][0][0 - grid[0][0]] = True
dp[0][0][0 + grid[0][0]] = True
for i in range(h):
    for j in range(w):
        for k in range(-bias_inf,bias_inf):
            if i == h-1 and j == w-1:
                break
            if dp[i][j][k]:
                if i == h-1:
                    dp[i][j+1][k - grid[i][j+1]] = True
                    dp[i][j+1][k + grid[i][j+1]] = True
                elif j == w-1:
                    dp[i+1][j][k - grid[i+1][j]] = True
                    dp[i+1][j][k + grid[i+1][j]] = True
                else:
                    dp[i][j+1][k + grid[i][j+1]] = True
                    dp[i+1][j][k + grid[i+1][j]] = True
                    dp[i][j+1][k - grid[i][j+1]] = True
                    dp[i+1][j][k - grid[i+1][j]] = True
ans = bias_inf
for i in range(-bias_inf,bias_inf):
    if dp[-1][-1][i]:
        ans = min(ans, abs(i))
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
h, w = map(int, input().split())
grid = []
bias_inf = 2000
for i in range(h):
    k = list(map(int, input().split()))
    grid.append(k)
for i in range(h):
    k = list(map(int, input().split()))
    for j in range(w):
        grid[i][j] = abs(grid[i][j] - k[j])

dp = [[[0 for i in range(-bias_inf,bias_inf)] for j in range(w)] for k in range(h)]
dp[0][0][0 - grid[0][0]] = 1
dp[0][0][0 + grid[0][0]] = 1
for i in range(h):
    for j in range(w):
        for k in range(-bias_inf,bias_inf):
            if i == h-1 and j == w-1:
                break
            if dp[i][j][k]:
                if i != h-1 and j != w-1:
                    dp[i][j+1][k + grid[i][j+1]] = 1
                    dp[i+1][j][k + grid[i+1][j]] = 1
                    dp[i][j+1][k - grid[i][j+1]] = 1
                    dp[i+1][j][k - grid[i+1][j]] = 1
                elif j == w-1:
                    dp[i+1][j][k - grid[i+1][j]] = 1
                    dp[i+1][j][k + grid[i+1][j]] = 1
                else:
                    dp[i][j+1][k - grid[i][j+1]] = 1
                    dp[i][j+1][k + grid[i][j+1]] = 1
ans = bias_inf
for i in range(-bias_inf,bias_inf):
    if dp[-1][-1][i]:
        ans = min(ans, abs(i))
print(ans)
### BUGGY CODE ###

n = int(raw_input())
cout = ""

for i in range(1,n+1):
	x = i

	if (x%3) == 0:
		cout = cout + " " + str(i)
		continue

	while x > 0:
		if (x%10) == 3:
			cout = cout + " " + str(i)
			continue
		x /= 10

print cout

### FIXED CODE ###

n = int(raw_input())
cout = ""

for i in range(1,n+1):
	x = i

	if (x%3) == 0:
		cout = cout + " " + str(i)
		continue

	while x > 0:
		if (x%10) == 3:
			cout = cout + " " + str(i)
			break
		x /= 10

print cout
### BUGGY CODE ###

N,M = map(int, input().split())
X = [ [int(j) for j in input().split()] for _ in range(N)]
ans = 0
sgn = [[-1,-1,-1],
        [-1,-1, 1],
        [-1, 1,-1],
        [-1, 1, 1],
        [ 1,-1,-1],
        [ 1,-1, 1],
        [ 1, 1,-1],
        [ 1, 1, 1]]
for s in sgn:
    dp = [ [0] * (M+1) for _ in range(N+1)]
 
    for n in range(0,N):
        x,y,z = X[n]
 
        # for m in range(0, min(n+1,M) ):
        for m in range(min(n,M-1), -1, -1 ):
            dp[n+1][m+1] =  max(dp[n+1][m+1], \
                (x if (s[0]>0) else -x) \
                + (y if (s[1]>0) else -y) \
                + (z if (s[2]>0) else -z) \
                + dp[n][m] )
            dp[n+1][m]   =  max(dp[n+1][m], dp[n][m])
 
        dp[n+1][M] = max(dp[n+1][M], dp[n][M])
    ans = max(ans, dp[N][M])
print(ans)

### FIXED CODE ###

N,M = map(int, input().split())
X = [ [int(j) for j in input().split()] for _ in range(N)]
ans = 0
for i in range(1<<3):
    if M==0:
        break
    ss = [None]*N

    for n in range(0,N):
        x,y,z = X[n]
        s = (x if (i & (1<<2)) else -x) \
            + (y if (i & (1<<1)) else -y) \
            + (z if (i & (1<<0)) else -z)
        ss[n] = s
    ss.sort()
    ans = max(ans, sum(ss[N-M:]))
print(ans)
### BUGGY CODE ###

N,K= map(int, input().split())
A =list(map(int, input().split()))
 
Aset =list(set(A))
B=[0]*len(Aset)
cnt =0
 
for i in range(len(Aset)):
  for j in range(len(A)):
    if Aset[i] == A[j]:
      cnt += 1
  B[i] = cnt
  cnt =0
 
B=sorted(B)[::-1]  
 
ans =0
 
for i in range(K,len(B)):
  ans +=B[i]
  
print(ans) 

### FIXED CODE ###

N,K=map(int, input().split())
a=list(map(int, input().split()))


import collections

c = collections.Counter(a)
c2=sorted(c.values())

sum=0
for i in range(len(c)-K):
        sum+=c2[i]
print(sum)
### BUGGY CODE ###

#!/usr/bin/env python3
from collections import Counter
MOD = 998244353


def solve(n,d):
    if d[0] != 0:
        return 0
    dc = Counter(d)
    if dc[0] > 1:
        return 0
    res = 1
    k = 1
    while k <= max(d):
        res *= dc[k-1]**dc[k]
        res %= MOD
        k += 1
    return res


def main():
    N = int(input())
    d = list(map(int,input().split()))
    # N,M = map(int,input().split())
    print('{}'.format(solve(N,d)))


if __name__ == '__main__':
  main()


### FIXED CODE ###

#!/usr/bin/env python3
from collections import Counter
MOD = 998244353


def solve(n,d):
    if d[0] != 0:
        return 0
    dc = Counter(d)
    if dc[0] > 1:
        return 0
    res = 1
    k = 1
    dmax = max(d)
    while k <= dmax:
        res *= dc[k-1]**dc[k]
        res %= MOD
        k += 1
    return res


def main():
    N = int(input())
    d = list(map(int,input().split()))
    # N,M = map(int,input().split())
    print(solve(N,d))


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

# N,Kの把握
l1 = list(map(int, input().split()))
N = l1[0]
K = l1[1]

#タイムアウト問題。リストをソートし、K後を削除する。
#空リストを作成。a,bを把握し、リストにaを追加、b回。これをN回くりかえし
l3 = []
for i in range(N):
	l2 = list(map(int, input().split()))
	a = l2[0]
	b = l2[1]
	if len(l3) > K and max(l3) < a:
		pass
	else:
		for j in range(b):
			l3.append(a)

# リストをソートし、K番目を出力
l3.sort()
print(str(l3[K-1]))

### FIXED CODE ###

# N,Kの把握
l1 = list(map(int, input().split()))
N = l1[0]
K = l1[1]

#リストをすぐに作成するのが悪手。数値と回数をセット作成
dic = {}
for i in range(N):
	l2 = list(map(int, input().split()))
	a = l2[0]
	b = l2[1]
	if a in dic:
		dic[a] += b #既に存在する数値であればそのまま回数を＋
	else:
		dic.update({a: b}) #新規の数値であれば追加

dic = sorted(dic.items(), key=lambda x:x[0])

x = 0
for key, value in dic: #回数値を足していき、総回数＞＝Kとなったときの数値を出力する。
	x += value
	if x >= K:
		print(str(key))
		break
### BUGGY CODE ###

import numpy as np

N = int(input())

inp = map(int,input().split(' '))

A = [int(i) for i in inp]

for j in range(N):
    B = np.hstack(([0],np.delete(A, j),[0]))
    print(int(np.sum(np.abs(np.diff(B,n=1)))))

### FIXED CODE ###

import numpy as np

N = int(input())

inp = map(int,input().split(' '))

A = [0] + [int(i) for i in inp] + [0]
s = np.sum(np.abs(np.diff(A,n=1)))

for j in range(1,N+1):
    df = np.abs(A[j+1]-A[j-1]) - np.abs(A[j]-A[j-1]) - np.abs(A[j+1]-A[j])
    print(int(s+df))
### BUGGY CODE ###

#C
N, K = map(int, input().split())
A = list(map(int, input().split()))
p=[]
ans=1
for j in range(K):
    ans=ans*A[j]
p.append(ans)
for i in range(1,N-K+1):
    ans=ans*A[i+K-1]/A[i-1]
    p.append(ans)

for j in range(len(p)-1):
    if p[j]<p[j+1]:
        print('Yes')
    else:
        print('No')

### FIXED CODE ###

#C
N, K = map(int, input().split())
A = list(map(int, input().split()))
p=[]
for i in range(N-K):
    if A[i+K]>A[i]:
        p.append(1)
    else:
        p.append(0)

for j in range(len(p)):
    if p[j]==1:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

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

r = s.count("R")
g = s.count("G")
b = s.count("B")

ans = r*g*b

for i in range(n):
    for j in range(i+1,n):
        k = j + (j-i)
        if k<n and set([s[i],s[j],s[k]])==set(["R","G","B"]):
            ans -= 1
print(ans)


### FIXED CODE ###

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

r = s.count("R")
g = s.count("G")
b = s.count("B")

ans = r*g*b

for i in range(n):
    for j in range(i+1,n):
        k = j + (j-i)
        if k<n and set([s[i],s[j],s[k]])==set(["R","G","B"]):
            ans -= 1
print(ans)
### BUGGY CODE ###

N = int(input())
M = [x+1 for x in range(N)]
print(sum(set(M))-N)

### FIXED CODE ###

N = int(input())
ans = N*(N-1)//2
print(ans)
### BUGGY 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

    return ans

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

ans = 1
cur = 0
open = 0
for c in s:
    # print(c, ans, open, cur)
    if c == "B":
        if open%2 == 0:
            open += 1
            cur = 1
        else:
            if open == 0:
                print(0)
                sys.exit()
            ans *= open
            ans %= MOD
            open -= 1
            cur = 0

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

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

### FIXED 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)
### BUGGY CODE ###

import sys

def JudgeLunLun(num):
  val = num
  if num <= 12:
    val = num
  else:
    # 真面目なルンルン数判定。配列に1文字ずつ格納して全桁ループ処理して判定
    A = [int(x) for x in list(str(num))]
    for i in range(len(A)-1):
      if abs(A[i]-A[i+1]) > 1:
        val = 0
        break
  return val

def main():
  K = int(input())
  cnt = 0
  for i in range(1, sys.maxsize):
    num = JudgeLunLun(i)
    # ルンルン数判定
    if num > 0:
      cnt += 1
    if cnt == K:
      break
  print(num)

if __name__ == '__main__':
  main()

### FIXED CODE ###

import sys

def JudgeLunLun(num):
  val = num
  next = 0
  if num <= 12:
    val = num
  else:
    # 真面目なルンルン数判定。文字列に変換して1桁毎の処理を行う。
    # 加算処理に備えて文字として扱う
    A = str(num)
    for i in range(len(A)-1):
      if abs(int(A[i])-int(A[i+1])) > 1:
        val = 0
        # A[i+1]が大きい時は、A[i]をカウントアップするしかない。
        if int(A[i]) < int(A[i+1]):
          head = str(int(A[:i+1])+1)
          body = '0'
          tail = '0' * (len(A) - (i+2))
        else:
          if int(A[i]) - int(A[i+1]) > 2:
            head = A[:i+1]
            body = str(int(A[i]) -1)
            tail = '0' * (len(A) - (i+2))            
          else:
            head = A[:i+1]
            body = str(int(A[i+1]) +1)
            tail = '0' * (len(A) - (i+2))
            if body == '10':
              head = str(int(head)+1)
              body = '0'
        
        # 編集後の値を結合して数値変換して返す
        next = int(head+body+tail)
  
  return val, next

def main():
  K = int(input())
  cnt = 0
  i = 1
  while cnt < K:
    val, next = JudgeLunLun(i)
    # ルンルン数判定
    if val > 0:
      i += 1
      cnt += 1
      if cnt == K:
        break
    else:
      i = next
    
  print(val)

if __name__ == '__main__':
  main()