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

s=input()
t=input()
m,n=len(s),len(t)
dp=[[0]*(n+1)for _ in range(m+1)]
for i in range(m):
    for j in range(n):
        if s[i]==t[j]:
            dp[i+1][j+1]=dp[i][j]+1
        else:
            if dp[i+1][j]>dp[i][j+1]:
                dp[i+1][j+1]=dp[i+1][j]
            else:
                dp[i+1][j+1]=dp[i][j+1]
a,b=m,n
tmp=''
while a and b:
    if s[a-1]==t[b-1]:
        a-=1
        b-=1
        tmp+=s[a]
    elif dp[a][b]==dp[a-1][b]:
        a-=1
    else:
        b-=1
print(tmp[::-1])


### FIXED CODE ###

s=input()
t=input()
m,n=len(s),len(t)
dp=[[0]*(n+1)for _ in range(m+1)]
for i in range(m):
    for j in range(n):
        if s[i]==t[j]:
            dp[i+1][j+1]=dp[i][j]+1
        else:
            if dp[i+1][j]>dp[i][j+1]:
                dp[i+1][j+1]=dp[i+1][j]
            else:
                dp[i+1][j+1]=dp[i][j+1]
a,b=m,n
tmp=''
while a and b:
    if s[a-1]==t[b-1]:
        a-=1
        b-=1
        tmp+=s[a]
    elif dp[a][b]==dp[a-1][b]:
        a-=1
    else:
        b-=1
print(tmp[::-1])
### BUGGY CODE ###

def BC132_E():
    n, m = list(map(int, input().split(' ')))
    e = [[] for _ in range(n)]
    for _ in range(m):
        u, v = list(map(int, input().split(' ')))
        e[u - 1].append(v - 1)
    s, t = list(map(int, input().split(' ')))
    s, t = s - 1, t - 1
    stack, visited = [(s, 0)], set()
    while stack:
        i, d = stack.pop(0)
        if i in visited:
            continue
        visited.add(i)
        a = set()
        for j in e[i]:
            a.update(e[j])
        b = set()
        for j in list(a):
            b.update(e[j])
        if t in b:
            return d + 1
        else:
            stack += [(x, d + 1) for x in list(b)]
    return -1


print(BC132_E())

### FIXED CODE ###

def BC132_E():
    n, m = list(map(int, input().split(' ')))
    e = [[] for _ in range(n)]
    for _ in range(m):
        u, v = list(map(int, input().split(' ')))
        e[u - 1].append(v - 1)
    s, t = list(map(int, input().split(' ')))
    s, t = s - 1, t - 1
    stack, visited = [(s, 0)], set()
    a, b = set(), set()
    while stack:
        i, d = stack.pop(0)
        if i == t: return d
        if i in visited:
            continue
        visited.add(i)
        v = set()
        for j in e[i]:
            if j in a: continue
            a.add(j)
            for k in e[j]:
                if k in b: continue
                b.add(k)
                v.update(e[k])
        if t in v:
            return d + 1
        else:
            stack += [(x, d + 1) for x in list(v)]
    return -1


print(BC132_E())
### BUGGY CODE ###

N,K=map(int,input().split())
c=0
if K%2==0:
    d=K//2
