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

def prime_factor(n):
    factors = []
    for i in range(2,int(n**0.5)+1):
        while n%i==0:
            factors.append(i)
            n = n//i
    if n!=1:
        factors.append(n)
    return factors

N = int(input())
li = prime_factor(N)
a = len(li)
ans = []
for i in range(2**a):
    tmp1 = 1
    tmp2 = 1
    for j in range(a):
        if ((i >> j) & 1):
            tmp1 *= li[j]
        else:
            tmp2 *= li[j]
    ans.append(max(len(str(tmp1)),len(str(tmp2))))
print(min(ans))

### FIXED CODE ###

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

N = int(input())
list =  make_divisors(N)
ans = 10**9
if len(list)%2==1:
    list.append(list[-1])
for i in range(0,len(list),2):
    tmp1 = len(str(list[i]))
    tmp2 = len(str(list[i+1]))
    ans = min(ans,max(tmp1,tmp2))
print(ans)
### BUGGY CODE ###

import heapq
N, A = map(int, input().split())
X = [int(x) - A for x in input().split()]
Xp = []
Xm = []
X0 = []
for x in X:
  if x > 0:
    Xp.append(x)
  elif x < 0:
    Xm.append(-x)
  else:
    X0.append(x)
limit = min(sum(Xp), sum(Xm))
Xp = [x for x in Xp if x <= limit]
Xm = [x for x in Xm if x <= limit]
R = [[[0, 0]], [[0, 0]]]
def c(X, k):
  Q = []
  heapq.heappush(Q, 0)
  for x in X:
    _Q = []
    while Q:
      q = heapq.heappop(Q)
      if q > limit:
        break
      heapq.heappush(_Q, q)
      heapq.heappush(_Q, q + x)
    Q = _Q
  preq = 0
  while Q:
    q = heapq.heappop(Q)
    if q > limit:
      break
    if q == preq:
      R[k][-1][1] += 1
    else:
      R[k].append([q, 1])
    preq = q
c(Xp, 0)
c(Xm, 1)
cx = 0
while R[0] and R[1]:
  if R[0][0][0] < R[1][0][0]:
    R[0] = R[0][1:]
  elif R[0][0][0] > R[1][0][0]:
    R[1] = R[1][1:]
  else:
    cx += R[0][0][1] * R[1][0][1]
    R[0] = R[0][1:]
    R[1] = R[1][1:]
print(cx * (2 ** len(X0)) - 1)

### FIXED CODE ###

from collections import Counter
N, A = map(int, input().split())
X = [int(x) - A for x in input().split()]
C = Counter([0])
for x in X:
  tmp = Counter()
  for i, c in C.items():
    tmp[i + x] += c
  C += tmp
print(C[0] - 1)
### BUGGY CODE ###

from operator import itemgetter
N= int(input())
ans = 1
a = []

for i in range(N):
    tmpa, tmpb = map(int,input().split())
    if tmpa-tmpb in a:
        a[tmpa-tmpb].append(tmpa+tmpb)
    else:
        a.append([tmpa-tmpb,tmpa+tmpb])

a.sort(key=itemgetter(1))
tmp = a[0][1]
for i in range(1, N):
    if a[i][0] >= tmp:
        ans += 1
        tmp = a[i][1]
print(ans)


### FIXED CODE ###

from operator import itemgetter
N= int(input())
ans = 1
a = []

for i in range(N):
    tmpa, tmpb = map(int,input().split())
    a.append([tmpa+tmpb, tmpa-tmpb])

a.sort()
    
tmp = a[0][0]
for i in range(1, N):
    if a[i][1] >= tmp:
        ans += 1
        tmp = a[i][0]
print(ans)
### BUGGY CODE ###

n = int(input())
s = list(input())
r_pos = []
g_pos = []
b_pos = []

for i in range(n):
    st = s[i]
    if st == "R":
        r_pos.append(i)

    if st == "G":
        g_pos.append(i)

    if st == "B":
        b_pos.append(i)

r_num = len(r_pos)
g_num = len(g_pos)
b_num = len(b_pos)


