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

MOD=10**9+7

def moddiv(a,m):
    return pow(a,m-2,m)

def solve():
    res=-10**30
    minus,plus,zero=[],[],[]
    for i in range(N):
        if A[i]<0:
            minus.append(A[i])
        elif A[i]>0:
            plus.append(A[i])
        else:
            zero.append(A[i])
    cump=1
    plus.sort()
    minus.sort()
    for i in range(len(plus)):
        cump=cump*plus[i]%MOD
    j=0
    i=0
    cumm=1
    while(j<=min(len(minus),K)):
        if j>0:
            cumm=cumm*minus[j-1]*minus[j-2]%MOD
            newm=minus[j-1]*minus[j-2]
        if K-j>len(plus):
            j+=2
            continue
        oldp=1
        while(K-j<len(plus)-i):
            cump=cump*moddiv(plus[i],MOD)%MOD
            oldp*=plus[i]
            i+=1
        if j>0:
            if newm>oldp:
                res=cumm*cump%MOD
        else:
            res=max(res,cumm*cump%MOD)
        j+=2
    if res!=-10**30:
        return res
    if len(zero)>0:
        return 0
    li=minus+plus
    li.sort(key=lambda x:abs(x))
    res=1
    for i in range(K):
        res=res*li[i]%MOD
    return res
N,K=map(int,input().split())
A=list(map(int,input().split()))

if min(A)>=0:
    res=1
    A.sort(reverse=True)
    for i in range(K):
        res=res*A[i]%MOD
elif max(A)<=0:
    res=1
    if not K%2:
        A.sort()
        for i in range(K):
            res=res*A[i]%MOD
    else:
        A.sort(reverse=True)
        for i in range(K):
            res=res*A[i]%MOD
else:
    res=solve()
print(res)

### FIXED CODE ###

MOD=10**9+7

def moddiv(a,m):
    return pow(a,m-2,m)

def solve():
    res=-10**30
    minus,plus,zero=[],[],[]
    for i in range(N):
        if A[i]<0:
            minus.append(A[i])
        elif A[i]>0:
            plus.append(A[i])
        else:
            zero.append(A[i])
    cump=1
    plus.sort()
    minus.sort()
    for i in range(len(plus)):
        cump=cump*plus[i]%MOD
    j=0
    i=0
    cumm=1
    while(j<=min(len(minus),K)):
        if j>0:
            cumm=cumm*minus[j-1]*minus[j-2]%MOD
            newm=minus[j-1]*minus[j-2]
        else:
            newm=0
        isbig=True
        if K-j>len(plus):
            j+=2
            continue
        oldp=1
        while(K-j<len(plus)-i):
            cump=cump*moddiv(plus[i],MOD)%MOD
            if isbig:
                oldp*=plus[i]
            if oldp>newm:
                isbig=False
            i+=1
        if j>0:
            if newm>oldp:
                res=cumm*cump%MOD
        else:
            res=max(res,cumm*cump%MOD)
        j+=2
    if res!=-10**30:
        return res
    if len(zero)>0:
        return 0
    li=minus+plus
    li.sort(key=lambda x:abs(x))
    res=1
    for i in range(K):
        res=res*li[i]%MOD
    return res
N,K=map(int,input().split())
A=list(map(int,input().split()))

if min(A)>=0:
    res=1
    A.sort(reverse=True)
    for i in range(K):
        res=res*A[i]%MOD
elif max(A)<=0:
    res=1
    if not K%2:
        A.sort()
        for i in range(K):
            res=res*A[i]%MOD
    else:
        A.sort(reverse=True)
        for i in range(K):
            res=res*A[i]%MOD
else:
    res=solve()
print(res)
### BUGGY CODE ###

from functools import lru_cache

N = int(input())

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

dish = N*4
dp = [[[-1 for k in range(dish )]for j in range(dish)]for i in range(dish)]

@lru_cache(maxsize=N*4)
def calc(i, j, k):
    if dp[i][j][k] >= 0:
        return dp[i][j][k]
    if i == 0 and j == 0 and k == 0:
        return 0
    ret = 0
    if i > 0:
        ret += calc(i - 1, j, k) * i
    if j > 0:
        ret += calc(i + 1, j - 1, k) * j 
    if k > 0:
        ret += calc(i, j + 1, k -1) * k

    ret += N
    ret *= 1.0 / (i + j + k)
    dp[i][j][k] = ret
    return ret


