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

import numpy as np


def read():
    N = int(input().strip())  # N <= 10**5
    to = [[] for _ in range(N)]
    cost = [[] for _ in range(N)]
    for i in range(N-1):
        # u[i] < v[i] は保証されている
        u, v, w = list(map(int, input().strip().split()))
        to[u-1].append(v-1)
        to[v-1].append(u-1)
        cost[u-1].append(w % 2)
        cost[v-1].append(w % 2)
    return N, to, cost


def solve(N, to, cost):
    c = np.ones((N, ), dtype=np.uint8) * -1  # -1: unvisited, 0: white, 1: black
    q = list()
    c[0] = 0
    q.append(0)
    while len(q) > 0:
        s = q.pop()
        for t, co in zip(to[s], cost[s]):
            if c[t] == -1:
                if co:
                    c[t] = 1 - c[s]
                else:
                    c[t] = c[s]
                q.append(t)
    return c


if __name__ == '__main__':
    inputs = read()
    colors = solve(*inputs)
    for col in colors:
        print("%d" % col)


### FIXED CODE ###

import numpy as np


def read():
    N = int(input().strip())  # N <= 10**5
    to = [[] for _ in range(N)]
    cost = [[] for _ in range(N)]
    for i in range(N-1):
        # u[i] < v[i] は保証されている
        u, v, w = list(map(int, input().strip().split()))
        to[u-1].append(v-1)
        to[v-1].append(u-1)
        cost[u-1].append(w % 2)
        cost[v-1].append(w % 2)
    return N, to, cost


def solve(N, to, cost):
    c = [-1] * N  # -1: unvisited, 0: white, 1: black
    q = list()
    c[0] = 0
    q.append(0)
    while len(q) > 0:
        s = q.pop()
        for t, co in zip(to[s], cost[s]):
            if c[t] == -1:
                if co:
                    c[t] = 1 - c[s]
                else:
                    c[t] = c[s]
                q.append(t)
    return c


if __name__ == '__main__':
    inputs = read()
    colors = solve(*inputs)
    for col in colors:
        print("%d" % col)
### BUGGY CODE ###

import numpy as np
n = int(input())
a = list(map(int, input().split()))
ap = [i+1 for i in a]
am = [i-1 for i in a]
a = np.array([ap, a, am])

maxs = 0
for i in range(a.min(), a.max() + 1):
  maxs = max(maxs, (a==i).sum())

print(maxs)

### FIXED CODE ###

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

for i in a:
    li.append(i-1)
    li.append(i+1)
    li.append(i)

import collections
L=collections.Counter(li)
print(max(L.values()))
### BUGGY CODE ###

import math
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
N = int(input())

# all = 0
# for i in range(2, N+1):
#     basyo = combinations_count(N, i)
#     # basyo = permutations_count(N, i) / 2  # 9と0が入る場所。i箇所。
#     # zerokyuu = i*(i-1)*2(i-2)  # 入る場所に0と9を入れる。
#     zerokyuu = 2**i - 2  # 全部0と全部9を抜く。
#     iti_hachi = 8**(N-i)  # 残った部分に1-8が入る全通り
#     all += basyo * zerokyuu * iti_hachi

lis = [int(combinations_count(N, i) * (2**i - 2) * (8**(N-i))) for i in range(2, N+1)]
print(sum(lis) % (10**9+7))

### FIXED CODE ###

N = int(input())
print((10**N - 9**N - 9**N + 8**N) % (10**9+7))
### BUGGY CODE ###


if __name__ == "__main__":
    N = int(input())
    A = list(map(int, input().split()))
    ans = A[0]
    for i in A[1:]:
        ans *= i
    if ans > 10**18:
        ans = -1
    print(ans)


### FIXED CODE ###

import numpy as np

if __name__ == "__main__":
    N = int(input())
    A = list(map(int, input().split()))
    ans = A[0]
    if 0 in A:
        ans = 0
    else:
        for i in A[1:]:
            ans *= i
            if ans > 1000000000000000000:
                ans = -1
                break
    print(ans)
### BUGGY CODE ###

import re

S = input()

trimmed = 0

while True:
    tmp = re.split("01|10", S)
    if len(tmp) == 1:
        break
    else:
        trimmed = trimmed + len(tmp) - 1
        S = "".join(tmp)

print(trimmed * 2)


### FIXED CODE ###

S = input()

zero = 0
one = 0