ans = r_num * g_num * b_num
for r in r_pos:
    for g in g_pos:
        x, y = min(r, g), max(r, g)

        dif = y - x
        left_pos = x - dif
        right_pos = y + dif
        mid_pos = 4000
        if dif % 2 == 0:
            mid_pos = x + dif // 2

        left = 0
        right = 0
        mid = 0
        if left_pos in b_pos:
            left = 1
        if right_pos in b_pos:
            right = 1
        if mid_pos in b_pos:
            mid = 1

        ans -= left + right + mid

print(ans)


### FIXED CODE ###

n = int(input())
s = list(input())
r_pos = []
g_pos = []
b_pos = []

for i in range(n):
    st = s[i]
    if st == "R":
        r_pos.append(i)

    if st == "G":
        g_pos.append(i)

    if st == "B":
        b_pos.append(i)

colors = [r_pos, g_pos, b_pos]
if len(colors[0]) > len(colors[1]):
    colors[0], colors[1] = colors[1], colors[0]
if len(colors[0]) > len(colors[2]):
    colors[0], colors[2] = colors[2], colors[0]
if len(colors[1]) > len(colors[2]):
    colors[1], colors[2] = colors[2], colors[1]

x_num, y_num, z_num = len(colors[0]), len(colors[1]), len(colors[2])

ans = x_num * y_num * z_num
c = set(colors[2])
for a in colors[0]:
    for b in colors[1]:
        x, y = min(a, b), max(a, b)

        dif = y - x
        left_pos = x - dif
        right_pos = y + dif
        mid_pos = 4000
        if dif % 2 == 0:
            mid_pos = x + dif // 2

        left = 0
        right = 0
        mid = 0
        if left_pos in c:
            left = 1
        if right_pos in c:
            right = 1
        if mid_pos in c:
            mid = 1

        ans -= left + right + mid

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

def main():
  n = int(input())
  dict = {}
  for i in range(n):
    s = input()
    if s not in dict:
      dict[s] = 1
    else:
      dict[s] += 1
  max_name = sorted([kv[0] for kv in dict.items() if kv[1] == max(dict.values())])
  for name in max_name:
    print(name)


if __name__ == '__main__':
  main()

### FIXED CODE ###

def main():
  n = int(input())
  dict = {}
  for i in range(n):
    s = input()
    dict.setdefault(s, 0)
    dict[s] += 1
  max_val = 0
  ans_ls = []
  for kv in dict.items():
    if kv[1] > max_val:
      max_val = kv[1]
      ans_ls = [kv[0]]    
    elif kv[1] == max_val:
      ans_ls.append(kv[0])
  ans_ls = sorted(ans_ls)
  for name in ans_ls:
    print(name)
 
 
if __name__ == '__main__':
  main()
### BUGGY CODE ###

import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
mod = 10**9 + 7
inf = float('inf')
ans = int(0)

S = str(input())
N = len(S)
M = 13
c = [0]*(N)
for i in range(N):
#    c[i] = (10**i)%M
    c[i] = pow(10,i,M)
#print(c)
c.reverse()
#print(c)
"""
dp = [[0]*M for _ in range(N+1)]
i = int(0)
for j in range(M):
    dp[0][j] = 1
for s in S:
    if s == "?":
        for l in range(10):
            m = l * c[i] % M
            dp[i+1][(M - m) % M] += dp[i][j]
    else:
        m = int(s) * c[i] % M
        dp[i][(M - m) % M] +=dp[i][j]
    i +=1
"""
dp = [[0]*M for _ in range(N)]
if S[0] == "?":
    for l in range(10):
        m = l * c[0]%M
        dp[0][m] += 1
else:
    m = int(S[0]) * c[0]%M
    dp[0][m] = 1
S = S[1:]
i = int(1)
for s in S:
    if s == "?":
        for j in range(M):
            for l in range(10):
                m = l*c[i]%M
                dp[i][j] += dp[i-1][(M+j-m)%M]
    else:
        for j in range(M):
            m = int(s)*c[i]%M
            dp[i][j] = dp[i-1][(M+j-m)%M]
    i +=1