one = A.count(1)
two = A.count(2)
three = A.count(3)

ret = calc(one,two,three)
print(ret)


### FIXED CODE ###

import sys
input = sys.stdin.readline

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

    dp = [[[0.0 for k in range(N + 1)]for j in range(N + 1)]for i in range(N + 1)]


    one = A.count(1)
    two = A.count(2)
    three = A.count(3)

    for k in range(three + 1):
        for j in range(two + three + 1 - k):
            for i in range(one + two + three + 1 -k -j):
                if i == 0 and j == 0 and k == 0:
                    continue
                ret = N * 1.0
                if i > 0:
                    ret += dp[i - 1][j][k] * i
                if j > 0:
                    ret += dp[i + 1][j - 1][k] * j 
                if k > 0:
                    ret += dp[i][j + 1][k -1] * k

                dp[i][j][k] = ret / (i + j + k)

    print(dp[one][two][three])

main()
### BUGGY CODE ###

#! /usr/bin/env python3

import sys
import numpy as np
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

N, K, *A = map(int, read().split())

ans = A

for _ in range(K):
    A_ = ans
    ans = [0] * N
    for i in range(N):
        acc = A_[i]
        for j in range(max(0, i - acc), min(N - 1, i + acc) + 1):
            ans[j] += 1
            ans[j] = min(ans[j], N)
    A_ = ans

print(*ans)


### FIXED CODE ###

#! /usr/bin/env python3

import sys
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

N, K, *A = map(int, read().split())

for _ in range(min(K, 42)):
    acc = [0] * (N + 1)
    for i, a in enumerate(A):
        l = max(0, i - a)
        r = min(N, i + a + 1)
        acc[l] += 1
        acc[r] -= 1
    acc[0] = min(N, acc[0])
    for i in range(N):
        acc[i + 1] = min(N, acc[i] + acc[i + 1])
    A = acc[:-1]
    if all(a == N for a in A):
        break
print(*A)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
A.sort()
B = []
C = []
Q = int(input())
for i in range(Q):
    b, c = map(int,input().split())
    for j, a in enumerate(A):
        if a == b:
            A[j] = c
    print(sum(A))


### FIXED CODE ###

from collections import Counter
N = int(input())
A = list(map(int,input().split()))
Q = int(input())
counter = Counter(A)
res = sum(A)
for i in range(Q):
    b, c = map(int,input().split())
    res -= counter[b] * b
    res += counter[b] * c
    counter[c] += counter[b]
    counter[b] = 0
    print(res)
### BUGGY CODE ###

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