else:
    print((N//K)**3)
    exit()

for i in range(d,N+1,d):
    for j in range(d,N+1,d):
        for k in range(d,N+1,d):
            if (i+j)%K==0 and (j+k)%K==0 and (k+i)%K==0:
                c+=1
print(c)

### FIXED CODE ###

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

if K%2==0:
    print((N//K)**3+((N//(K//2))-(N//K))**3)
else:
    print((N//K)**3)
### BUGGY CODE ###

n = int(input())
*A, = map(int, input().split())
a, b, c = A.count(1), A.count(2), A.count(3)
DP = [[[0.0 for k in range(n+1)] for j in range(n+1)] for i in range(n+1)]
for k in range(c+1):
    for j in range(b+c-k+1):
        for i in range(a+b+c-k-j+1):
            if i+j+k == 0:
                continue
            DP[i][j][k] = n
            if i > 0:
                DP[i][j][k] += DP[i-1][j][k]*i
            if j > 0:
                DP[i][j][k] += DP[i+1][j-1][k]*j
            if k > 0:
                DP[i][j][k] += DP[i][j+1][k-1]*k
            DP[i][j][k] /= (i+j+k)
print(DP[a][b][c])


### FIXED CODE ###

n = int(input())
*A, = map(int, input().split())
a, b, c = A.count(1), A.count(2), A.count(3)
DP = [[[0.0 for k in range(n+1)] for j in range(n+1)] for i in range(n+1)]
for k in range(c+1):
    for j in range(b+c-k+1):
        for i in range(n-j-k+1):
            if i+j+k == 0:
                continue
            tmp = n
            if i > 0:
                tmp += DP[i-1][j][k]*i
            if j > 0:
                tmp += DP[i+1][j-1][k]*j
            if k > 0:
                tmp += DP[i][j+1][k-1]*k
            DP[i][j][k] = tmp/(i+j+k)
print(DP[a][b][c])
### BUGGY CODE ###

# coding: utf-8
# Your code here!
MOD = 10**9 + 7
N = int(input())
S = list(input())
if S[0] == "W" or S[2*N-1] == "W":
    print(0)
    exit()

L,R = [0], []
total = [0 for i in range(2*N)]
total[0] = 1
l,r = 1,0
prev = "L"
for i in range(1, 2*N):
    if S[i] == S[i-1]:
        if prev == "L":
            R.append(i)
            total[i] = total[i-1] - 1
            r += 1
            prev = "R"
        else:
            L.append(i)
            total[i] = total[i-1] + 1
            l += 1
            prev = "L"
    else:
        if prev == "L":
            L.append(i)
            total[i] = total[i-1] + 1
            l += 1
        else:
            R.append(i)
            total[i] = total[i-1] - 1
            r += 1
    if l < r:
        print(0)
        exit()

if not (len(L) == N and len(R) == N):
    print(0)
    exit()

def fact(n):
    ret = 1
    while n > 1:
        ret *= n
        n -= 1
    return ret
    
cnt = 1
for r in R:
    cnt = (cnt * (total[r] + 1)) % MOD
print(cnt * fact(N) % MOD)

### FIXED CODE ###

# coding: utf-8
# Your code here!
MOD = 10**9 + 7
N = int(input())
S = list(input())
if S[0] == "W" or S[2*N-1] == "W":
    print(0)
    exit()

L,R = [0], []
total = [0 for i in range(2*N)]
total[0] = 1
l,r = 1,0
prev = "L"
for i in range(1, 2*N):
    if S[i] == S[i-1]:
        if prev == "L":
            R.append(i)
            total[i] = total[i-1] - 1
            r += 1
            prev = "R"
        else:
            L.append(i)
            total[i] = total[i-1] + 1
            l += 1
            prev = "L"
    else:
        if prev == "L":
            L.append(i)
            total[i] = total[i-1] + 1
            l += 1
        else:
            R.append(i)
            total[i] = total[i-1] - 1
            r += 1
    if l < r:
        print(0)
        exit()

if not (len(L) == N and len(R) == N):
    print(0)
    exit()

def fact(n):
    ret = 1
    while n > 1:
        ret = (ret * n) % MOD
        n -= 1
    return ret
    
cnt = 1
for r in R:
    cnt = (cnt * (total[r] + 1)) % MOD
print(cnt * fact(N) % MOD)
### BUGGY CODE ###

N = int(input())
A = [list(map(int,input().split())) for _ in range(N)]

INF = 10**9+10
E_list = [[] for _ in range((N*(N-1))//2)]
k = 0
for i in range(N):
    for j in range(i+1,N):
        E_list[k] = (A[i][j],i,j)
        k += 1
E_list.sort(key = lambda x:x[0])
B = [[INF]*N for _ in range(N)]
ans = 0
for l,i,j in E_list:
    l_min = INF
    Bi = B[i]
    Bj = B[j]
    for k in range(N):
        tmp = Bi[k]+Bj[k]
        if tmp < l_min:
            l_min = tmp
    if l > l_min:
        ans = -1
        break
    elif l < l_min:
        ans += l
    Bi[j] = l
    Bj[i] = l
print(ans)

### FIXED CODE ###

N = int(input())
A = [list(map(int,input().split())) for _ in range(N)]

INF = 10**10
E_list = []
for i in range(N):
    for j in range(i+1,N):
        E_list.append([A[i][j],i,j])
E_list.sort()
B = [[INF]*N for _ in range(N)]
ans = 0
for l,i,j in E_list:
    l_min = INF
    for k in range(N):
        l_min = min(l_min,B[i][k]+B[k][j])
    if l > l_min:
        ans = -1
        break
    elif l < l_min:
        ans += l
    B[i][j] = l
    B[j][i] = l
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 7)
read = sys.stdin.buffer.read 
inp = sys.stdin.buffer.readline

from itertools import accumulate
def resolve():
    K, Q = map(int, inp().split())
    D = list(map(int, inp().split()))

    for _ in range(Q):
        n, x, m = map(int, inp().split())
        # 最初にmの余りをとっても変わらない
        # 与えられた要素をすべてmod mにとりあえずする
        E = [d%m for d in D]
        acc_E = list(accumulate(E))

        # 数列がN項であるということは、末項は数列dをN-1回足したものである
        loop, rem = divmod(n - 1, K)
        tot = x % m + acc_E[-1] * loop

        # Bi = Bi+1 になっている個所：0の個数
        zero = [int(e == 0) for e in E]
        zero_acc = list(accumulate(zero))
        tot_zero = zero_acc[-1] * loop

        if rem > 0:
            tot += acc_E[rem-1]
            tot_zero += zero_acc[rem - 1]
        dame = tot // m
        print(n - 1 - dame - tot_zero)

if __name__ == "__main__":
    resolve()


### FIXED CODE ###


import sys
sys.setrecursionlimit(10 ** 7)
read = sys.stdin.buffer.read 
inp = sys.stdin.buffer.readline

import numpy as np
def resolve():
    K, Q = map(int, inp().split())
    D = np.array(inp().split(), dtype=np.int64)
    nxm = [list(map(int, inp().split())) for _ in range(Q)]

    for n, x, m in nxm:
        # 最初にmの余りをとっても変わらない
        # 与えられた要素をすべてmod mにとりあえずする
        E = D % m
        acc_E = np.cumsum(E)

        # 数列がN項であるということは、末項は数列dをN-1回足したものである
        loop, rem = divmod(n - 1, K)
        tot = x % m + acc_E[-1] * loop

        # Bi = Bi+1 になっている個所：0の個数
        zero_acc = np.cumsum(E == 0).astype(np.int64)
        tot_zero = zero_acc[-1] * loop

        if rem > 0:
            tot += acc_E[rem-1]
            tot_zero += zero_acc[rem - 1]
        dame = tot // m
        print(n - 1 - dame - tot_zero)

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

import itertools as it
a,b,c,k=list(map(int,input().split()))
arr=[]
for i in range(a):
    arr.append(1)
for i in range(b):
    arr.append(0)
for i in range(c):
    arr.append(-1)
res=list(it.combinations(arr,k))
re=[]
for i in res:
    re.append(sum(i))
print(max(re))

### FIXED CODE ###

def xyz(a,b,c,k):
    if k==a:
        return(k)
    if a>k:
        return(k)
    sum1=a
    if a+b>=k:
        return(a)
    d=k-a-b
    sum1=sum1-d
    return(sum1)
    
    


a,b,c,k=list(map(int,input().split()))
d=xyz(a,b,c,k)
print(d)
### BUGGY CODE ###

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


def lcm(a, b):
    return a * b // gcd(a, b)


n = int(input())
a = list(map(int, input().split()))
lcm_a = a[0]

for i in range(1, n):
    lcm_a = lcm(lcm_a, a[i])

ans = 0

for i in a:
    ans += lcm_a // i

print(ans%1000000007)


### FIXED CODE ###

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


def lcm(a, b):
    return a * b // gcd(a, b)


n = int(input())
a = list(map(int, input().split()))
lcm_a = a[0]

for i in range(1, n):
    lcm_a = lcm(lcm_a, a[i])

ans = 0

for i in a:
    ans += lcm_a // i

print(ans%1000000007)
### BUGGY CODE ###

x,y = map(int,input().split())
li = list(map(int,input().split()))
li.sort()
score = 0
for i in range(y):
  li.sort()
  li[x - 1] //= 2
for j in li:
  score += j
print(score)

### FIXED CODE ###

import heapq

n, m = map(int,input().split())
li = list(map(lambda x: int(x)*(-1),input().split()))

heapq.heapify(li)

for i in range(m):
    a = heapq.heappop(li)
    a = (-a) // 2
    heapq.heappush(li,-a)

print(-sum(li))
### BUGGY CODE ###

import numpy as np

s = input()
p = np.array([0]*13)
p[0] = 1

for si in range(len(s)):
  a = np.array([0]*13)
  if s[si] == '?':
    for j in range(10):
      for i in range(13):
        a[(i*10+j)%13] += p[i]
  else:
    c = int(s[si])
    for i in range(13):
      a[(i*10+c)%13] += p[i]
  p = np.mod(a,1000000007)
print(p[5])

### FIXED CODE ###

import numpy as np

s = input()
p = np.array([0]*13)
p[0] = 1

amari = [[0]*13 for _ in range(13)]
for j in range(10):
  for i in range(13):
    amari[i][(i*10+j)%13] += 1
M = np.array(amari)

for si in range(len(s)):
  a = np.array([0]*13)
  if s[si] == '?':
    a = np.dot(p,M)
  else:
    c = int(s[si])
    for i in range(13):
      a[(i*10+c)%13] += p[i]
  p = np.mod(a,1000000007)
print(p[5])
### BUGGY CODE ###


S=list(str((input())))
Q=int(input())
t=0
for _ in range(Q):
    T=list(map(str,input().split()))
    if T[0]=="1":
        t+=1
    else:
        if (T[1]=="1" and t%2 == 0) or (T[1]=="2" and t%2 != 0):
            S.insert(0,T[2])
        else:
            S.append(T[2])


if t%2 != 0:
    S.reverse()

print("".join(S))

### FIXED CODE ###

from collections import deque

S=deque(str((input())))
Q=int(input())
t=0
for _ in range(Q):
    T=list(map(str,input().split()))
    if T[0]=="1":
        t+=1
    else:
        if (T[1]=="1" and t%2 == 0) or (T[1]=="2" and t%2 != 0):
            S.appendleft(T[2])
        else:
            S.append(T[2])


if t%2 != 0:
    S.reverse()

print("".join(S))
### BUGGY CODE ###

from collections import deque
from itertools import product
h, w = list(map(int,input().split()))
sy, sx = list(map(int,input().split()))
gy, gx = list(map(int,input().split()))
sx, sy, gx, gy = sx-1, sy-1, gx-1, gy-1
 
G = [list(input()) for _ in range(h)]
D = [[10**6]*w for _ in range(h)]
D[sy][sx] = 0
Q = deque([(sy, sx)])
while Q:
    y, x = Q.pop()
    for dy, dx in product(range(-2, 3), repeat=2):
        ny, nx = y+dy, x+dx
        if dx==dy==0:
            G[y][x] = '#'
        elif (0<=ny<h and 0<=nx<w) and G[ny][nx] != '#':
            if abs(dy)+abs(dx)<=1:
                G[ny][nx] = '#'
                D[ny][nx] = D[y][x]
                Q.append((ny, nx))
            elif D[ny][nx] == 10**6:
                D[ny][nx] = D[y][x]+1
                Q.appendleft((ny, nx))
            
if D[gy][gx] == 10**6:
    print(-1)
else:
    print(D[gy][gx])


### FIXED CODE ###

from collections import deque
from itertools import product
h, w = list(map(int,input().split()))
sy, sx = list(map(int,input().split()))
gy, gx = list(map(int,input().split()))
sx, sy, gx, gy = sx-1, sy-1, gx-1, gy-1
 
G = [list(input()) for _ in range(h)]
D = [[10**6]*w for _ in range(h)]
D[sy][sx] = 0
Q = deque([(sy, sx)])
while Q:
    y, x = Q.pop()
    for dy, dx in product(range(-2, 3), repeat=2):
        ny, nx = y+dy, x+dx
        if dx==dy==0:
            G[y][x] = '#'
            continue
        elif ny<0 or h<=ny or nx<0 or w<=nx:
            continue
        elif G[ny][nx] == '#':
            continue
        elif abs(dy)+abs(dx)<=1:
            G[ny][nx] = '#'
            D[ny][nx] = D[y][x]
            Q.append((ny, nx))
        elif D[ny][nx] == 10**6:
            D[ny][nx] = D[y][x]+1
            Q.appendleft((ny, nx))
            
if D[gy][gx] == 10**6:
    print(-1)
else:
    print(D[gy][gx])
### BUGGY CODE ###

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

ans = 2**n
#n2 = n
#ans = 1
#rou = 0
#while n2 >= 1:
    #n2, rem = divmod(n2, 2)
    #if rem == 1:
        #ans *= 2**(2**rou)
    #rou += 1

#　数え過ぎたものを引く
import math
def comb(n, r):
    return math.factorial(n) // (math.factorial(n-r) * math.factorial(r))

ans -= comb(n, a) + comb(n, b) + 1


print(int(ans % (1000000007)))

### FIXED CODE ###

#TLE

#comb_mod(n, r, mod) = nCr % mod
def comb_mod(n, r, mod):
    ans = 1
    if r <= n/2:
        for i in range(n-r+1, n+1):
            ans *= i
            ans %= mod
        for i in range(1, r+1):
            ans *= pow(i, mod-2, mod)
            ans %= mod
    else:
        for i in range(r+1, n+1):
            ans *= i
            ans %= mod
        for i in range(1, n-r+1):
            ans *= pow(i, mod-2, mod)
            ans %= mod
    return ans

n, a, b = map(int, input().split())
ans = pow(2, n, 10**9+7) - comb_mod(n, a, 10**9+7) - comb_mod(n, b, 10**9+7) - 1
if ans < 0:
    ans += 10**9 + 7
if ans < 0:
    ans += 10**9 + 7

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

import sys
sys.setrecursionlimit(1000000)
from collections import deque

def bfs(sx,sy,gx,gy):
    d = [[float("inf")] * w for i in range(h)]
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]

    que = deque([])
    que.append((sx, sy))
    d[sx][sy] = 0

    while que:
        p = que.popleft()
        if p[0] == gx and p[1] == gy:
            break
        for i in range(4):
            nx = p[0] + dx[i]
            ny = p[1] + dy[i]
            if 0 <= nx < h and 0 <= ny < w and s[nx][ny] != "#" and d[nx][ny] == float("inf"):
                que.append((nx, ny))
                d[nx][ny] = d[p[0]][p[1]] + 1

    return d[gx][gy]

h,w=map(int,input().split())
s = [list(input()) for i in range(h)]
ans=0
for i in range(h):
    for j in range(w):
        if s[i][j]=='.':
            for k in range(h):
                for l in range(w):
                    if s[k][l]=='.':
                        ans = max(ans,bfs(i,j,k,l))
print(ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)
from collections import deque


h,w=map(int,input().split())
s = [list(input()) for i in range(h)]

def bfs(sx,sy):
    dx = [0,1,0,-1]
    dy = [1,0,-1,0]
    d = [[-1]*w for i in range(h)]
    q = deque()
    q.append((sx,sy))
    d[sx][sy] = 0
    while q:
        x,y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if  0<= nx < h and 0 <= ny < w and d[nx][ny]==-1 and s[nx][ny]=='.':
                q.append((nx,ny))
                d[nx][ny] = d[x][y]+1
    return max([max(i) for i in d])

count = 0
for i in range(h):
    for j in range(w):
        if s[i][j] != '#':
            count  = max(count, bfs(i,j))
print(count)
### BUGGY CODE ###

import numpy as np
n=input()
data=list(map(int,input().split()))
is_i=0
num=sorted(data)
count=num[1]
if num[0]!=num[1]:
    if any([x%num[1]!=0 for x in data[1::]])==True:
        count=int(num[1]/2)+1
for i in range(count+1)[::-1]:
    is_i=0
    if all([x%i==0 for x in data]):
        print(i)
        break
    else:
        for j in range(len(data)):
            if data[j]%i!=0:
                is_i+=1
        if is_i==1:
            print(i)
            break

### FIXED CODE ###

from fractions import gcd
import numpy as np
n=int(input())
data=list(map(int,input().split()))
left=np.zeros(n+1,dtype=np.int)
right=np.zeros(n+1,dtype=np.int)
kotae=1
for i in range(n):
    left[i+1]=gcd(left[i],data[i])
    right[n-i-1]=gcd(right[n-i],data[n-i-1])
for j in range(n):
    num=gcd(left[j],right[j+1])
    kotae=max(num,kotae)
print(kotae)
### BUGGY CODE ###

N = int(input())
S = input()
ans = S.count("R") * S.count("G") * S.count("B")

for i in range(N - 2):
    for j in range(i + 1, N - 1):
        if S[i] != S[j]:
            x = 2 * j - i
            if x <= N - 1 and S[i] != S[x] and S[x] != S[j]:
                ans -= 1

print(ans)


### FIXED CODE ###

N = int(input())
S = input()
ans = S.count("R") * S.count("G") * S.count("B")

for i in range(N - 2):
    for j in range(i + 1, N - 1):
        if S[i] != S[j]:
            x = 2 * j - i
            if x < N and S[i] != S[x] and S[x] != S[j]:
                ans -= 1

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

n = int(input())
a = [int(input()) for i in range(n)]
b = a
c = max(a)

for i in range(n):
    if a[i] == c:
        x = b.pop(i) #i番目の要素を削除
        print(max(b)) #その中での最大値を出力
        b.insert(i, x) #削除した要素を戻す
    else:
        print(c)

### FIXED CODE ###

import heapq

n = int(input())
a = [int(input()) for i in range(n)]
b = heapq.nlargest(2, set(a))
c = a.count(b[0])

if len(b) == 1 or c > 1: #bの長さが1または、最大値が2回以上存在するなら
    for i in range(n):
        print(b[0]) #最大値のみを表示

else: #bの長さが2以上なら
    for i in range(n):
        if a[i] == b[0]: #i番目が最大値だったら
            print(b[1]) #2番目に大きい値を出力
        else: #そうでなければ
            print(b[0]) #最大値を出力
### BUGGY CODE ###

s = input()
ans = 0

while True:
    c = s.count("ABC")
    ans += c
    if c == 0:
        print(ans)
        break
    s = s.replace("ABC", "BCA")


### FIXED CODE ###

s = input()
s2 = s.replace("BC", 'D')
ans = 0
na = 0
for c in s2:
  if na:
    if c == "D":
      ans += na
    elif c != "A":
      na = 0
  if c == 'A':
    na += 1
print(ans)
### BUGGY CODE ###

n = int(input())

a = [0]*n

for x in range(1, n):
    for y in range(1, x+1):
        for z in range(1, y+1):
            t = x**2+y**2+z**2+x*y+y*z+z*x-1
            if t >= n:
                break
            if ((x==y)and(y!=z))or((x==z)and(y!=x))or((y==z)and(x!=z)):
                a[t] = 3
            elif (x!=y)and(y!=z)and(x!=z):
                a[t] = 6
            else:
                a[t] = 1

for i in range(n):
    print(a[i])

### FIXED CODE ###

import math

n = int(input())

a = [0]*n

for x in range(1, int(math.sqrt(n))+1):
    for y in range(1, x+1):
        for z in range(1, y+1):
            t = x**2+y**2+z**2+x*y+y*z+z*x-1
            if t >= n:
                break
            if x == y == z:
                a[t] += 1
            elif (x!=y)and(y!=z)and(x!=z):
                a[t] += 6
            else:
                a[t] += 3

for i in range(n):
    print(a[i])
### BUGGY CODE ###

from collections import deque
import heapq

s = input()
s += " "

S = ""

for i in range(len(s)-1):
    if s[i] == "B" and s[i+1] == "C":
        S += "Z"

    elif i > 0 and s[i] == "C" and s[i-1] == "B":
        continue
    else:
        S += s[i]

#print (S)
la = deque([])
ans = 0
for i in range(len(S)):

    if S[i] == "A":
        la.append(i)

    elif S[i] == "Z" and len(la) > 0:
        lastA = la.popleft()
        ans += i - lastA
        la.append(i)

    else:
        la = deque()

print (ans)


### FIXED CODE ###

from collections import deque
import heapq

s = input()
s += " "

S = ""

for i in range(len(s)-1):
    if s[i] == "B" and s[i+1] == "C":
        S += "Z"

    elif i > 0 and s[i] == "C" and s[i-1] == "B":
        continue
    else:
        S += s[i]

#print (S)
la = deque([])
ans = 0
for i in range(len(S)):

    if S[i] == "A":
        la.append(i)

    elif S[i] == "Z" and len(la) > 0:
        lastA = la.popleft()
        ans += i - lastA
        la.append(i)

    else:
        la = deque([])

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

N = int(input())
power = 1
m = 10**9 + 7
for i in range(1,N+1):
    power *= i
print(power % m)


### FIXED CODE ###

import math
n=int(input())
mod = 10**9 + 7
ans = math.factorial(n)
print(ans % mod)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000)

def combination_to_index(a,b,n):
    if(b<a):
        c = a
        a = b
        b = c
    return (2*n-a)*(a-1)//2+b-a

def dfs(n,seen,gp,d):
    #print(d)
    res = -1
    if(n in seen):
        return -1
    for x in gp[n]:
        res = max(res,dfs(x,seen.union(set([n])),gp,d+1))

    if(res == -1):
        return d
    else:
        return res

def main():
    N = int(input())
    M = N*(N-1)//2
    gp = [[] for _ in range(M+1)]
    for a in range(1,N+1):
        A = [int(x) for x in input().split()]
        for ind,b in enumerate(A[:-1]):
            gp[combination_to_index(a,b,N)].append(combination_to_index(a,A[ind+1],N))
    cnts = [0]*(M+1)
    for i in gp:
        for j in i:
            cnts[j]+=1

    for ind,i in enumerate(cnts):
        if(i==0 and ind!=0):
            gp[0].append(ind)

    d = dfs(0,set(),gp,0)
    if(d==0):
        print(-1)
    else:
        print(d)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
from collections import deque
input = sys.stdin.readline
def combination_to_index(a,b,n):
    if(b<a):
        a,b = b,a
    return (2*n-a)*(a-1)//2+b-a

def main():
    N = int(input())
    M = N*(N-1)//2
    gp = [[] for _ in range(M+1)]
    cnts = [0]*(M+1)
    for a in range(1,N+1):
        A = [int(x) for x in input().split()]
        for ind,b in enumerate(A[:-1]):
            fr = combination_to_index(a,b,N)
            to = combination_to_index(a,A[ind+1],N)
            gp[fr].append(to)
            cnts[to] += 1

    for ind,i in enumerate(cnts):
        if(i==0 and ind!=0):
            gp[0].append(ind)
            cnts[ind]+=1

    ans = 0
    cnt = 0
    stk = deque()
    stk.append((0,0))
    while stk:
        n,ans = stk.popleft()
        for x in gp[n]:
            cnts[x]-=1
            if(cnts[x]==0):
                stk.append((x,ans+1))
                cnt += 1
    if(cnt!=M):
        print(-1)
    else:
        print(ans)

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

n = int(input())
P = [float(i) for i in input().split()]

DP = [[0] * (n+1) for j in range(n+1)]
DP[0][0] = 1

for i in range(n):
    for j in range(n):
        DP[i+1][j+1] += DP[i][j] * P[i]
        DP[i+1][j] += DP[i][j] * (1 - P[i])

print(sum(DP[n][(n+1)//2:]))

### FIXED CODE ###

n = int(input())
P = [float(i) for i in input().split()]

DP = [[0] * (n+1) for j in range(n+1)]
DP[0][0] = 1

for i in range(n):
    for j in range(n):
        DP[i+1][j+1] += DP[i][j] * P[i]
        DP[i+1][j] += DP[i][j] * (1 - P[i])

print(sum(DP[n][(n+1)//2:]))