"""
dp = [[0]*M for _ in range(N)]
if S[0] == "?":
    for l in range(10):
        m = l * c[0]%M
        dp[0][m] += 1
else:
    m = int(S[0]) * c[0]%M
    dp[0][m] = 1

for i in range(1,N):
    if S[i] == "?":
        for j in range(M):
            for l in range(10):
                m = l*c[i]%M
                dp[i][j] += dp[i-1][(M+j-m)%M]
    else:
        for j in range(M):
            m = int(S[i])*c[i]%M
            dp[i][j] = dp[i-1][(M+j-m)%M]
"""
#print(dp)
print(dp[N-1][5]%mod)




### FIXED CODE ###

import sys
 
 
def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    s = str(input().rstrip('\n'))
    ls = [[0] * 13 for _ in range(len(s))]
    for i in range(len(s)):
        if i == 0:
            if s[-i-1] == "?":
                for j in range(10):
                    ls[i][j] += 1
            else:
                ls[i][int(s[-i-1])] += 1
        else:
            mult = pow(10, i, 13)
            if s[-i-1] == "?":
                for j in range(13):
                    for k in range(10):
                        ls[i][(k * mult + j) % 13] += ls[i-1][j]
            else:
                st = int(s[-i-1])
                for j in range(13):
                    ls[i][(st * mult + j) % 13] += ls[i-1][j]
        for j in range(13):
            ls[i][j] = ls[i][j] % mod
    print(ls[-1][5])
 
 
if __name__ == '__main__':
    solve()
### BUGGY CODE ###

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

ans = 'IMPOSSIBLE'
for i in abl:
    if i[0] == 1 and [i[1],N] in abl:
        ans = 'POSSIBLE'
        print(ans)
        exit()
print(ans)


### FIXED CODE ###

N, M = map(int, input().split())

abl1 = set()
abl2 = set()
for _ in range(M):
    ab = list(map(int,input().split()))
    if ab[0] == 1:
        abl1.add(ab[1])
    elif ab[1] == N:
        abl2.add(ab[0])


for i in abl1:
   if i in abl2:
       print("POSSIBLE")
       exit()
print("IMPOSSIBLE")
### BUGGY CODE ###

from itertools import groupby

N,K=map(int,input().split())
S=input()
def condition(num):
    flag=0
    for i in range(0,N-num+1):
        test=[]
        count=0
        for j in range(i,i+num):
            test.append(int(S[j]))
        test=groupby(test)
        for key,group in test:
            if key==0:
                count+=1
        if K>=count:
            flag=1
    return flag==1
start=1
end=N
while end-start>1:
    test=(end+start)//2
    if condition(test):
        start=test
    else:
        end=test
if condition(end):
    print(end)
else:
    print(start)

### FIXED CODE ###

from itertools import groupby

N,K=map(int,input().split())
S=input()
def condition(num):
    flag=0
    first=[int(S[i]) for i in range(0,N-num+1)]
    last=[int(S[i+num-1]) for i in range(0,N-num+1)]
    test=[]
    for i in range(0,num):
        test.append(int(S[i]))
    sub=groupby(test)
    count=0
    for key,group in sub:
        if key==0:
            count+=1
    if K>=count:
        flag=1
    for i in range(1,N-num+1):
        if first[i-1]==0 and first[i]==1:
            count-=1
        if last[i-1]==1 and last[i]==0:
            count+=1
        if K>=count:
            flag=1
    return flag==1
start=1
end=N
while end-start>1:
    test=(end+start)//2
    if condition(test):
        start=test
    else:
        end=test
if condition(end):
    print(end)
else:
    print(start)
### BUGGY CODE ###

a,b,c,d = map(int,input().split())
if c > d:
    a,b = b,a
    c,d = d,c


dp = [[1 for i in range(d+1)] for j in range(c+1)]
dp[0][0] = 0

