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

N = int(input())

ans = 0
divisor = 10
if N % 2 == 0:
    while N >= divisor:
        ans += N // divisor
    divisor *= 5
print(ans)

### FIXED CODE ###

N = int(input())

ans = 0
divisor = 10
if N % 2 == 0:
    while N >= divisor:
        ans += N // divisor
        divisor *= 5
print(ans)
### BUGGY CODE ###

n = int(input())
res = 0
for i in range(1,n):
    res += i%(i+1)
print(res)

### FIXED CODE ###

n = int(input())
print(n*(n-1)//2)
### BUGGY CODE ###

h, w = map(int, input().split(" "))
sr, sc = map(int, input().split(" "))
er, ec = map(int, input().split(" "))

board=[['' for i in range(w)] for j in range(h)]
for i in range(h):
    s=input()
    for j in range(w):
        board[i][j]= s[j]
rs,cs=[],[]
rs.append(sr-1)
cs.append(sc-1)
magic=[[1e6 for i in range(w)] for j in range(h)]
dr=[-1,1,0,0]
dc=[0,0,-1,1]
magic[sr-1][sc-1]=0
while len(rs)>0:
    r,c=rs.pop(0),cs.pop(0)
    for i in range(4):
        nr,nc= r+dr[i],c+dc[i]
        if nr < 0 or nr >= h or nc < 0 or nc >= w or board[nr][nc] == '#':
            continue
        if magic[nr][nc]>magic[r][c]:
            magic[nr][nc]= magic[r][c]
            rs.insert(0,nr)
            cs.insert(0,nc)
    #wizard
    for nr in range(r-2,r+3):
        for nc in range(c-2,c+3):
            if nr < 0 or nr >= h or nc < 0 or nc >= w or board[nr][nc] == '#':
                continue
            if magic[nr][nc] > magic[r][c]+1:
                    magic[nr][nc] = magic[r][c]+1
                    rs.append(nr)
                    cs.append(nc)
print(magic[er-1][ec-1] if magic[er-1][ec-1]<1e6 else -1)

### FIXED CODE ###

import collections

h, w = map(int, input().split(" "))
sr, sc = map(int, input().split(" "))
er, ec = map(int, input().split(" "))

board=[['' for i in range(w)] for j in range(h)]
for i in range(h):
    s=input()
    for j in range(w):
        board[i][j]= s[j]
rs,cs=collections.deque([sr-1]),collections.deque([sc-1])
magic=[[1e6 for i in range(w)] for j in range(h)]
dr=[-1,1,0,0]
dc=[0,0,-1,1]
magic[sr-1][sc-1]=0
while len(rs)>0:
    r,c=rs.popleft(),cs.popleft()
    for i in range(4):
        nr,nc= r+dr[i],c+dc[i]
        if nr < 0 or nr >= h or nc < 0 or nc >= w or board[nr][nc] == '#':
            continue
        if magic[nr][nc]>magic[r][c]:
            magic[nr][nc]= magic[r][c]
            rs.appendleft(nr)
            cs.appendleft(nc)
    #wizard
    for nr in range(r-2,r+3):
        for nc in range(c-2,c+3):
            if nr < 0 or nr >= h or nc < 0 or nc >= w or board[nr][nc] == '#':
                continue
            if magic[nr][nc] > magic[r][c]+1:
                    magic[nr][nc] = magic[r][c]+1
                    rs.append(nr)
                    cs.append(nc)
print(magic[er-1][ec-1] if magic[er-1][ec-1]<1e6 else -1)
### BUGGY CODE ###

import sys
from scipy.sparse import lil_matrix
from scipy.sparse.csgraph import dijkstra

def abc070_d():
    read = sys.stdin.buffer.read
    inp = iter(map(int, read().split()))

    n = next(inp)
    adjmtx = lil_matrix((n, n), dtype=int)
    for _ in range(n-1):
        a = next(inp) - 1
        b = next(inp) - 1
        c = next(inp)
        adjmtx[a, b] = c
        adjmtx[b, a] = c

    q = next(inp)
    k = next(inp) - 1

    dist = dijkstra(csgraph=adjmtx, indices=k)
    eps = 1e-6

    for _ in range(q):
        x = next(inp) - 1
        y = next(inp) - 1
        ans = int(dist[x] + dist[y] + eps)
        print(ans)

if __name__ == '__main__':
    abc070_d()

### FIXED CODE ###

def abc070_d():
    import sys
    sys.setrecursionlimit(10010010)
    read = sys.stdin.buffer.read
    inp = iter(map(int, read().split()))

    n = next(inp)
    adjlist = [[] for _ in range(n)]
    for _ in range(n-1):
        a = next(inp) - 1
        b = next(inp) - 1
        c = next(inp)
        adjlist[a].append((b, c))
        adjlist[b].append((a, c))

    q = next(inp)
    k = next(inp) - 1

    dist = [-1] * n

    def dfs(x:int, d:int):
        dist[x] = d
        for nx, nd in adjlist[x]:
            if dist[nx] != -1: continue
            dfs(nx, d + nd)

    dfs(k, 0)

    for _ in range(q):
        x = next(inp) - 1
        y = next(inp) - 1
        ans = dist[x] + dist[y]
        print(ans)

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

n = int(input())
l = list(map(int, input().split()))
a = 0
for m in range(n):
    k = l.count(m+1)
    a += int(k*(k-1)/2)
for m in range(n):
    print(a-l.count(l[m])+1)

### FIXED CODE ###

n = int(input())
l = list(map(int, input().split()))
a = []
b = 0
for m in range(n):
    a.append(0)
for m in range(n):
    a[l[m]-1] += 1
for m in range(n):
    b += int(a[m]*(a[m]-1)/2)
for m in range(n):
    print(b-a[l[m]-1]+1)
### BUGGY CODE ###

N = int(input()) 
d = list(map(int, input().split()))
a=int(N/2)
for i in range(len(d)-1):
	for j in range(i+1, len(d)):
		if d[i] > d[j]:
			temp = d[i]
			d[i] = d[j]
			d[j] = temp
print(d[a]-d[a-1])

### FIXED CODE ###

N = int(input()) 
d = list(map(int, input().split()))
a=int(N/2)
def quick_sort(arr):
    left = []
    right = []
    if len(arr) <= 1:
        return arr

    # データの状態に左右されないためにrandom.choice()を用いることもある。
    # ref = random.choice(arr)
    ref = arr[0]
    ref_count = 0

    for ele in arr:
        if ele < ref:
            left.append(ele)
        elif ele > ref:
            right.append(ele)
        else:
            ref_count += 1
    left = quick_sort(left)
    right = quick_sort(right)
    return left + [ref] * ref_count + right
d=quick_sort(d)
print(d[a]-d[a-1])
### BUGGY CODE ###

# -*- coding: utf-8 -*-

# 組み合わせの数だけ返してくれる関数
def nCr(n, r):
    """
    Calculate the number of combination (nCr = nPr/r!).
    The parameters need to meet the condition of n >= r >= 0.
    It returns 1 if r == 0, which means there is one pattern
    to choice 0 items out of the number of n.
    """

    # 10C7 = 10C3
    r = min(r, n-r)

    # Calculate the numerator.
    numerator = 1
    for i in range(n, n-r, -1):
        numerator *= i

    # Calculate the denominator. Should use math.factorial?
    denominator = 1
    for i in range(r, 1, -1):
        denominator *= i

    return numerator // denominator

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

h = H - A
w = B + 1
ans = 0
# マスを右上に1つずつずらして、必ず通る場所でパターンを足し合わせていく
while h > 0 and w <= W:
    ans += nCr(h+w-2, h-1) * nCr(H-h+W-w, H-h) % (10 ** 9 + 7)
    h -= 1
    w += 1

print(ans % (10 ** 9 + 7))

### FIXED CODE ###

# -*- coding: utf-8 -*-

H,W,A,B = map(int, input().split())
mod = (10 ** 9 + 7)

# 予め組み合わせ計算に必要な階乗と逆元のテーブルを作っておく
factorial = [0] * (H+W)
factorial[0] = 1
factorial[1] = 1
inverse = [0] * (H+W)
inverse[0] = 1
inverse[1] = 1
for i in range(2,H+W):
    factorial[i] = factorial[i-1] * i % mod
    # フェルマーの小定理から(x! ** mod-2 % mod == x! ** -1 % mod)
    # powに第三引数入れると冪乗のmod付計算を高速にやってくれる
    inverse[i] = pow(factorial[i], mod-2, mod)
    
# 組み合わせの数だけ返してくれる関数(自作)
def nCr(n, r):
    # 10C7 = 10C3
    r = min(r, n-r)
    # 分子の計算
    numerator = factorial[n]
    # 分母の計算
    denominator = inverse[r] * inverse[n-r] % mod
    return numerator * denominator % mod

h = H - A
w = B + 1
ans = 0
# マスを右上に1つずつずらして、必ず通る場所でパターンを足し合わせていく
while h > 0 and w <= W:
    ans = (ans + nCr(h+w-2, h-1) * nCr(H-h+W-w, H-h)) % mod
    h -= 1
    w += 1

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

import sys, math
from collections import defaultdict
from copy import deepcopy
import itertools
# 文字列の場合は普通のinput()を使うか下を使う
# input = sys.stdin.readline().rstrip()

N = int(input())
S = input()
d = {}
key = set([])
for i in range(10):
    for j in range(10):
        for k in range(10):
            d[(i, j, k)] = 0
            key.add((i, j, k))

ans = 0
for x in S:
    x = int(x)
    for key_num in key:
        i, j, k = key_num
        n = d[key_num]
        if n == 0 and i == x:
            d[key_num] += 1
        elif n == 1 and j == x:
            d[key_num] += 1
        elif n == 2 and k == x:
            d[key_num] += 1
            ans += 1
print(ans)

### FIXED CODE ###

import sys, math
from collections import defaultdict, deque
from copy import deepcopy
import itertools
# 文字列の場合は普通のinput()を使うか下を使う
# input = sys.stdin.readline().rstrip()

N = int(input())
S = input()
q = deque([])
q_new = deque([])
d = defaultdict(list)
for i in range(10):
    for j in range(10):
        for k in range(10):
            d[i].append([k, j, i])

ans = 0
for x in S:
    x = int(x)
    q = deepcopy(d[x])
    d[x] = []
    for key in q:
        l = len(key)
        if l == 3:
            d[key[1]].append(key[:2])
        elif l == 2:
            d[key[0]].append(key[:1])
        elif l == 1:
            ans += 1

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

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

def lcm(x, y):
 
   #  获取最大的数
   if x > y:
       greater = x
   else:
       greater = y
 
   while(True):
       if((greater % x == 0) and (greater % y == 0)):
           lcm = greater
           break
       greater += 1
 
   return lcm
print(lcm(a,b))


### FIXED CODE ###

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

def lcm(x, y):
 
   #  获取最大的数
   if x > y:
       lower = y
   else:
       lower = x
 
   while(True):
       if((x % lower == 0) and (y % lower == 0)):
           lcm = x*y//lower
           break 
       lower -= 1
 
   return lcm
print(lcm(a,b))
### BUGGY CODE ###

import math
N = float(input())

n = math.sqrt(N)
sum = 0
for i in range(int(n), int(N)):
  div = int(N/i)
  res = N - i*div
  if(div == res):
    sum = sum + i
  
print(sum)

### FIXED CODE ###

import math
N = int(input())
sqrtN = int(math.sqrt(float(N)))

ans = 0
prefnum = []

for div in range(1, sqrtN+1):
  if( N % div == 0):
    quot = int(N/div)
    if((quot-1) > div):
      prefnum.append(int(quot-1))
      
for i in prefnum:
  ans = ans + i

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

import sys,math,collections,itertools
input = sys.stdin.readline
from numba import jit

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

@jit
def solve(N,K,A):
    for i in range(K):
        imo = [0]*(N+1)
        flag = 1
        for j in range(N):
            imo[max(0,j-A[j])] += 1
            imo[min(N,j+A[j]+1)] -= 1
            if j-A[j]>0 or j+A[j]+1<N:
                flag = 0
        A = list(itertools.accumulate(imo))[:-1]
        if flag == 1:
            break
    return A

A = solve(N,K,A)
print(*A)


### FIXED CODE ###

import sys,math,collections,itertools
input = sys.stdin.readline

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

for i in range(K):
    imo = [0]*(N+1)
    flag = 1
    for j in range(N):
        imo[max(0,j-A[j])] += 1
        imo[min(N,j+A[j]+1)] -= 1
        if j-A[j]>0 or j+A[j]+1<N:
            flag = 0
    A = list(itertools.accumulate(imo))[:-1]
    if flag == 1:
        break
print(*A)
### BUGGY CODE ###

# E
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

def judge(cand, a, k, plus, minus, length, place):
    if plus > k or minus > k:
        return False
    
    if place == length:
        if plus - minus == 0 and plus <=  k:
            return True
        else:
            return False
    else:
        m = a[place] % cand
        p = cand - m
        return judge(cand, a, k, plus+p, minus, length, place+1) or judge(cand, a, k, plus, minus+m, length, place+1)
        
n,k = map(int, input().split())
a = list(map(int, input().split()))
# 候補はsum(a)の正約数。
total = sum(a)
length = len(a)
candidate = make_divisors(total)
candidate.sort(reverse = True)
for cand in candidate:
    if judge(cand, a, k, 0, 0, length, 0):
        print(cand)
        break

### FIXED CODE ###

# E
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


def SumArea(r, l, a2):
    return a2[l]-a2[r]

def judge(cand, a, k):
    m_list = [i%cand for i in a]
    m_list.sort()
    p_list = [cand-r for r in m_list]
    
    # 累積和
    b=list(range(1,30))
    m2=[0]
    p2=[0]
    for i in m_list:m2.append(m2[-1]+i)
    for i in p_list:p2.append(p2[-1]+i)
        
    length = len(a)
    for i in range(length):
        m_total  = SumArea(0, i, m2)
        p_total = SumArea(i, length, p2)
        if m_total == p_total and p_total <= k:
            return True
    return False
    
        
n,k = map(int, input().split())
a = list(map(int, input().split()))
pflag = True
# 候補はsum(a)の正約数。
total = sum(a)
length = len(a)
candidate = make_divisors(total)
candidate.sort(reverse = True)
for cand in candidate:
    if judge(cand, a, k):
        print(cand)
        pflag = False
        break
if pflag:
    print(1)
### BUGGY CODE ###

from itertools import combinations

n, k = [int(item) for item in input().split()]
xy = [[int(item) for item in input().split()] for _ in range(n)]

xsort = sorted(xy, key=lambda x: x[0])
ysort = sorted(xy, key=lambda x: x[1])

def count_points_in_rec(x0, x1, y0, y1):
    count = 0
    for x, y in xy:
        if x < x0 or x1 < x:
            continue
        elif y < y0 or y1 < y:
            continue
        count += 1
    return count

ans = 5 * 10**18
for a, b in combinations(xsort, 2):
    x0 = a[0]
    x1 = b[0]
    for c, d in combinations(ysort, 2):
        y0 = c[1]
        y1 = d[1]
        if count_points_in_rec(x0, x1, y0, y1) >= k:
            ans = min(ans, (x1-x0) * (y1-y0))

print(ans)


### FIXED CODE ###

from itertools import combinations
 
n, k = [int(item) for item in input().split()]
xy = [[int(item) for item in input().split()] for _ in range(n)]
 
xsort = sorted(xy, key=lambda x: x[0])
ysort = sorted(xy, key=lambda x: x[1])
l = [i for i in range(n)]
 
cum = [[0 for _ in range(n+1)] for _ in range(n+1)]
for i in range(n):
    for j in range(n):
        cum[i+1][j+1] = cum[i+1][j] + cum[i][j+1] - cum[i][j] + ([xsort[i][0], ysort[j][1]] in xy)

def count_points_in_rec(x0, x1, y0, y1):
    point = cum[x1+1][y1+1] - cum[x0][y1+1] - cum[x1+1][y0] + cum[x0][y0]
    return point

ans = 5 * 10**18
comb = []
for a, b in combinations(l, 2):
    if b - a >= k-1:
        comb.append([a, b])
for a, b in comb:
    for c, d in comb:
        if count_points_in_rec(a, b, c, d) == k:
            ans = min(ans, (xsort[b][0]-xsort[a][0]) * (ysort[d][1]-ysort[c][1]))
print(ans)
### BUGGY CODE ###

import numpy as np

H,W = list(map(int,input().split()))
INFTY = 10000
A = np.array([[-1]*(W+2)] + 
             [[-1]+[0 if c=="#" else INFTY for c in input()] + [-1] 
              for _ in range(H)] + 
             [[-1]*(W+2)] )

q = []
for i in range(1,H+1):
    for j in range(1,W+1):
        if A[i][j] == 0:
            q.append((i,j))
ans = 0
k = 0
while k < len(q):
    i,j = q[k]
    v = A[i][j]
    if A[i-1][j]==INFTY:
        A[i-1][j] = v + 1
        q.append((i-1,j))
        ans = max(ans,v+1)
    if A[i+1][j]==INFTY:
        A[i+1][j] = v + 1
        q.append((i+1,j))
        ans = max(ans,v+1)
    if A[i][j-1]==INFTY:
        A[i][j-1] = v + 1
        q.append((i,j-1))
        ans = max(ans,v+1)
    if A[i][j+1]==INFTY:
        A[i][j+1] = v + 1
        q.append((i,j+1))
        ans = max(ans,v+1)
    k += 1
print(ans)

### FIXED CODE ###

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

q = []
for i in range(H):
    for j in range(W):
        if A[i][j] == "#":
            q.append((i,j))
            A[i][j] = 0
ans = 0
k = 0
while k < len(q):
    i,j = q[k]
    v = A[i][j]
    if i>0 and A[i-1][j]==".":
        A[i-1][j] = v + 1
        q.append((i-1,j))
        ans = max(ans,v+1)
    if i<H-1 and A[i+1][j]==".":
        A[i+1][j] = v + 1
        q.append((i+1,j))
        ans = max(ans,v+1)
    if j>0 and A[i][j-1]==".":
        A[i][j-1] = v + 1
        q.append((i,j-1))
        ans = max(ans,v+1)
    if j<W-1 and A[i][j+1]==".":
        A[i][j+1] = v + 1
        q.append((i,j+1))
        ans = max(ans,v+1)
    k += 1
print(ans)
### BUGGY CODE ###

n, a, b = map(int, input().split())
ans = []
while (True):
    for _ in range(a):
        ans.append('b')
    if len(ans) >= n:
        break
    for _ in range(b):
        ans.append('r')
    if len(ans) >= n:
        break
print(ans[:n].count('b'))


### FIXED CODE ###

n, a, b = map(int, input().split())
ans = (n//(a+b)) * a
if n % (a+b) > a:
    print(ans + a)
else:
    print(ans + n % (a+b))
### BUGGY CODE ###

import numpy as np
N = int(input())
s = str(input())
maxlen = N//2
appear = [[0]*(N+1) for _ in range(26)]
for i in range(N):
    appear[ord(s[i])-97][i]=1
for i in range(26):
    appear[i] = list(np.cumsum(appear[i]))

def solve(tgt):
    for i in range(N-tgt*2+1):
        for j in range(26):
            if appear[j][N]-appear[j][i+tgt] < appear[j][i+tgt]-appear[j][i]:
                continue
        if s[i:i+tgt] in s[i+tgt:]:
            return True

    return False

ng = maxlen + 1
ok = 0
while ng-ok > 1:
    tgt = (ok+ng)//2
    if solve(tgt):
        ok = tgt
    else:
        ng = tgt
print(ok)


### FIXED CODE ###

from collections import defaultdict as dd
N = int(input())
s = str(input())
maxlen = N//2

def solve(tgt):
    dic = dd(int)
    st = s[tgt:2*tgt]
    dic[st] += 1
    ls = [st]
    for char in s[2*tgt:]:
        st = st[1:]+char
        dic[st] += 1
        ls.append(st)
    st = s[:tgt]
    if dic[st] > 0:
        return True
    dic[ls[0]] -= 1
    for i,char in enumerate(s[tgt:N-tgt]):
        st = st[1:]+char
        if dic[st] > 0:
            return True
        dic[ls[i+1]] -= 1
    return False

ng = maxlen + 1
ok = 0
while ng-ok > 1:
    tgt = (ok+ng)//2
    if solve(tgt):
        ok = tgt
    else:
        ng = tgt
print(ok)
### BUGGY CODE ###

n = int(input())
sl = []
for _ in range(n):
    sl.append(input())
rl=[]
ll=[]
for i in range(n):
    r=sorted(sl[i])
    if r in rl: ll[rl.index(r)]+=1
    else: rl.append(r); ll.append(0)
rslt=0
for i in ll:
    if not i==0: rslt+=((1+i)*i >> 1)
print(rslt)


### FIXED CODE ###

n = int(input())
S=[input() for _ in range(n)]
S=[''.join(sorted(i)) for i in S]
d={}
rslt=0
for s in S:
    if s in d:
        rslt+=d[s]
        d[s]+=1
    else:
        d[s]=1
print(rslt)
### BUGGY CODE ###

if __name__ == '__main__':
    N = int(input())
    H = list(map(int, input().split()))
    #print(N, H)
    for x in sorted(H, reverse=True):
        if any(map(lambda h:h <= x - 2, H[H.index(x):])):
            print('No')
            break
    else:
        print('Yes')

### FIXED CODE ###

if __name__ == '__main__':
    N = int(input())
    H = list(map(int, input().split()))
    #print(N, H)
    x1 = H.pop()
    for i in range(N-1):
        x2 = H.pop()
        if x1 - x2 <= -2:
            print('No')
            break
        elif x1 > x2:
            x1 = x2
    else:
        print('Yes')
### BUGGY CODE ###

from heapq import heappop,heappush,heapify
from collections import deque
import bisect
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
A = [int (i) for i in input().split()]
A.sort()
D = []
P = 0
for i in range(M):
  B,C = map(int, input().split())
  D.extend([C]*B)
  P += B
D.sort(reverse=True)
ans = sum(A)
for i in range(min(P,N)):
  if A[i] < D[i]:
    ans += D[i] - A[i]
  else:
    break
print(ans)

### FIXED CODE ###

N, M = map(int, input().split())
A = [int(i) for i in input().split()]
table = []
for i in range(N):
  table.append((A[i],1))
for i in range(M):
  b,c = map(int, input().split())
  table.append((c,b))
table.sort()
count = 0
ans = 0
while True:
  c, b = table.pop()
  if b <= N - count:
    ans += c*b
    count += b
  else:
    ans += (N-count)*c
    break
print(ans)
### BUGGY CODE ###

n,a=map(int,input().split())
N=list(map(int,input().split()))
def cal(a,b,c):
    if a==b==c==0:
        return 1
    if a>=1 and c<N[a-1]:
        return cal(a-1,b,c)
    if a>=1 and b>=1and c>=N[a-1]:
        return(cal(a-1,b,c)+cal(a-1,b-1,c-N[a-1]))
    else:
        return 0
    
ans=0
for k in range(n):
    ans+=cal(n,k+1,(k+1)*a)
print(ans)
        

### FIXED CODE ###

n,a=map(int,input().split())
lists=list(map(int,input().split()))

for i in range(n):
    lists[i]-=a
answer=0
dp=[[0 for i in range(5001)] for _ in range(51)]
#dp[i][j]で0からi枚目まで好きなように選択してそのそうわがｊ-2500となるような撮り方の総数
#最終的に求めるのはdp[i][0]である

for i in range(n+1):
    for j in range(4951):
        if i>=1 and j>=lists[i-1]:
            dp[i][j]=dp[i-1][j-lists[i-1]]+dp[i-1][j]
        if i>=1 and j<lists[i-1]:
            dp[i][j]=dp[i-1][j]
        else:
            if j==2500 and i==0:
                dp[i][j]=1
            elif j!=2500 and i==0:
                dp[i][j]=0
print(dp[n][2500]-1)
### BUGGY CODE ###

n = int(input())
l = list(map(int,input().split()))
k = [0 for i in range(n)]
t = []
for i in range(n-1,-1,-1):
  a = l[i]
  if a!=k[i]:
    t.append(i+1)
    for j in range(i,-1,-1):
      if (i+1)%(j+1)==0:
        k[j] += 1
        k[j] %= 2
if len(t)==0:
  print(0)
else:
  print(len(t))
  print(*t)

### FIXED CODE ###

n = int(input())
l = list(map(int,input().split()))
k = [0 for i in range(n)]
t = []
for i in range(n-1,-1,-1):
  a = l[i]
  s = 0
  for j in range(i,n,i+1):
    if j ==i:
      continue
    if k[j]==1:
      s += 1
      s %= 2
  if a!=(k[i]+s)%2:
    t.append(i+1)
    k[i] += 1
    k[i] %= 2
    
if len(t)==0:
  print(0)
else:
  print(len(t))
  print(*t)
### BUGGY CODE ###

N = int(input())
S = input()
number = []

for i in range(N):
    number.append(S.count('W', 0, i) + S.count('E', i, N))

print(min(number))

### FIXED CODE ###

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

eastNumber = S.count('E')
westNumber = 0
minimum = N

for i in range(N):
    if S[i] == 'E':
        eastNumber -= 1
        number = eastNumber + westNumber
        if minimum > number:
            minimum = number
    else:
        number = eastNumber + westNumber
        if minimum > number:
            minimum = number
        westNumber += 1

print(minimum)
### BUGGY CODE ###

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

dp = [0.0] * (N + 1)
dp[0] = 1.0

for i, p in enumerate(P, 1):
    dp = [p * dp[j - 1] + (1 - p) * dp[j] for j in range(N + 1)]

print(sum(dp[-(-N // 2):]))

### FIXED CODE ###

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

dp = [[0.0] * (N + 1) for _ in range(N + 1)]
dp[0][0] = 1.0

for i, p in enumerate(P, 1):
    for j in range(N + 1):
        dp[i][j] = p * dp[i - 1][j - 1] + (1 - p) * dp[i - 1][j]

print(sum(dp[N][-(-N // 2):]))