for i in range(0,a[0]*2+1,2):
    ans = [i]
    for j in range(1,n):
        tmp = (a[j-1]-ans[j-1]//2)*2
        if tmp%2 == 0:
            ans.append(tmp)
        else:
            break
    if (ans[-1]//2 + ans[0]//2) == a[-1]:
        print(*ans)
        exit()

### FIXED CODE ###

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

s = sum(a)
s1 = 0
for i in range(1,n,2):
    s1 += a[i]

ans = [s-s1*2]
for i in range(1,n):
    ans.append((a[i-1]-ans[i-1]//2)*2)

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

n, x, y = map(int, input().split())

node = list(range(1, n + 1))

dis_list = []

for i in node:
    for j in node:
        if j != i:
            dis = min(abs(j - i), abs(x - i) + 1 + abs(y - j), abs(y - i) + 1 + abs(x - j))
            dis_list.append(dis)

for dis in range(1, n):
    print(len([i for i in dis_list if i == dis]) // 2)

### FIXED CODE ###

n, x, y = map(int, input().split())

dis_list = [0] * (n - 1)

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

for i in dis_list:
    print(i)
### BUGGY CODE ###

n=int(input())
L=list(map(int,input().split()))
L=sorted(L)

from itertools import combinations
from bisect import bisect_right,bisect_left

comb=combinations(L, 2)
cnt=0
for cb in comb:
    b,c=min(cb), max(cb)
    # a must be b or lower
    hi=bisect_left(L, b)
    low=bisect_right(L, c-b)
    #print(b,c,hi,low)
    cnt+=max(0,hi-low)
print(cnt)

### FIXED CODE ###

from bisect import bisect_left

n=int(input())
L=list(map(int,input().split()))
L=sorted(L)
ans=0
for i in range(n-2):
    a=L[i]
    for j in range(i+1,n-1):
        ans+=bisect_left(L,a+L[j])-j-1
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 6)  # 変更

from bisect import bisect_left,bisect
n = int(input())
x = list(map(int,input().split()))
t = n.bit_length()
kprv = [[10**10 for i in range(t+1)] for j in range(n)]
for i in range(t):
    for j in range(n):
        if j + pow(2,i) > n-1:
            break
        kprv[j][i] = x[j+2**i] - x[j]

L = int(input())
q = int(input())

for _ in range(q):
    a , b = map(lambda x:int(x)-1,input().split())
    cou = 0
    if a > b:
        a , b = b , a
    now = a
    while now < b:
        cou += 1
        p = L
        while True:
            nex = bisect(kprv[now],p)
            if nex == 0:
                break
            else:
                p -= kprv[now][nex-1]
                now += pow(2,nex-1)
    print(cou)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 6)  # 変更
from bisect import bisect_left,bisect

n = int(input())
x = list(map(int,input().split()))
L = int(input())
t = n.bit_length()
prv = [n-1] * n
for i in range(n):
    prv[i] = bisect(x,x[i]+L) - 1
kprv = [prv]
S = prv
for i in range(t-1):
    kar = [n-1] * n
    for j in range(n):
        kar[j] = S[S[j]]
    kprv.append(kar)
    S = kar

q = int(input())
for _ in range(q):
    a , b = map(lambda x:int(x)-1,input().split())
    if a > b:
        a , b = b , a
    lef = 0
    rig = n-1
    while rig - lef > 1:
        mid = (rig+lef)//2
        p = mid.bit_length()
        now = a
        for i in range(p):
            if (mid>>i) & 1 == 1:
                now = kprv[i][now]
        if now >= b:
            rig = mid
        elif now < b:
            lef = mid
    print(rig)
### BUGGY CODE ###

from fractions import gcd
mod = 10**9+7
def main():
  n = int(input())
  A = list(map(int, input().split()))
  m = A[0]
  for i in range(1, n):
    m = m // gcd(m, A[i]) * A[i]
  ans = 0
  for i in range(n):
    ans += m//A[i]
  print(ans%mod)
if __name__ == "__main__":
  main()

### FIXED CODE ###

from fractions import gcd
mod = pow(10, 9)+7
n = int(input())
A = list(map(int, input().split()))
m = A[0]
for i in range(1, n):
  m = m // gcd(m, A[i]) * A[i]
ans = 0
for i in A:
  ans += m//i
print(ans%mod)
### BUGGY CODE ###

n = int(input())
s = str(input())
count = 0

for k in range(n):
    for j in range(n):
        for i in range(n):
            if i < j < k:
                a = (s[i], s[j], s[k])
                #print(a)
                a_set = set(a)
                #print(a_set)
                if len(a_set) == 3 and (j - i) != (k - j):
                    count += 1
            else:
                continue

print(count)

### FIXED CODE ###

n = int(input())
s = str(input())
count = 0
sum_RGB = s.count("R") * s.count("G") * s.count("B")
for i in range(n):
    for j in range(i, n):  # rangeをiからにすることでループ減らせる
        # for k in range(n): # sum_RGBから減らしていくのでｋがi,jで決まる
        k = 2*j - i
        if k < n:
            a = (s[i], s[j], s[k])
            # print(a)
            a_set = set(a)
            # print(a_set)
            if len(a_set) == 3:
                count += 1

print(sum_RGB - count)
### BUGGY CODE ###

import collections
n = int(input())
li = list(map(int, input().split()))
for k in range(n):
    dic = collections.Counter(li)
    dic[li[k]] -=1
    x = 0
    for d in dic.values():
        x+= int(d*(d-1)*0.5)
    print(x)

### FIXED CODE ###

import collections
n = int(input())
a = map(int, input().split())
li = []
for i in a:
    li.append(i)
collections.Counter(li)
m = 0
dic = collections.Counter(li)
for i in dic.values():
    m += int(i*(i-1)*0.5)
for k in range(n):
      print(m-dic[li[k]]+1)
### BUGGY CODE ###

N = int(input().strip())
A = [ int(i) for i in input().strip().split(' ')]
#unique_supervisor = list(set(A))

for i in range(1, N+1):
    print(list.count(A, i)) 

### FIXED CODE ###

N = int(input().strip())
data = [0 for _ in range(N)]
for i in input().strip().split(' '):
    data[int(i)-1] += 1

for d in data:
    print(d)
### BUGGY CODE ###

s = input()
q = int(input())

query = []
flag = 0
ctn = 0
for _ in range(q):
    temp = input().split()
    if len(temp) == 1:
        if flag == 0:
            flag = 1
        else:
            flag = 0
        ctn += 1
    else:
        query.append(temp + [flag])

for q in query:
    if q[-1] == 0:
        if q[1] == "1":
            s = q[2] + s
        else:
            s = s + q[2]
    else:
        if q[1] == "1":
            s = s + q[2]
        else:
            s = q[2] + s

if ctn % 2 == 1:
    print(s[::-1])
else:
    print(s)

### FIXED CODE ###

from collections import deque

def main():

    s = deque(input())
    q = int(input())

    flag = 0
    query = []

    for _ in range(q):
        temp = input().split()
        if len(temp) == 1:
            flag += 1
        else:
            query.append(temp + [flag%2])

    for q in query:
        if q[-1] == 0:
            if q[1] == "1":
                s.appendleft(q[2])
            else:
                s.append(q[2])
        else:
            if q[1] == "1":
                s.append(q[2])
            else:
                s.appendleft(q[2])

    if flag % 2 == 1:
        print("".join(list(s)[::-1]))
    else:
        print("".join(s))

main()
### BUGGY CODE ###

#l=list(map(int, input().split()))
n,k,q=map(int, input().split())

l = []
for i in range(n):
    l.append(k)

for a in range(q):
    j = int(input())
    for i in range(len(l)):
        if (j-1 != i):
            l[i] -=1

for i in l:
    if (i > 0):
        print("Yes")
    else:
        print("No")



### FIXED CODE ###

#l=list(map(int, input().split()))
n,k,q=map(int, input().split())

l = []
for i in range(n):
    l.append(k)

for a in range(q):
    j = int(input())
    l[j-1] += 1

for i in l:
    if (i - q > 0):
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

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

T = [0]*(max(A)+1)
D = [0]*(max(A)+1)
for i in A:
    # iの2以上の倍数の値は1に
    for j in range(2*i, max(A)+1, i):
        T[j] += 1
    # ダブってる値は2以上に
    D[i] += 1

# Tが0かつDが1の数を数える
ans = 0
for i in A:
    if T[i] == 0 and D[i] == 1:
        ans += 1

print(ans)

### FIXED CODE ###

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

cnt = [0] * ((10 ** 6) + 1)

for elem in a:
    cnt[elem] += 1

unique = []

for i in range((10 ** 6) + 1):
    if cnt[i] == 1:
        unique.append(i)

cnt = [0] * ((10 ** 6) + 1)

a = list(set(a))

for elem in a:
    for m in range(elem * 2, (10 ** 6) + 1, elem):
        cnt[m] = 1

ans = 0
        
for elem in unique:
    if cnt[elem] == 0:
        ans += 1

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

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

dp = [float("inf") for _ in range(N)]
dp[0] = 0
for i in range(N - 1):
    for j in range(1, min(K + 1, N - i)):
        dp[i + j] = min(dp[i + j], dp[i] + abs(h[i + j] - h[i]))
print(dp[N - 1])

### FIXED CODE ###

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

dp = [float("inf") for _ in range(N)]
dp[0] = 0
for i in range(N - 1):
    for j in range(1, min(K + 1, N - i)):
        dp[i + j] = min(dp[i + j], dp[i] + abs(h[i + j] - h[i]))
print(dp[N - 1])
### BUGGY CODE ###

import numpy as np
n=int(input())
cnt=np.zeros(n+1,dtype = int)
for i in range(1,n+1):
    cnt[i::i]+=1
ans=cnt*np.arange(n+1)
print(sum(ans))

### FIXED CODE ###

n=int(input())
ans=0
for i in range(1,n+1):
    k=n//i
    ans+=i*k*(k+1)//2
print(ans)
### BUGGY CODE ###

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

from operator import mul
from functools import reduce

scores = []
judge_str = {True: "Yes", False: "No"}

for i in range(K, N+1):
    scores.append(reduce(mul, A[i-K:i]))
    if len(scores) == 1:
        continue
    else:
        print(judge_str[scores[i-K-1] < scores[i-K]])


### FIXED CODE ###

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

judge_str = {True: "Yes", False: "No"}

for i in range(K+1, N+1):
    print(judge_str[A[i-K-1] < A[i-1]])
### BUGGY CODE ###

import sys
import heapq
import bisect

mod = 10**9+7
dd = ((-1,0),(1,0),(0,-1),(0,1))

def I(): return(int(sys.stdin.readline()))
def LI(): return([int(x) for x in sys.stdin.readline().split()])
def S(): return(sys.stdin.readline()[:-1])
def IR(n): return([I() for _ in range(n)])

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

def LCM(a,b):
    return a * b // GCD(a,b)

def main():
    N,Q = LI()
    Parent = [-1] * N
    tree = [False]*N
    tree[0] = True
    cur_tree = []
    for _ in range(N-1):
        a,b = LI()
        cur_tree.append([a-1,b-1])

    counter = [0] * N
    for _ in range(Q):
        p,x = LI()
        counter[p-1] += x

    while cur_tree:
        nxt_tree = []
        for a,b in cur_tree:
            if tree[a]:
                Parent[b] = a
                tree[b] = True
            elif tree[b]:
                Parent[a] = b
                tree[a] = True
            else:
                nxt_tree.append([a,b])
        cur_tree = [x for x in nxt_tree]

    r = []

    for i in range(N):
        ans = counter[i]
        p = Parent[i]
        while p != -1:
            ans += counter[p]
            p = Parent[p]
        r.append(ans)

    return(" ".join(map(str,r)))




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


### FIXED CODE ###

import sys
import heapq
import bisect

mod = 10**9+7
dd = ((-1,0),(1,0),(0,-1),(0,1))

def I(): return(int(sys.stdin.readline()))
def LI(): return([int(x) for x in sys.stdin.readline().split()])
def S(): return(sys.stdin.readline()[:-1])
def IR(n): return([I() for _ in range(n)])

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

def LCM(a,b):
    return a * b // GCD(a,b)

def main():
    N,Q = LI()
    node=[[] for _ in range(N)]
    flag = [True for _ in range(N)]
    for _ in range(N-1):
        a,b = LI()
        node[a-1].append(b-1)
        node[b-1].append(a-1)

    counter = [0] * N
    for _ in range(Q):
        p,x = LI()
        counter[p-1] += x

    cur = [[0,0]]
    while cur:
        nxt = []
        for a,c in cur:
            flag[a]=False
            counter[a]+=c
            for b in node[a]:
                if flag[b]:
                    nxt.append([b,counter[a]])
        cur = [x for x in nxt]

    r = [counter[i] for i in range(N)]

    return(" ".join(map(str,r)))

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

n = int(input())
pp = list(map(int, input().split()))

cnt = 0

for i in range(n):
    for p in pp[:i + 1]:
        if pp[i] > p:
            break
    else:
        cnt += 1

print(cnt)

### FIXED CODE ###

n = int(input())
pp = list(map(int, input().split()))

cnt = 0
min_val = 2 * 10 ** 5 + 1

for p in pp:
    if min_val >= p:
        cnt += 1
        min_val = p

print(cnt)
### BUGGY CODE ###

s = input()
t = input()
for i in range(len(s)):
    if s[i] != t[i]:
        s = s.translate(str.maketrans({s[i]:t[i],t[i]:s[i]}))
if s == t:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

s = input()
t = input()
l = [0]*26
flag = 0
for i in range(len(s)):
    if l[ord(s[i])-ord("a")] == 0:
        if t[i] not in l:
            l[ord(s[i])-ord("a")] = t[i]
        else:
            flag = 1
            break
    else:
        if l[ord(s[i])-ord("a")] != t[i]:
            flag = 1
            break
if flag == 0:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

N=int(input())
a=4/N
for h in range(1,3501):
    H=1/h
    for n in range(h,3501):
        flag=0
        if a-H-1/n-h<=0 and a-H-1/n-1/3500>=0:

            st,end=h,3500
            for w in [st,end]:
                B=4*h*n*w-(n*w+h*w+h*n)*N
                if B==0:
                    break
            while st!=end:
                #print(h,n,st,end)
                w=int((st+end)/2)
                if end-st==1:
                    end=w
                    st=w
                B=4*h*n*w-(n*w+h*w+h*n)*N
                if B==0:
                    flag=1
                    break
                elif B>0:
                    end=w
                else:
                    st=w

        if flag:
            break
    if flag:
        break

print(h,n,w)


### FIXED CODE ###

N=int(input())
a=4/N
h_st=max(int(N*(1/4))-1,1)
#h_st=1
for h in range(h_st,3501):
    H=1/h
    for n in range(h,3501):
        flag=0
        if 4*h*n*n-(n*n+h*n+h*n)*N<=0 and 4*h*n*3500-(n*3500+h*3500+h*n)*N>=0:

            st,end=n,3500
            for w in [st,end]:
                B=4*h*n*w-(n*w+h*w+h*n)*N
                if B==0:
                    flag=1
                    break
            while st!=end:
                #print(h,n,st,end)
                w=int((st+end)/2)
                if end-st==1:
                    end=w
                    st=w
                B=4*h*n*w-(n*w+h*w+h*n)*N
                if B==0:
                    flag=1
                    break
                elif B>0:
                    end=w
                else:
                    st=w

        if flag:
            break
    if flag:
        break

print(h,n,w)
### BUGGY CODE ###

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

ans = 1

for i in range(n):
    ans *= a[i]

if ans > 10 ** 18:
    print(-1)
    exit()

print(ans)


### FIXED CODE ###

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

ans = 1

if 0 in a:
    print(0)
    exit()
for i in range(n):
    ans *= a[i]
    if ans > 10 ** 18:
        print(-1)
        exit()


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

R,G,B,N = map(int,input().split())
count = 0
for r in range(N//R+1):
  for g in range(N//G+1):
    if (N-R*r-G*g)%B == 0 and (N-R*r-G*g) > -1:
      count += 1
print(count)



### FIXED CODE ###

R,G,B,N = map(int,input().split())
cnt = 0
for r in range(N//R+1):
  for g in range((N-R*r)//G+1):
    if (N-R*r-G*g)%B == 0:
      cnt += 1
print(cnt)
### BUGGY CODE ###

N = int(input())
p = [0]
p += list(map(float, input().split(' ')))
dp = [[0 for _ in range(N + 1)] for _ in range(N + 1)]
dp[1][0], dp[1][1] = 1- p[1], p[1]
for i in range(2, N + 1):
  for j in range(i + 1):
      dp[i][j] = dp[i-1][j-1]  * p[i]
      dp[i][j] += dp[i-1][j] * (1 - p[i])
res = 0
for i in range(N // 2 + 1, N + 1):
  res += dp[N][i]
print(res)

### FIXED CODE ###

N = int(input())
p = [0]
p += list(map(float, input().split(' ')))
dp = [[0 for _ in range(N + 1)] for _ in range(N + 1)]
dp[1][0], dp[1][1] = 1- p[1], p[1]
for i in range(2, N + 1):
  for j in range(i + 1):
      dp[i][j] = dp[i-1][j-1]  * p[i]
      dp[i][j] += dp[i-1][j] * (1 - p[i])
res = 0
for i in range(N // 2 + 1, N + 1):
  res += dp[N][i]
print(res)