mod = 10**9+7
#print(dp)
ans = 0
for i in range(1,c+1):
    for j in range(i,d+1):
        dp[i][j] = (dp[i-1][j] + dp[i][j-1])%mod
        if j<=c:
            dp[j][i] = dp[i][j]
        # if i >= a and j >= b:
        #     ans += dp[i][j]
        #     if i>=b and j >=a:
        #         ans += dp[i][j]

# print(ans%mod)


ans = 0
for i in range(a,c+1):
    for j in range(b,d+1):
        ans += dp[i][j]
        ans %=mod
        #print(dp[i+1][j+1])
#print(dp)
print(ans%mod)

### FIXED CODE ###

p = 10 ** 9 + 7 # mod
N = (10 ** 6) * 2 + 10  # N は必要分だけ用意する
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

def cmb(r, n, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

a = list(map(int,input().split()))
ans = cmb(a[2]+1,a[2]+a[3]+2,p) - cmb(a[1],a[2]+a[1]+1,p) - cmb(a[0],a[3]+a[0]+1,p) + cmb(a[0],a[0]+a[1],p)
print(ans%p)
### BUGGY CODE ###

import numpy as np
from collections import Counter
n = int(input())
A = np.array(list(map(int, input().split())))
C = Counter(A)
A = np.sort(A)
c = 0
while len(A) > 0:
    ai = A[0]
    AL = A[1:]
    if C[ai] == 1:
        c += 1
    mask = AL % ai != 0
    A = AL[mask]
print(c)


### FIXED CODE ###

from collections import Counter
n = int(input())
A = tuple(map(int, input().split()))
C = Counter(A)
A = list(set(A))
ok = [True] * (10**6+1)

for a in A:
    temp = a+a
    while temp < 10**6+1:
        ok[temp] = False
        temp += a

c = 0
for a in A:
    if C[a] == 1 and ok[a] == True:
        c += 1
print(c)
### BUGGY CODE ###


def q3():
    import math
    k = int(input())
    sum_n = 0
    gcd_2_dict = {}

    def gcd(n1, n2):
        if n1 < n2:
            sorted_nums = tuple([n1, n2])
        else:
            sorted_nums = tuple([n2, n1])
        if sorted_nums in gcd_2_dict:
            return gcd_2_dict[sorted_nums]
        gcd_num = math.gcd(n1, n2)
        gcd_2_dict[sorted_nums] = gcd_num
        return gcd_num

    for a in range(1, k + 1):
        for b in range(1, k + 1):
            for c in range(1, k + 1):
                sorted_nums = sorted([a, b, c])
                sum_n += gcd(gcd(sorted_nums[0], sorted_nums[1]), sorted_nums[2])

    print(sum_n)

q3()

### FIXED CODE ###


from math import gcd

K = int(input())

a = 0
for ai in range(1, K + 1):
  for bi in range(1, K + 1):
    gcd_ab = gcd(ai, bi)
    for ci in range(1, K + 1):
      a += gcd(gcd_ab, ci)

print(a)
### BUGGY CODE ###

ls = []
for i in range(int(input())):
    command, text = input().split()
    if command == "insert":
        ls.append(text)
    else:
        print("yes" if text in ls else "no")

### FIXED CODE ###

dic = {}
line = []
for i in range(int(input())):
    line.append(input().split())
for i in line:
    if i[0][0] == "i":
        dic[i[1]] = None
    else:
        print("yes" if i[1] in dic else "no")
### BUGGY CODE ###

from collections import deque

def pr(A,n):
    for i in range(n):
        if i!=n-1:
            print(A[i],end=" ")
        else:
            print(A[i])

n=int(input())
que_r=deque()

for i in range(n):
    s=input().split()

    if s[0]=="insert":
        que_r.appendleft(int(s[1]))
    elif s[0]=="delete" and que_r.count(int(s[1]))>=1:
        que_r.remove(int(s[1]))
    elif s[0]=="deleteFirst":
        gav=que_r.popleft()
    elif s[0]=="deleteLast":
        gav=que_r.pop()

pr(que_r,len(que_r))


### FIXED CODE ###

from collections import deque


n=int(input())
que_r=deque()

for i in range(n):
    s=input()
    l=len(s)
    if s[0]=="i":
        que_r.appendleft(s[7:])
    elif s[6]==" ":
        try:
            que_r.remove(s[7:])
        except: pass
    elif l>10:
        que_r.popleft()
    elif l>6:
        que_r.pop()

print(*que_r)
### BUGGY CODE ###

from decimal import *
from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush,heappop
import math
from collections import *
from functools import reduce,cmp_to_key
import sys
input = sys.stdin.readline

M = mod = 998244353
def factors(n):return sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))
def inv_mod(n):return pow(n, mod - 2, mod)

