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

import copy
H,W,K=map(int,input().split())
S=[]
for _ in range(H):
    S.append([int(x) for x in list(input())])

ans=(H-1)+(W-1)

for i in range(2**(H-1)):
    check=[0]*H
    for j in range(H-1):
        if ((i>>j)&1):
            check[j+1]=check[j]+1
        else:
            check[j+1]=check[j]
    
    g=check[H-1]+1
    A=[0]*g
    c=0
    f=0
    for j in range(W):
        B=[0]*g
        for k in range(H):
            if S[k][j]==1:
                B[check[k]]+=1
            if B[check[k]]>K:
                c=10**4
                f=1
                break
        if f:
            break
        #print("AB",A,B)
        for l in range(g):
            if A[l]+B[l]>K:
                c+=1
                A=copy.copy(B)
                break
            else:
                A[l]+=B[l]
    ans=min(ans,c+g-1)

print(ans)




### FIXED CODE ###

import copy
H,W,K=map(int,input().split())
S=[]
for _ in range(H):
    S.append([int(x) for x in list(input())])

ans=(H-1)+(W-1)

for i in range(2**(H-1)):
    check=[0]*H
    for j in range(H-1):
        if ((i>>j)&1):
            check[j+1]=check[j]+1
        else:
            check[j+1]=check[j]
    
    g=check[H-1]+1
    A=[0]*g
    c=0
    f=0
    for j in range(W):
        B=[0]*g
        for k in range(H):
            if S[k][j]==1:
                B[check[k]]+=1
            if B[check[k]]>K:
                c=10**4
                f=1
                break
        if f:
            break
        #print("AB",A,B)
        for l in range(g):
            if A[l]+B[l]>K:
                c+=1
                A=copy.copy(B)
                break
            else:
                A[l]+=B[l]
    ans=min(ans,c+g-1)

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

import sys
readline = sys.stdin.readline
from math import floor
from decimal import Decimal

N = int(readline())
A = [Decimal(readline()) for _ in range(N)]


G = 10**10
Aint = [int(a) for a in A if int(a) == a]
Afl = [int(a*G) for a in A if int(a) != a]


H = 200
geta = 100
Grid = [[0]*H for _ in range(H)]


i25 = []
for ai in Aint:
    i2 = 0
    i5 = 0
    while ai%2 == 0:
        ai //= 2
        i2 += 1
    while ai%5 == 0:
        ai //= 5
        i5 += 1
    i25.append((i2, i5)) 

for af in Afl:
    i2 = -10
    i5 = -10
    while af%2 == 0:
        af //= 2
        i2 += 1
    while af%5 == 0:
        af //= 5
        i5 += 1
    i25.append((i2, i5)) 


for i2, i5 in i25:
    Grid[geta+i2][geta+i5] += 1

for i in range(geta+90, geta-90, -1):
    for j in range(geta+90, geta-90, -1):
        Grid[i][j] += Grid[i][j+1]

for j in range(geta+90, geta-90, -1):
    for i in range(geta+90, geta-90, -1):
        Grid[i][j] += Grid[i+1][j]


lai = len(Aint)
ans = 0
for i2, i5 in i25:
    ans += Grid[geta-i2][geta-i5]
    #print(i2, i5, Grid[geta-i2][geta-i5])