for ch in S:
    if ch == "0":
        zero = zero + 1
    else:
        one = one + 1

print(min(zero, one) * 2)
### BUGGY CODE ###

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

from math import gcd

def prime_factorize(n):
    a = set()
    while n % 2 == 0:
        a.add(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.add(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.add(n)
    return a

f = True
l = set()
for i in range(n):
    x = prime_factorize(a[i])
    y = l|x
    if len(l)+len(x)!=len(y):
        f = False
        break
    l = y
    
if f:
    print('pairwise coprime')
    exit()

g = a[0]
for i in range(n):
    g = gcd(g,a[i])

if g==1:
    print('setwise coprime')
else:
    print('not coprime')

### FIXED CODE ###

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

from math import gcd
g = a[0]
for i in range(n):
    g = gcd(g,a[i])

if g!=1:
    print('not coprime')
    exit()

f = True
l = set()
for i in a:
    for j in range(2,int(i**0.5)+1):
        if i%j==0:
            if i in l:
                f = False
                break
            l.add(i)
        while i%j==0:
            i = i//j
        if i<2:
            break
    if i>1:
        if i in l:
            f = False
            break
        l.add(i)
        
if f:
    print('pairwise coprime')
else:
    print('setwise coprime')
### BUGGY CODE ###

# correct answer
n = int(input())
s = input()
r = s.count("R")
g = s.count("G")
b = s.count("B")
total = r*g*b
for i in range(n):
    for d in range(n):
        j = i + d
        k = j + d
        if k >= n:
            continue
        if s[i] != s[j] and s[j] != s[k] and s[k] != s[i]:
            total -= 1
print(total)

### FIXED CODE ###

n = int(input())
s = input()
r = s.count("R")
g = s.count("G")
b = s.count("B")
total = r*g*b
for i in range(n):
    for d in range(n):
        j = i + d
        k = j + d
        if k >= n:
            break
        if s[i] != s[j] and s[j] != s[k] and s[k] != s[i]:
            total -= 1
print(total)
### BUGGY CODE ###

H, N = map(int, input().split())
L = [list(map(int, input().split())) for _ in range((N))]
dp = [float('inf')] * (H + 1)
dp[0] = 0
for h in range(H):
    for dmg, cst in L:
        next = min(h + dmg, H)
        dp[next] = min(dp[next], dp[h] + cst)
print(dp[-1])


### FIXED CODE ###

def main():
    H, N = map(int, input().split())
    magic = [list(map(int, input().split())) for _ in range((N))]
    dp = [float('inf')] * (H + 1)
    dp[0] = 0
    for h in range(H):
        for dmg, cst in magic:
            next = min(h + dmg, H)
            dp[next] = min(dp[next], dp[h] + cst)
    print(dp[h+1])
main()
### BUGGY CODE ###

import bisect
import heapq
import math
import queue
import sys


def main():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    
    A = [i for i in map(int, input().split())]
    A.sort()

    for i in range(M):
        B, C = map(int, input().split())
        insert_index = bisect.bisect_left(A, C)
        A[insert_index:insert_index] = [C for i in range(B)]
        A = A[-N:]

    print(sum(A))


if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
from collections import defaultdict


def main():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    
    A = defaultdict(int)
    for i in map(int, input().split()):
        A[i] += 1
        
    for i in range(M):
        B, C = map(int, input().split())
        A[C] += B
        
    ret = 0
    count = 0
    for value, num_value in sorted(A.items(), key=lambda x:x[0])[::-1]:
        num_value = min(num_value, N - count)
        ret += value * num_value
        count += num_value
        if num_value == N:
            break
    
    print(ret)


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

N = int(input())
A = [0 for _ in range(N)]
for i in range(N):
    A[i] = int(input())
lst = [A.count(a)%2 for a in set(A)]
print(sum(lst))

### FIXED CODE ###

N = int(input())
A = []
for i in range(N):
    A.append(int(input()))
As = sorted(A)
num = 0
i = 0
while i < N:
    count = 0
    j = As[i]
    while i < N and As[i] == j:
        count += 1
        i += 1
    if count % 2 == 1:
        num += 1
print(num)
### BUGGY CODE ###

n=int(input())
comb=[]
ans=[]


for k in range(1, n+1):
    flag=False
    for x in range(1, k+1):
        if 6*x**2 >k:
            break
        else:
            for y in range(x, k+1):
                for z in range(y, k+1):
                    if (x+y+z)**2 - x*y-y*z-z*x==k:
                        comb.append((x,y,z))
                        flag=True
                        break
    
    if flag:
        pass
    else:
        comb.append((0, 0, 0))


l=len(comb)

for s in range(l):
    if comb[s][0]==comb[s][1]==comb[s][2]==0:
        ans.append(0)
    elif comb[s][0]==comb[s][1]==comb[s][2]!=0:
        ans.append(1)
    elif comb[s][0]!=comb[s][1] and comb[s][1]!=comb[s][2] and comb[s][2]!=comb[s][0]:
        ans.append(6)
    else:
        ans.append(3)

for i in range(l):
    print(ans[i])

### FIXED CODE ###

n=int(input())
cnt=[0]*(n+1)

for x in range(1, 101):
    for y in range(1, 101):
        for z in range(1, 101):
            tmp=x*x + y*y + z*z + x*y + y*z + z*x
            if tmp <=n:
                cnt[tmp]+=1


for i in range(1, n+1):
    print(cnt[i])
### BUGGY CODE ###

N = int(input())
A = [int(n) for n in input().split()]
for i in range(N):
	A_init = A
	A = [n for n in A if n != i+1]
	print(len(A_init) - len(A))

### FIXED CODE ###

N = int(input())
A =[int(n) for n in input().split()]
b = [0]*N
for i in A:
  b[i-1]+=1
for i in range(N):
  print(b[i])
### BUGGY CODE ###

n,k=map(int,input().split())
N=abs(n-k)
while N<n:
    n=N
    N=abs(n-k)
print(n)


### FIXED CODE ###

n,k=map(int,input().split())
n%=k
N=abs(n-k)
while N<n:
    n=N
    N=abs(n-k)
print(n)
### BUGGY CODE ###

l, r = map(int, input().split())
mod = 2019

r = min(r, l+4038)
ans = 2018
for i in range(l, r+1):
    for j in range(i+1, r+1):
        x = i * j % mod
        ans = min(ans, x)
print(ans)


### FIXED CODE ###

l, r = map(int, input().split())
mod = 2019
 
r = min(r, l+4038)
ans = 2018
for i in range(l, r+1):
    for j in range(i+1, r+1):
        x = i * j % mod
        ans = min(ans, x)
print(ans)
### BUGGY CODE ###

n, k, *p = map(int, open(0).read().split())

max_e = 0
for i in range(n-k+1):
  e = 0
  
  for j in range(i, i+k):
    e += (p[j]+1)/2
  
  if e > max_e:
    max_e = e

print(max_e)

### FIXED CODE ###

n, k, *p = map(int, open(0).read().split())

q = []
for p_i in p:
  q.append((p_i+1)/2)
  
s = [0]
pre_s = 0
for q_i in q:
  pre_s += q_i
  s.append(pre_s)

ans = 0
for i in range(n-k+1):
  if ans < (s[i+k] - s[i]):
    ans = s[i+k] - s[i]
    
print(ans)
### BUGGY CODE ###

N, Ma, Mb = map(int, input().split())
L = [[int(i) for i in input().split()] for _ in range(N)]

inf = N * 101
dp = [[[inf for _ in range(N*10+11)] for _ in range(N*10+11)] for _ in range(N+1)]

dp[0][0][0] = 0
for i in range(N):
    for j in range(N*10):
        for k in range(N*10):
            dp[i+1][j][k] = min(dp[i+1][j][k], dp[i][j][k])
            dp[i+1][j+L[i][0]][k+L[i][1]] = min(dp[i+1][j+L[i][0]][k+L[i][1]], dp[i][j][k] + L[i][2])
ans = inf
for i in range(1, N*10//max(Ma, Mb)):
    ans = min(ans, dp[N][i*Ma][i*Mb])

if ans == inf:
    print(-1)
else:
    print(ans)


### FIXED CODE ###

import itertools
N, Ma, Mb = map(int, input().split())
L = [[int(i) for i in input().split()] for _ in range(N)]

inf = N * 101
dp = [[[inf for _ in range(N*10+11)] for _ in range(N*10+11)] for _ in range(N+1)]

dp[0][0][0] = 0
cmb = itertools.product(range(N), range(N*10), range(N*10))
for i, j, k in cmb:
    dp[i+1][j][k] = min(dp[i+1][j][k], dp[i][j][k])
    dp[i+1][j+L[i][0]][k+L[i][1]] = min(dp[i+1][j+L[i][0]][k+L[i][1]], dp[i][j][k] + L[i][2])
ans = inf
for i in range(1, N*10//max(Ma, Mb)):
    ans = min(ans, dp[N][i*Ma][i*Mb])

if ans == inf:
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

mod=10**9+7
n=int(input())
T=[int(i) for i in input().split()]
A=[int(i) for i in input().split()]
Tres=[0]*n
Ares=[0]*n
Tres[0]=[0,T[0]]
Ares[-1]=[0,A[-1]]
for i in range(1,n):
  if T[i]!=T[i-1]:
    Tres[i]=[0,T[i]]
  else:
    Tres[i]=[1,T[i]]
  if A[-i-1]!=A[-i]:
    Ares[-i-1]=[0,A[-i-1]]
  else:
    Ares[-i-1]=[1,A[-i-1]]
ans=1
for i in range(n):
  ta,tb=Tres[i]
  aa,ab=Ares[i]  
  if ta==1 and aa==1:
    ans=ans*min(tb,ab)
  elif ta==0 and aa==1 and tb>ab:
    ans=0
  elif ta==1 and aa==0 and tb<ab:
    ans=0
  elif ta==0 and aa==0 and tb!=ab:
    ans=0
print(ans%mod)


### FIXED CODE ###

mod=10**9+7
n=int(input())
T=[int(i) for i in input().split()]
A=[int(i) for i in input().split()]
Tres=[0]*n
Ares=[0]*n
Tres[0]=(0,T[0])
Ares[n-1]=(0,A[n-1])
for i in range(1,n):
  if T[i]>Tres[i-1][1]:
    Tres[i]=(0,T[i])
  else:
    Tres[i]=(1,T[i])
  if A[n-i-1]>Ares[n-i][1]:
    Ares[n-i-1]=(0,A[n-i-1])
  else:
    Ares[n-i-1]=(1,A[n-i-1])
if Tres[0]<=Ares[0]:
  ans=1
else:
  ans=0
for i in range(1,n):
  ta,tb=Tres[i]
  aa,ab=Ares[i]  
  if ta==aa==1:
    ans=ans*min(tb,ab)%mod
  elif ta==0 and aa==1 and tb>ab:
    ans=0
  elif ta==1 and aa==0 and tb<ab:
    ans=0
  elif ta==0 and aa==0 and tb!=ab:
    ans=0
print(ans%mod)
### BUGGY CODE ###

def main():
    N, Q = map(int, input().split())
    S = input()
    l = [0] * Q
    r = [0] * Q
    for i in range(Q):
        l[i], r[i] = map(int, input().split())
    count = [S[l[i]-1:r[i]].count('AC') for i in range(Q)]
    for i in range(Q):
        print(count[i])
main()

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
l = [0] * Q
r = [0] * Q
for i in range(Q):
    l[i], r[i] = map(int, input().split())
counter = [0] * N

for i in range(N-1):
    if S[i:i+2] == 'AC':
        counter[i+1] += counter[i] + 1
    else:
        counter[i+1] += counter[i]

for i in range(Q):
    print(counter[r[i]-1] - counter[l[i]-1])
### BUGGY CODE ###

def main():
    N = int(input())
    ans = 0
    for c in range(1, N):
        ans += solve(N-c)
    print(ans)

def solve(n):
    res = 0
    for i in range(1,n+1):
        if n % i == 0:
            res += 1
    return res

main()

### FIXED CODE ###


def main():
    N = int(input())
    ans = sum((N-1)//i for i in range(1, N))
    print(ans)

main()
### BUGGY CODE ###


import sys

N, M = map(int, input().split())
uvs = [list(map(lambda x:int(x)-1, input().split())) for _ in range(M)]
S, T = map(lambda x:int(x)-1, input().split())

roots = [[] for _ in range(N)]

for uv in uvs:
    roots[uv[0]].append(uv[1])

costs = [-10000 for _ in range(N)]

from collections import deque

todo = deque([S])
costs[S] = 0

while len(todo)>0:
    checking = todo.popleft()
    next_targets = deque([checking])
    for i in range(3):
        purposes = set()
        while len(next_targets) > 0:
            now = next_targets.pop()
            for root in roots[now]:
                purposes.add(root)
        next_targets = deque(purposes)
    for next_target in next_targets:
        if costs[next_target] < 0:
            costs[next_target] = costs[checking]+1
            todo.append(next_target)
        if next_target == T:
            print(costs[next_target])
            sys.exit()
print(-1)

### FIXED CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Tue Jul  7 18:47:41 2020

@author: naoki
"""
import sys
import copy
def func():
    N, M = map(int, input().split())
    uvs = [list(map(lambda x:int(x)-1, input().split())) for _ in range(M)]
    S, T = map(lambda x:int(x)-1, input().split())
    
    roots = [[] for _ in range(N)]
    
    for uv in uvs:
        roots[uv[0]].append(uv[1])
    
    costs = [-10000]*(N)
    
    from collections import deque
    
    todo = deque([S])
    costs[S] = 0
    todo_set = set([S])
    
    layers = [set() for _ in range(3)]
    
    while len(todo)>0:
        checking = todo.popleft()
        next_targets = deque([checking])
        for i in range(3):
            purposes = set()
            while len(next_targets) > 0:
                now = next_targets.pop()
                for root in roots[now]:
                    if root not in layers[i]:
                        layers[i].add(root)
                        purposes.add(root)
            next_targets = purposes.copy()
        for next_target in next_targets:
            if costs[next_target] < 0 and next_target not in todo_set:
                costs[next_target] = costs[checking]+1
                todo.append(next_target)
                todo_set.add(next_target)
                if next_target == T:
                    print(costs[next_target])
                    sys.exit()
    print(-1)
if __name__ == "__main__":
    func()
### BUGGY CODE ###

import math
mod=10**9 + 7
N=10**6+1
inv_t=[0]+[1]
for i in range(2,N):
    inv_t+=[inv_t[mod%i]*(mod-int(mod/i))%mod]
n=int(input())
A=list(map(int,input().split()))
l=[0]*10**6
for a in A:
    for i in range(2,int(math.sqrt(a))+1):
        c=0
        while a%i==0:
            c+=1
            a//=i
        l[i]=max(l[i],c)
    if a!=1:
        l[a]=max(l[a],1)
lcm=1
for i in range(10**6):
    if l[i]!=0:
        lcm=(lcm*(i**l[i]))%mod
ans=0
for a in A:
    ans=(ans+lcm*inv_t[a])%mod
print(ans)

### FIXED CODE ###

N=10**6+1
mod=10**9+7

inv_l=[0,1]
for i in range(2,N):
    inv_l+=[inv_l[mod%i]*(mod-int(mod/i))%mod]

prime_list=[]
min_prime=[1]*(N+1)
is_prime=[0,0]+[1]*(N-1)
for i in range(2,N+1):
    if is_prime[i]==1:
        prime_list.append(i)
        j=i
        while j<=N:
            is_prime[j]=0
            if min_prime[j]==1:
                min_prime[j]=i
            j+=i

def lcm(l,mod):
    max_count=[0]*(N+1)
    for a in l:
        a_min_prime=min_prime[a]
        a_count=0
        while a>1:
            if min_prime[a]==a_min_prime:
                a_count+=1
                a//=a_min_prime
            else:
                max_count[a_min_prime]=max(max_count[a_min_prime],a_count)
                a_min_prime=min_prime[a]
                a//=a_min_prime
                a_count=1
            if a==1:
                max_count[a_min_prime]=max(max_count[a_min_prime],a_count)
    ret=1
    for i in range(1,N+1):
        if max_count[i]!=0:
            ret=(ret*i**max_count[i])%mod
    return ret

n=int(input())
A=list(map(int,input().split()))
L=lcm(A,mod)
ans=0
for i in range(n):
    ans=(ans+L*inv_l[A[i]])%mod
print(ans)
### BUGGY CODE ###

n,m,k = map(int,input().split())
ans = 0
MOD = 10**9+7
for i in range(1,n):
    ans += (i*(n-i)*(m**2))%MOD
    ans %= MOD
for i in range(1,m):
    ans += (i*(m-i)*(n**2))%MOD
    ans %= MOD
from scipy.misc import comb
print((ans*comb(m*n-2,k-2,exact=True))%MOD)

### FIXED CODE ###

n,m,k = map(int,input().split())
ans = 0
mod = 10**9+7
max = 2*10**5
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル
for i in range( 2, max + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod
C = cmb(m*n-2,k-2,mod)
for i in range(1,n):
    ans += (i*(n-i)*(m**2))*C
for i in range(1,m):
    ans += (i*(m-i)*(n**2))*C
print(ans%mod)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

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

def prime_factor(n):
    factors = []
    while n%2==0:
        factors.append(2)
        n//=2
    f=3
    while f*f<=n:
        if n%f==0:
            factors.append(f)
            n//=f
        else:
            f+=2
    if n!=1:
        factors.append(n)
    return set(factors)

"""
def gcd(a,b):
    while b:
        a,b=b,a%b
    return a
"""
import math
val = L[0]
for i in range(1,n):
    val=math.gcd(L[i],val)
if val!=1:
    print('not coprime')
    sys.exit()

d={}
for i in range(n):
    factors = prime_factor(L[i])
    for j in factors:
        if j not in d.keys():
            d[j]=1
        else:
            print('setwise coprime')
            sys.exit()
print('pairwise coprime')



### FIXED CODE ###

import sys
import math
input = sys.stdin.readline
def prime_factor(n):
    factors = []
    while n%2==0:
        factors.append(2)
        n//=2
    f=3
    while f*f<=n:
        if n%f==0:
            factors.append(f)
            n//=f
        else:
            f+=2
    if n!=1:
        factors.append(n)
    return set(factors)


n=int(input())
L=list(map(int,input().split()))
val = L[0]
for i in range(1,n):
    val=math.gcd(val,L[i])
if val!=1:
    print('not coprime')
    sys.exit()
d={}
for i in range(n):
    factors = prime_factor(L[i])
    for j in factors:
        if j not in d.keys():
            d[j]=1
        else:
            print('setwise coprime')
            sys.exit()
print('pairwise coprime')
### BUGGY CODE ###

N = int(input())
P = list(map(float, input().split()))

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

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

print (sum(dp[N][(N + 1) // 2:]))

### FIXED CODE ###

N = int(input())
P = list(map(float, input().split()))

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

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

print (sum(dp[N][(N + 1) // 2:]))
### BUGGY CODE ###

n = int(input())
mod = 10**9+7
ans = 1
for i in range(1,n+1):
  ans *= i
print(ans%mod)

### FIXED CODE ###

n = int(input())
mod = 10**9+7
ans = 1
for i in range(1,n+1):
  ans = i * ans%mod
print(ans)
### BUGGY CODE ###

n,k = map(int, input().split())
l = [n]
if k==1:
    print(0)
    exit
else:
    while abs(l[-1]-k) not in l:
        l.append(abs(l[-1]-k))
    print(min(l))

### FIXED CODE ###

n,k = map(int, input().split())
print(min(n%k,k-(n%k)))
### BUGGY CODE ###

MOD = 10 ** 9 + 7
N = int(input())
x = list(map(int, input().split()))
x.sort()
 
kaijo = [1]
for i in range(1, N):
    kaijo.append(kaijo[-1] * i)
 
ans = 0
for i in range(N - 1):
    ans = (ans * (i + 1) + (x[-1] - x[i]) * kaijo[i]) % MOD
 
print(ans)

### FIXED CODE ###

MOD = 10 ** 9 + 7
N = int(input())
x = list(map(int, input().split()))
x.sort()
 
kaijo = [1]
for i in range(1, N):
    kaijo.append(kaijo[-1] * i % MOD)
 
ans = 0
for i in range(N - 1):
    ans = (ans * (i + 1) + (x[-1] - x[i]) * kaijo[i]) % MOD
 
print(ans)
### BUGGY CODE ###

import sys
def h(i):
 l=2*i;r=l+1
 if r<=H:
  if A[i]<A[l]:
   if A[l]<A[r]:A[i],A[r]=A[r],A[i];h(r)
   else:A[i],A[l]=A[l],A[i];h(l)
  elif A[i]<A[r]:A[i],A[r]=A[r],A[i];h(r)
 elif l<=H and A[i]<A[l]:A[i],A[l]=A[l],A[i];h(l)
H=0
A=[0]*2000001
for e in sys.stdin:
 if'i'==e[0]:
  H+=1;A[H]=int(e[7:]);k=H
  while k>1 and A[k//2]<A[k]:A[k],A[k//2]=A[k//2],A[k];k//=2
 elif'x'==e[1]:
  print(A[1]);H-=1
  if H:A[1]=A[H+1];h(1)


### FIXED CODE ###

import sys
from heapq import*
H=[]
O=[]
for e in sys.stdin:
 if'i'==e[0]:heappush(H,-int(e[7:]))
 elif't'==e[2]:O+=[-heappop(H)]
 else:print('\n'.join(map(str,O)))