def li():return [int(i) for i in input().rstrip('\n').split()]
def st():return input().rstrip('\n')
def val():return int(input().rstrip('\n'))
def li2():return [i for i in input().rstrip('\n')]
def li3():return [int(i) for i in input().rstrip('\n')]
def li4():return [float(i) for i in input().rstrip('\n').split(' ')]

n = val()
l = li4()
mihe = n//2 + 1


dp = [[0 for i in range(n)] for j in range(n + 1)]
sumarray = [1 for i in range(n + 1)]



for i in range(n-1,-1,-1):
    for j in range(n-1,i - 1,-1):
        dp[i][j] = round(( l[i] / (1 - l[i]) ) * sumarray[j + 1],10)

    for j in range(n):
        if sumarray[j] != 1:
            sumarray[j] = round(sumarray[j] + dp[i][j],10)
        else:
            sumarray[j] = round(dp[i][j],10)



# for i in dp:print(*i)
# print(*sumarray)

curr = 1
for i in l:curr = round(curr * (1 - i),10)

print(sum(round(j * curr,10) for j in sumarray[:- mihe]))


### FIXED CODE ###

from decimal import *
from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush,heappop
import math
from collections import *
from functools import reduce,cmp_to_key
import sys
input = sys.stdin.readline

M = mod = 998244353
def factors(n):return sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))
def inv_mod(n):return pow(n, mod - 2, mod)

def li():return [int(i) for i in input().rstrip('\n').split()]
def st():return input().rstrip('\n')
def val():return int(input().rstrip('\n'))
def li2():return [i for i in input().rstrip('\n')]
def li3():return [int(i) for i in input().rstrip('\n')]
def li4():return [float(i) for i in input().rstrip('\n').split(' ')]

n = val()
l = li4()
mihe = n//2 + 1


curr = 1
for i in l:curr *= (1 - i)
dp = [0 for i in range(n + 1)]
dp[0] = 1

for i in range(n):

    for j in range(i + 1,-1,-1):
        if not j:dp[j] *= 1 - l[i]
        else:dp[j] = dp[j-1] * l[i] + dp[j] *(1 - l[i])

ans = 0
for i in dp[-mihe:]:
    ans += i

print(round(ans,10))
### BUGGY CODE ###

I = list(map(int, input().split()))
N = I[0]
K = I[1]
H = list(map(int, input().split()))
inf = 2*(10**9)
dp = [inf for _ in range(N+1)]

dp[N] = 0
dp[N-1] = abs(H[N-1]-H[N-2])
for i in range(N-2,0,-1):
	for k in range(1,K+1):
		if i+k<=N:
			dp[i] = min(abs(H[i+k-1]-H[i-1])+dp[i+k], dp[i])

print(dp[1])

### FIXED CODE ###

I = list(map(int, input().split()))
N = I[0]
K = I[1]
H = list(map(int, input().split()))

dp = [float('inf') for _ in range(N+1)]

dp[N] = 0
for i in range(N-1,N-K-1,-1):
	if i>0:
		dp[i] = abs(H[i-1]-H[N-1])

for i in range(N-K-1,0,-1):
	for k in range(1,K+1):
		if i+k<=N:
			dp[i] = min(abs(H[i+k-1]-H[i-1])+dp[i+k], dp[i])

print(dp[1])
### BUGGY CODE ###

def find(e):
  if parent[e] == e:
    return e
  return find(parent[e])