print((ans-lai)//2)

### FIXED CODE ###

import sys
readline = sys.stdin.readline

G = 10**10
lai = 0
def Decimal(x):
    global lai
    a = x.strip().split('.')
    if len(a) == 1 or all([ai == '0' for ai in a[1]]):
        lai += 1
        return int(a[0])*G
        
    lf = len(a[1])
    i, f = map(int, a)
    return (i*10**(lf) + f)*10**(10-lf)
    
    
N = int(readline())
A = [Decimal(readline()) for _ in range(N)]

H = 200
geta = 100
Grid = [[0]*H for _ in range(H)]
i25 = []


for af in A:
    i2 = -10
    i5 = -10
    while af%2 == 0:
        af //= 2
        i2 += 1
    while af%5 == 0:
        af //= 5
        i5 += 1
    i25.append((i2, i5)) 


for i2, i5 in i25:
    Grid[geta+i2][geta+i5] += 1

for i in range(geta+90, geta-90, -1):
    for j in range(geta+90, geta-90, -1):
        Grid[i][j] += Grid[i][j+1]

for j in range(geta+90, geta-90, -1):
    for i in range(geta+90, geta-90, -1):
        Grid[i][j] += Grid[i+1][j]


ans = 0
for i2, i5 in i25:
    ans += Grid[geta-i2][geta-i5]
    #print(i2, i5, Grid[geta-i2][geta-i5])
print((ans-lai)//2)
### BUGGY CODE ###

a="PD"*100000+"P"
s=input()
n=len(s)
r=""
c=0
for i in range (n):
    if s[i]=='?':
        r+="D"
    else:
        r+=s[i]
print(r)

### FIXED CODE ###

s=input()
print(s.replace("?", "D"))
### BUGGY CODE ###



import numpy as np
N,K=map(int,input().split())
A=list(map(int,input().split()))

A=np.array(A)

A_pos=np.sort(A[A>0])
A_neg=np.sort(A[A<0])
A_neg2=np.sort(-A_neg.copy())
nz=len(A[A==0])
np=len(A_pos)
nn=len(A_neg)
n_post=np*(np-1)//2+(nn*(nn-1))//2
n_zero=nz*(np+nn)+nz*(nz-1)//2
n_neg=np*nn

#array内で積がx未満になるペアの数
def syakutori_pos(x,array):
    n=len(array)
    res=0
    j=n-1
    for i in range(n):
        tmp=0
#         j=n-1
        y=-(-x//array[i])
        while j!=-1:
            
            if array[j]>=y:
                j-=1
            else:
                break
        
        tmp+=j+1
        if array[i]**2<x:
            tmp-=1

            
        res+=tmp
    res=res//2
    return res



#array内で積がx未満になるペアの数
def syakutori_neg(x):
    y=x//A_neg
#     print(A_pos,y)
    res=0
    i=0
    j=np-1
    for z in reversed(y):
        while(j!=-1):
            if z<A_pos[j]:
                j-=1
            else:
                break
#         print(z,j+1)
        res+=j+1
    return np*nn-res



def syakutori(x):
    if x>0:
        return syakutori_pos(x,A_pos)+syakutori_pos(x,A_neg2)+n_neg+n_zero
    elif x==0:
        return n_neg
    else:
        return syakutori_neg(x)




r=10**18
l=-10**18
while(r-l>1):
    mid=(l+r)//2
    z=syakutori(mid)
#     z= count_pair(mid)
#     print(l,r)
    if z < K:
        l=mid
    else:
        r=mid
print(l)

### FIXED CODE ###

import numpy as np
N,K=map(int,input().split())
A=list(map(int,input().split()))

A=np.array(A)

A_pos=np.sort(A[A>0])
A_neg=np.sort(A[A<0])
A_neg2=-A_neg[::-1]
n_pos=len(A_pos)
n_neg=len(A_neg)
n_zero=N-n_pos-n_neg

def position_in_neg(x):
    y=n_pos-np.searchsorted(A_pos,x//A_neg,side='right')
    return y.sum()

def position_in_pos(x):
    z=np.searchsorted(A_pos,-(-x//A_pos),side='left')
    w=np.searchsorted(A_neg2,-(-x//A_neg2),side='left')
    tmp=len(A_pos[A_pos**2<x])+len(A_neg2[A_neg2**2<x])
    return (z.sum()+w.sum()-tmp)//2

def position(x):
    if x<0:
        return position_in_neg(x)
    elif x==0:
        return n_pos*n_neg
    else:
        return position_in_pos(x)+n_pos*n_neg+(n_pos+n_neg)*n_zero+n_zero*(n_zero-1)//2

l=-pow(10,18)
r=pow(10,18)
while(r-l>1):
    mid=(l+r)//2
    if position(mid)<K:
        l=mid
    else:
        r=mid
print(l)
### BUGGY CODE ###

import sys
import os


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

    a, *ret = sys.stdin.readline().rstrip()
    ret.insert(0, a)
    Q = int(sys.stdin.readline().rstrip())

    for q in range(Q):
        line = sys.stdin.readline().split()
        if line[0] == '1':
            ret.reverse()
        elif line[0] == '2' and line[1] == '1':
            ret.insert(0, line[2])
        else:
            ret.append(line[2])

    print("".join(ret))



if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import os


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

    ret = sys.stdin.readline().rstrip()
    Q = int(sys.stdin.readline().rstrip())
    m = ""
    u = ""
    r = 0
    for q in range(Q):
        line = sys.stdin.readline().split()
        if line[0] == '1':
            m, u = u, m
            r ^= 1
        elif line[0] == '2' and line[1] == '1':
            m += line[2]
        else:
            u += line[2]

    if r == 0:
        print(m[::-1] + ret[::1] + u)
    else:
        print(m[::-1] + ret[::-1] + u)


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

import numpy as np

def seachPrimeNum(N):
    max = int(np.sqrt(N))
    seachList = [i for i in range(2,N+1)]
    primeNum = []
    while seachList[0] <= max:
        primeNum.append(seachList[0])
        tmp = seachList[0]
        seachList = [i for i in seachList if i % tmp != 0]
    primeNum.extend(seachList)
    return primeNum

#def numsearch(list):
    #for i in list:
        #print(i)
        #if (i+1)/2 not in list:
            #list.remove(i)
    #return list

def main():
    Q = int(input())
    list = seachPrimeNum(100000)
    #list2 = numsearch(list)
    #print(list2)
    c = [0]*100001
    c[0] = 0
    for i in range(1,100001,1):
        #print(i)
        if i in list and (i+1)/2 in list:
            c[i] = c[i-1]+1
        else:
            c[i] = c[i-1]
    #print(c)
    for i in range(Q):
        l,r = map(int,input().split())
        print(c[r]-c[l-1])

main()


### FIXED CODE ###

import numpy as np

def seachPrimeNum(N):
    max = int(np.sqrt(N))
    seachList = [i for i in range(2,N+1)]
    primeNum = []
    while seachList[0] <= max:
        primeNum.append(seachList[0])
        tmp = seachList[0]
        seachList = [i for i in seachList if i % tmp != 0]
    primeNum.extend(seachList)
    return primeNum

#def numsearch(list):
    #for i in list:
        #print(i)
        #if (i+1)/2 not in list:
            #list.remove(i)
    #return list

def main():
    Q = int(input())
    list = seachPrimeNum(100000)
    #フラグを立てるよ
    check = [0]*100001
    primeCheck = [0]*100001
    for i in list:
        primeCheck[i] = 1
    for i in list:
        if i == 2:
            continue
        tmp = int((i+1)/2)
        if primeCheck[tmp] == 1:
            check[i] = 1
    #答えを求めるための累積和
    c = [0]*100001
    c[0] = 0
    for i in range(1,100001,1):
        #print(i)
        if check[i] == 1:
            c[i] = c[i-1]+1
        else:
            c[i] = c[i-1]
    #print(c)
    for i in range(Q):
        l,r = map(int,input().split())
        print(c[r]-c[l-1])

main()
### BUGGY CODE ###

# -*- coding: utf-8 -*-
# モジュールのインポート
import math

# 標準入力の取得
N, K = list(map(int, input().split()))
A = list(map(int, input().split()))

# 求解処理
to = [A]
# ダブリング表の作成
for i in range(math.ceil(math.log2(K))):
    to_i = to[i]
    to_next = []
    for j in range(N):
        to_next.append(to_i[to_i[j]-1])

    to.append(to_next)

result = 1
for i in range(math.ceil(math.log2(K))):
    if ((K >> i) & 1):
        result = to[i][result-1]


print(result)


### FIXED CODE ###

# -*- coding: utf-8 -*-
# モジュールのインポート
import math


def get_input() -> tuple:
    """
    標準入力の取得

    Returns:\n
        tuple: 標準入力
    """
    N, K = list(map(int, input().split()))
    A = list(map(int, input().split()))

    return N, K, A


def main(N: int, K: int, A: list) -> None:
    """
    求解処理.

    Args:
        N (int): 町の数
        K (int): テレポーターの使用回数
        A (list): テレポーターの転送先
    """
    # タブリング表の作成
    to = [A]
    for i in range(math.ceil(math.log2(K))):
        to_i = to[i]
        to_next = []
        for j in range(N):
            to_next.append(to_i[to_i[j]-1])

        to.append(to_next)

    result = 1
    for i in range(math.ceil(math.log2(K))):
        if ((K >> i) & 1):
            result = to[i][result-1]

    print(result)


if __name__ == "__main__":
    N, K, A = get_input()
    main(N, K, A)
### BUGGY CODE ###

import math
import sys
import os
from operator import mul

sys.setrecursionlimit(10**7)

def _S(): return sys.stdin.readline().rstrip()
def I(): return int(_S())
def LS(): return list(_S().split())
def LI(): return list(map(int,LS()))

if os.getenv("LOCAL"):
    inputFile = basename_without_ext = os.path.splitext(os.path.basename(__file__))[0]+'.txt'
    sys.stdin = open(inputFile, "r")
INF = float("inf")

N = I()
S = list(_S())
ans = 0

for i in range(N):
    for j in range(i,N):
        for k in range(j,N):
            if S[i]==S[j]:
                continue
            if S[i]==S[k] or S[j]==S[k]:
                continue
            if (j-i) == (k-j):
                continue
            ans += 1

print(ans)

# R G B
# R B G
# G B R
# G R B
# B G R
# B R G

# i   j   k
#  - != -

# RBRBGRBGGB
# 1122233333
# 0000111233
# 0112223334

# B*3
# G*4

### FIXED CODE ###

import math
import sys
import os
from operator import mul
import bisect

sys.setrecursionlimit(10**7)

def _S(): return sys.stdin.readline().rstrip()
def I(): return int(_S())
def LS(): return list(_S().split())
def LI(): return list(map(int,LS()))

if os.getenv("LOCAL"):
    inputFile = basename_without_ext = os.path.splitext(os.path.basename(__file__))[0]+'.txt'
    sys.stdin = open(inputFile, "r")
INF = float("inf")

N = I()
S = list(_S())
ans = 0

r = []
g = []
b = []

for i,s in enumerate(S):
    if s == 'R':
        r.append(i)
    if s == 'G':
        g.append(i)
    if s == 'B':
        b.append(i)

# j = bisect.bisect_right(<list>,<value>)
# print(r)
# print(g)
# print(b)

# for i in r:
#     for j in g:
#         for k in b:
#             tmp = sorted([i,j,k])
#             if not tmp[1]-tmp[0]==tmp[2]-tmp[1]:
#                 ans += 1

ans = len(r)*len(g)*len(b)

for i in range(N):
    for j in range(i,N):
        k = j + (j-i)
        if k > N-1:
            break
        if S[i]==S[j]:
            continue
        if S[i]==S[k] or S[j]==S[k]:
            continue
        ans -= 1

print(ans)

# R G B
# R B G
# G B R
# G R B
# B G R
# B R G

# i   j   k
#  - != -

# RBRBGRBGGB
# 1122233333
# 0000111233
# 0112223334

# B*3
# G*4

# GB系: (2,4), (4,5)
# RB系: (1,3),
### BUGGY CODE ###

n = int(input())

a = [int(input()) - 1 for _ in range(n)]

i = 0
count = 0

while(1):
  i = a[i]
  count += 1
  if i == 1:
    break
  elif i == a[i]:
    count = -1
    break
  
print(count)

### FIXED CODE ###

n = int(input())

a = [int(input()) - 1 for _ in range(n)]

i = 0
count = 0

for _ in range(n+1):
  i = a[i]
  count += 1
  if i == 1:
    break

if count == n + 1:
  count = -1
  
print(count)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
ans = 0
for i in range(N):
    if i == 0:
        ans += A[i]
    else:
        ans *= A[i]
        if ans > 10**18:
            ans *= -1
        if A[i] == 0:
            ans = 0
            break

if ans < 0:
    ans = -1
print(ans)

### FIXED CODE ###

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

if 0 in A:
    print(0)
else:
    ans = A[0]
    for i in range(N-1):
        ans *= A[i+1]
        if ans > 10**18:
            ans = -1
            break
    print(ans)
### BUGGY CODE ###

n = int(input())
l_a = list(map(int, input().split()))
ans = []
q = int(input())
for _ in range(q) :
    b, c = map(int, input().split())
    for i in range(n) :
        if l_a[i] == b :
            l_a[i] = c
    ans.append(sum(l_a))

for value in ans :
    print(value)


### FIXED CODE ###

import collections

n = int(input())
l_a = list(map(int, input().split()))
col = collections.Counter(l_a)
bef = sum(l_a)
q = int(input())
ans = []
for _ in range(q) :
    b, c = map(int, input().split())
    bef += (c - b)*col[b]
    ans.append(bef)
    col[c] += col[b]
    col[b] = 0

for value in ans :
    print(value)
### BUGGY CODE ###

n,q = map(int,input().split())
s = input()
count = 0
for i in range(q):
  l,r = input().split()
  l = int(l)
  r = int(r)
  t = s[l-1:r]
  count = t.count("AC")
  print(count)

### FIXED CODE ###

n,q = map(int,input().split())
s = input()
s_count = [0]
for i in range(len(s)):
  if s[i:i+2] == "AC":
    s_count.append(s_count[i] + 1)
  else:
    s_count.append(s_count[i])

for i in range(q):
  l,r = map(int,input().split())
  count = s_count[r-1] - s_count[l-1]
  print(count)
### BUGGY CODE ###

from collections import defaultdict

def getlist():
	return list(map(int, input().split()))

H, W, N = getlist()
D = defaultdict(int)
D[0] += (H - 2) * (W - 2)
L = []
for i in range(N):
	a, b = getlist()
	for j in range(3):
		for k in range(3):
			if H - 2 >= a - j and a - j >= 1 and W - 2 >= b - k and b - k >= 1:
				L.append([a - j, b - k])

L = sorted(L)
n = len(L)
if n != 0:
	v = L[0]
c = 0
for i in range(n):
	if v == L[i]:
		c += 1
	else:
		D[c] += 1
		c = 1
	v = L[i]

if n != 0:
	D[c] += 1
for i in range(1, 10):
	D[0] -= D[i]

for i in range(10):
	print(D[i])

### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline

from collections import defaultdict

def getlist():
	return list(map(int, input().split()))

H, W, N = getlist()
D = defaultdict(int)
D[0] += (H - 2) * (W - 2)
L = []
for i in range(N):
	a, b = getlist()
	for j in range(3):
		for k in range(3):
			if H - 2 >= a - j and a - j >= 1 and W - 2 >= b - k and b - k >= 1:
				L.append((a - j, b - k))

L = sorted(L)
n = len(L)
if n != 0:
	v = L[0]
c = 0
for i in range(n):
	if v == L[i]:
		c += 1
	else:
		D[c] += 1
		c = 1
	v = L[i]

if n != 0:
	D[c] += 1
for i in range(1, 10):
	D[0] -= D[i]

for i in range(10):
	print(D[i])
### BUGGY CODE ###

import numpy as np


def solve(s):
    MOD = 10 ** 9 + 7
    dp = np.zeros(13, dtype=np.int64)
    dp[0] = 1
    idx = np.zeros(13, dtype=np.int8)
    for i in range(13):
        idx[i * 10 % 13] = i
    window = np.ones(10, dtype=np.int8)
    for c in s:
        if c == '?':
            ndp = np.convolve(dp[idx], window, mode='full')
            dp = ndp[:13]
            dp[:9] += ndp[13:]
            dp %= MOD
        else:
            dp = np.roll(dp[idx], int(c))
    return dp[5]


s = input()
print(solve(s))


### FIXED CODE ###

import numpy as np


def solve(s):
    MOD = 10 ** 9 + 7
    dp = np.zeros(13, dtype=np.int64)
    dp[0] = 1
    idx = np.zeros(13, dtype=np.int8)
    for i in range(13):
        idx[i * 10 % 13] = i
    window = np.ones(10, dtype=np.int8)
    for c in s:
        if c == '?':
            tdp = dp[idx]
            ndp = np.concatenate([tdp[4:], tdp])
            dp = np.convolve(ndp, window, mode='valid') % MOD
        else:
            dp = np.roll(dp[idx], int(c))
    return dp[5]


s = input()
print(solve(s))
### BUGGY CODE ###

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

    color = [-1] * N
    color[0] = 0
    stack = [0]
    while stack:
        v = stack.pop()
        for to in range(N):
            if S[v][to] == '0': continue
            if color[to] >= 0:
                if color[to] == color[v]:
                    print(-1)
                    exit()
                continue
            stack.append(to)
            color[to] = color[v]^1

    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])
    print(max(max(d) for d in D) + 1)

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())
A = list(map(int, input().split()))

for i in range(N):
  A[i] -= i

ans = sum(list(
  A[i+1:].count(-A[i] - 2 * i) for i in range(N)
))
  
print(ans)

### FIXED CODE ###

from collections import deque, Counter

N = int(input())

A = [
  int(j) - i  for i, j in enumerate(input().split())
]
cnt_A = Counter(A)

ans = 0
d = deque(A)
for i in range(N):
  a = d.popleft()
  #c = d.count(-a - 2 * i)
  c = cnt_A[-a - 2 * i]
  ans += c
print(ans)
### BUGGY CODE ###

n,m=map(int, input().split())
an=[int(i)//2 for i in input().split()]
ma=max(an)
count=0
q=1
while m>=ma*q:
    for ak in an:
        if (ma*q)%ak==0 and ((ma*q)//ak)%2==1:
            plus=1
        else:
            plus=0
            break
    q+=2
    if plus==1:
        count+=1
print(count)

### FIXED CODE ###

n,m=map(int, input().split())
an=[int(i) for i in input().split()]
import fractions
ans=an[0]
for i in range(1, n):
    ans = ans * an[i] // fractions.gcd(ans, an[i])

def count2(i):
    if i%2==0:
        c=0
        while i%2==0:
            i//=2
            c+=1
        return c
    else:
        return 0
    
c2=count2(ans)

for ak in an:
    if ak%(2**c2)==0:
        d=1
        pass
    else:
        d=0
        break

if d==0:
    print(0)
else:
    lca=ans//2
    if (m//lca)%2==0:
        print((m//lca)//2)
    else:
        print(((m//lca)+1)//2)
### BUGGY CODE ###

k, s = map(int, input().split())
ans = 0
for x in range(min(s, k) + 1):
    for y in range(min(s-x, k) + 1):
        for z in range(min(s-x-y, k) + 1):
            if x + y + z == s:
                ans += 1
else:
    print(ans)

### FIXED CODE ###

k, s = map(int, input().split())
ans = 0
for x in range(k+1):
    for y in range(k+1):
        z = s - x - y
        if 0 <= z <= k:
            ans += 1
else:
    print(ans)
### BUGGY CODE ###

K = int(input())

def gcd(a,b):
    mod = max(a,b) % min(a,b)
    if mod == 0:
        temp = min(a,b)
        return temp
    if a >= b:
        a = mod
    else:
        b = mod
    return gcd(a, b)

ans = 0
for a in range(1,K+1):
    for b in range(1, K+1):
        ab = gcd(a,b)
        for c in range(1, K+1):
            ans += gcd(ab, c)

print(ans)


### FIXED CODE ###

K = int(input())

def gcd(a,b):
    if a % b == 0:
        return b
    return gcd(b, a%b)

dec = {}
for a in range(1,K+1):
    for b in range(1, K+1):
        if gcd(a,b) not in dec:
            dec[gcd(a,b)] = 1
        else:
            dec[gcd(a,b)] += 1
ans = 0
for c in range(1, K+1):
    for key in dec.keys():
        ans += gcd(c, key)*dec[key]

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

#D

line = [int(x) for x in input().split()]
n = line[0]
x = line[1]
y = line[2]

results =[0]*(n+2)

for i in range(1, n+1):
    for j in range(i,n+1):
        results[min([abs(j-i), abs(x-i) + 1 + abs(j-y), abs(y-i) + 1 + abs(j-x)])] = results[min([abs(j-i), abs(x-i) + 1 + abs(j-y)])] + 1

for i in range(1, n):
    print(results[i])



### FIXED CODE ###

#D

line = [int(x) for x in input().split()]
n = line[0]
x = line[1]
y = line[2]

results =[0]*(n+2)

for i in range(1, n):
    for j in range(i+1,n+1):
        results[min([abs(j-i), abs(x-i) + 1 + abs(j-y)])-1] += 1

for i in range(0, n-1):
    print(results[i])
### BUGGY CODE ###

def f_c():
    n = int(input())
    s = input()

    stack, c = 1, 1
    for si in s[1:]:
        if si=="B":
            if stack%2==0:
                stack += 1
            else:
                c *= stack
                stack -= 1
        else:
            if stack%2==0:
                c *= stack
                stack -= 1
            else:
                stack += 1
        c %= (10**9+7)
    if stack!=0 or c==0:
        print(0)
    else:
        for i in range(1, n+1):
            c*=i
        print(c%(10**9+7))

if __name__ == "__main__":
    f_c()


### FIXED CODE ###

# import sys
# input = sys.stdin.readline
Q = 10**9+7
def main():
    N = int( input())
    S = input()
    left = 0
    ans = 1
    # for i in range(N*2):
    #     s = S[i]
    for s in S:
        if s == "B":
            if left%2 == 0:
                left += 1
            else:
                ans *= left
                left -= 1
        else:
            if left%2 == 1:
                left += 1
            else:
                ans *= left
                left -= 1
        ans %= Q
    if left > 0 or ans == 0:
        print(0)
        return
    for i in range(1,N+1):
        ans *= i
        ans %= Q
    print(ans)
if __name__ == '__main__':
    main()