n, m = map(int,input().split())
l = []
for _ in range(m):
  p, q = map(int,input().split())
  p -= 1
  q -= 1
  if (p,q) not in l:
    l.append((p,q))
parent = [i for i in range(n)]
for i,j in l:
  x = find(i)
  y = find(j)
  if x > y:
      x, y = y, x
  parent[y] = x
mx = 0
for i in set(parent):
    mx = max(mx,parent.count(i))
print(mx)


### FIXED CODE ###

class UnionFind(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]

    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x

    def is_same(self, x, y):
        return self.find(x) == self.find(y)

n,m = map(int,input().split())
uf1=UnionFind(n)
for i in range(m):
    a,b=map(int, input().split())
    uf1.union(a-1,b-1)

for i in range(n):uf1.find(i)
X = uf1.par

ans = [0]*n
for i in range(n):
    ans[X[i]] += 1

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

N,M=map(int,input().split())
A=list(map(int,input().split()))
num=[0,2,5,5,4,5,6,3,7,6]
dp=[0]
keta=[0]
tmp=0
tmp1=0
tmp_keta=-1
tmp1_keta=-1
for i in range(1,N+1):
    tmp=-1
    tmp_keta=-1
    for j in A:
        tmp1=-1
        tmp1_keta=-1
        if(i-num[j]>=0):
            if(dp[i-num[j]]>0):
                tmp1=dp[i-num[j]]+j*(10**keta[i-num[j]])
                tmp1_keta=keta[i-num[j]]+1
            elif(dp[i-num[j]]==0):
                tmp1=j
                tmp1_keta=1

            if(tmp1>tmp):
                tmp=tmp1
                tmp_keta=tmp1_keta
                
    dp.append(tmp)
    keta.append(tmp_keta)
print(dp[N])


### FIXED CODE ###

N,M=map(int,input().split())
A=list(map(int,input().split()))
if(1 in A):
    if(4 in A):
        A.remove(4)
    if(9 in A):
        A.remove(9)
    if(6 in A):
        A.remove(6)
if(5 in A):
    if(3 in A):
        A.remove(3)
    if(2 in A):
        A.remove(2)
if(3 in A):
    if(2 in A):
        A.remove(2)
if(9 in A):
    if(6 in A):
        A.remove(6)
if(7 in A):
    if(9 in A):
        A.remove(9)
    if(6 in A):
        A.remove(6)
num=[0,2,5,5,4,5,6,3,7,6]
dp=[0]
keta=[0]
tmp=0
tmp1=0
tmp_keta=-1
tmp1_keta=-1
for i in range(1,N+1):
    tmp=-1
    tmp_keta=-1
    for j in A:
        tmp1=-1
        tmp1_keta=-1
        if(i-num[j]>=0):
            if(dp[i-num[j]]>0):
                tmp1=dp[i-num[j]]+j*(10**keta[i-num[j]])
                tmp1_keta=keta[i-num[j]]+1
            elif(dp[i-num[j]]==0):
                tmp1=j
                tmp1_keta=1

            if(tmp1>tmp):
                tmp=tmp1
                tmp_keta=tmp1_keta
                
    dp.append(tmp)
    keta.append(tmp_keta)
print(dp[N])
### BUGGY CODE ###

N = int(input())
S = list(input())
L = [1]
cumsumL = [1]
res = 1
rvisited = 0
mod = 10 ** 9 + 7
class Factorial:
  def __init__(self, n, mod):
    self.f=[1]
    for i in range(1, n + 1):
      self.f.append(self.f[-1] * i % mod)
    self.i=[pow(self.f[-1], mod - 2, mod)]
    for i in range(1, n + 1)[: : -1]:
      self.i.append(self.i[-1] * i % mod)
    self.i.reverse()
  def factorial(self, i):
    return self.f[i]
  def ifactorial(self, i):
    return self.i[i]
  def combi(self, n, k):
    return self.f[n] * self.i[n - k] % mod * self.i[k] % mod
f = Factorial(N, mod)
if S[0] == "W" or S[-1] == "W":
  print(0)
  exit(0)
for i in range(1, 2 * N):
  if S[i - 1] == S[i]:
    L.append((L[i - 1] + 1 )% 2)
  else:
    L.append(L[i - 1])
if sum(L) != N:
  print(0)
  exit(0)
for i in range(1, 2 * N):
  cumsumL.append(cumsumL[i - 1] + L[i])
for i in range(1, 2 * N):
  if L[i] == 0:
    res *= cumsumL[i] - rvisited % mod
    rvisited += 1
print(f.factorial(N) * res % mod)

### FIXED CODE ###

N = int(input())
S = list(input())
L = [1]
cumsumL = [1]
res = 1
rvisited = 0
mod = 10 ** 9 + 7
class Factorial:
  def __init__(self, n, mod):
    self.f=[1]
    for i in range(1, n + 1):
      self.f.append(self.f[-1] * i % mod)
    self.i=[pow(self.f[-1], mod - 2, mod)]
    for i in range(1, n + 1)[: : -1]:
      self.i.append(self.i[-1] * i % mod)
    self.i.reverse()
  def factorial(self, i):
    return self.f[i]
  def ifactorial(self, i):
    return self.i[i]
  def combi(self, n, k):
    return self.f[n] * self.i[n - k] % mod * self.i[k] % mod
f = Factorial(N, mod)
if S[0] == "W" or S[-1] == "W":
  print(0)
  exit(0)
for i in range(1, 2 * N):
  if S[i - 1] == S[i]:
    L.append((L[i - 1] + 1 )% 2)
  else:
    L.append(L[i - 1])
if sum(L) != N:
  print(0)
  exit(0)
for i in range(1, 2 * N):
  cumsumL.append(cumsumL[i - 1] + L[i])
for i in range(1, 2 * N):
  if L[i] == 0:
    res *= cumsumL[i] - rvisited % mod
    res %= mod
    rvisited += 1
print(f.factorial(N) * res % mod)
### BUGGY CODE ###

from collections import deque,Counter
import sys
input = sys.stdin.readline

n,m,k = map(int,input().split())
ans = [0]*(n+1)
frd = [[] for _ in range(n+1)]

for _ in range(m):
    a,b = map(int,input().split())
    frd[a].append(b)
    frd[b].append(a)
    ans[a] -= 1
    ans[b] -= 1

ucnt = 0
uni = [-1]*(n+1)
stk = deque()
for i in range(n):
    if uni[i] != -1: continue
    stk.append((i,0))
    while stk:
        cur,prev = stk.pop()
        uni[cur] = ucnt
        for nxt in frd[cur]:
            if uni[nxt] != -1 or nxt == prev: continue
            stk.append((nxt,cur))
    ucnt += 1
cnt = Counter(uni)

for _ in range(k):
    c,d = map(int,input().split())
    if uni[c] == uni[d]:
        ans[c] -= 1
        ans[d] -= 1

for i in range(1,n+1): 
    ans[i] += cnt[uni[i]] - 1
    print(ans[i],end=" ")

### FIXED CODE ###

from collections import deque,Counter

n,m,k = map(int,input().split())
frd = [[] for _ in range(n)]
blk = [[] for _ in range(n)]
for _ in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    frd[a].append(b)
    frd[b].append(a)
for _ in range(k):
    c,d = map(int,input().split())
    c -= 1
    d -= 1
    blk[c].append(d)
    blk[d].append(c)

ucnt = 0
uni = [-1]*n
stk = deque()
for i in range(n):
    if uni[i] != -1: continue
    stk.append((i,-1))
    while stk:
        cur,prev = stk.pop()
        uni[cur] = ucnt
        for nxt in frd[cur]:
            if nxt == prev: continue
            if uni[nxt] != -1: continue
            stk.append((nxt,cur))
    ucnt += 1
cnt = Counter(uni)

for i in range(n):
    ans = cnt[uni[i]] - 1
    for f in frd[i]:
        if uni[i] == uni[f]: ans -= 1
    for b in blk[i]:
        if uni[i] == uni[b]: ans -= 1
    print(ans,end=" ")