Harryxun/sft_time huggingface dataset:
### 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(0, n):
    for j in range(0, i+1):
        dp[i+1][j+1] = dp[i][j]*p[i]
        dp[i+1][j] = dp[i][j]*(1-p[i]) + dp[i][j-1]*p[i]
        
ans = sum([dp[n][i] for i in range(n//2+1,n+1)])
print(ans)

### 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(0, n):
    for j in range(0, i+1):
        dp[i+1][j+1] = dp[i][j]*p[i]
        dp[i+1][j] = dp[i][j]*(1-p[i]) + dp[i][j-1]*p[i]
        
ans = sum([dp[n][i] for i in range(n//2+1,n+1)])
print(ans)
### BUGGY CODE ###

from collections import Counter
n = int(input())
a = list(map(int, input().split()))
cola = Counter(a)
mult = [True] * (10**6+1)
seta = list(set(a))

for s in seta:
    tmp = s * 2
    while tmp <= 10 ** 6:
        mult[tmp] = False
        tmp += s

ans = 0
for s in seta:
    if cola[s] == 1 and mult[s] == True:
        ans += 1

print(ans)


### FIXED CODE ###

from collections import Counter
n = int(input())
a = list(map(int, input().split()))
c = Counter(a)
m = [True] * (10**6+1)
s = list(set(a))
for u in s:
    t = u * 2
    while t <= 10 ** 6:
        m[t] = False
        t += u
r = 0
for u in s:
    if c[u] == 1 and m[u] == True:
        r += 1
print(r)
### BUGGY CODE ###

import numpy as np
#import math
#from decimal import *
#from numba import njit

#@njit
def main():
    N = int(input())
    A = np.array(list(map(int, input().split())))
    B = np.zeros(N, dtype='int32')
    count = 0
    i = 0
    for j in range(i+1, N):
        B[j] = A[i] + A[j] - j
    count += np.count_nonzero(B[i+1:] == 0)
    for i in range(1, N-1):
        count += np.count_nonzero(B[i+1:] == -(-A[0] + A[i] + i))
    print(count)
main()


### FIXED CODE ###

#import numpy as np
#import math
#from decimal import *
#from numba import njit
from collections import Counter

#@njit
def main():
    N = int(input())
    A = list(map(int, input().split()))
    count = 0
    r = []
    l = []
    for i in range(N):
        r += i - A[i],
        l += i + A[i],

    c = Counter(l)
    for i in r:
        count += c[i]

    print(count)
main()
### BUGGY CODE ###

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

pro=1
for i in range(n):
    pro *=List[i]

if pro > 10**18 :
    print("-1")
else:
    print(pro)

### FIXED CODE ###

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

pro=1
List.sort()
for i in range(n):
    pro *=List[i]
    if pro > 10**18 :
        print("-1")
        exit()

print(pro)
### BUGGY CODE ###

import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def pf(s): return print(s, flush=True)

N, Q = LI()
S = input()
"""
ACのインデックスをすべて記録しておき、始点、終点で区切って出す
少ない方を取ったほうがいいかな
"""
ACs = []
for sidx in range(0, len(S)-1):
    if S[sidx] == 'A':
        if S[sidx+1] == 'C':
            ACs.append(sidx)

#  print(ACs)

LR = []
for i in range(Q):
    LR.append(LI())

#  N, Q = 10**5, 10**5
#  S = 'ACTCTTCGTG'*10**4
#  LR = []
#  for i in range(Q):
#      LR.append([3,9000])

#  for l, r in LR:
#      tmp = S[l-1:r]
#      print(tmp.count('AC'))

result = []
#  print(ACs)
for l, r in LR:
    start = bisect.bisect_left(ACs, l-1)
    end = bisect.bisect_left(ACs, r-1)
    #  print('s,e', start, end)
    print(len(ACs[start:end]))


### FIXED CODE ###

import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def pf(s): return print(s, flush=True)

N, Q = LI()
S = input()
"""
ACのインデックスをすべて記録しておき、始点、終点で区切って出す
少ない方を取ったほうがいいかな
"""
ACs = []
for sidx in range(0, len(S)-1):
    if S[sidx] == 'A':
        if S[sidx+1] == 'C':
            ACs.append(sidx)

#  print(ACs)

LR = []
for i in range(Q):
    LR.append(LI())

#  N, Q = 10**5, 10**5
#  S = 'ACTCTTCGTG'*10**4
#  LR = []
#  for i in range(Q):
#      LR.append([3,9000])

#  for l, r in LR:
#      tmp = S[l-1:r]
#      print(tmp.count('AC'))

result = []
#  print(ACs)
for l, r in LR:
    start = bisect.bisect_left(ACs, l-1)
    end = bisect.bisect_left(ACs, r-1)
    #  print('s,e', start, end)
    print(end-start)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

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

#output
from collections import Counter
import bisect
import numpy as np

l = Counter(A).most_common()
l = [b for a, b in l]
M = len(l)
l.sort()
m = np.cumsum(l)
p = m[-1]

maximum_operation = [0] * N

ll = []
for x in range(1, N+1):
    a = bisect.bisect_left(l, x)
    if a == 0:
        b = M*x
        c = 0
    elif a >= M:
        b = 0
        c = p
    else:
        b = (M-a)*x
        c = m[a-1] 
    ll.append((b + c)/x)
ll.sort()

for K in range(M):
    maximum_operation[K] = N - bisect.bisect_left(ll, K+1)

for m in maximum_operation:
    print(m)


### FIXED CODE ###

import sys
input = sys.stdin.readline

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

#output
from collections import Counter
import bisect

l = Counter(A).most_common()
l = [b for a, b in l]
M = len(l)
l.sort()
p = sum(l)

maximum_operation = [0] * N

ll = []
for x in reversed(range(1, N+1)):
    a = bisect.bisect_left(l, x)
    if a == 0:
        b = M*x
        c = 0
    elif a >= M:
        b = 0
        c = p
    else:
        b = (M-a)*x
        c = sum(l[0:a]) 
    ll.append((b + c)/x)

for K in range(M):
    maximum_operation[K] = N - bisect.bisect_left(ll, K+1)

for m in maximum_operation:
    print(m)
### BUGGY CODE ###

n, k = map(int, input().split())
A = list(map(int, input().split()))
m=0
for i in range(0,n-k+1):
    s=0
    for j in range(i,i+k):
        s=s+(A[j]+1)/2
    if s>m:
        m=s
print(m)

### FIXED CODE ###

n,k = map(int, input().split())
A = list(map(int, input().split()))
s=[0]*(n+1)
for i in range(1,n+1):
    s[i]=s[i-1]+A[i-1]
s1=[0]*(n-k+1)
for i in range(0,n-k+1):
    s1[i]=s[k+i]-s[i]
print((max(s1)+k)/2)
### BUGGY CODE ###

n = int(input())
d = list(map(int,input().split()))
k_max = max(d)
k_min = min(d)
result = 0
for k in range(k_min,k_max+1):
    count = 0
    for i in range(n):
        if d[i] >= k:
            count += 1
        if count > n//2:
            break
    if count == n//2:
        result += 1
print(result)

### FIXED CODE ###

n = int(input())
d = list(map(int,input().split()))
d.sort()
l = d[n//2 -1]
r = d[n//2]
print(r - l)
### BUGGY CODE ###

MOD = 10**9+7

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

def power(base, exp, op=lambda x, y: x * y, ie=1):
    res = ie
    while exp:
        if exp & 1:
            res = op(res, base)
        base = op(base, base)
        exp >>= 1
    return res

matrix_id = [[i == j for j in range(N)] for i in range(N)]

def matrix_mul(A, B):
    res = [[0 for j in range(N)] for i in range(N)]
    for i in range(N):
        for j in range(N):
            for k in range(N):
                res[i][j] += A[i][k] * B[k][j]
                res[i][j] %= MOD
    return res

P = power(A, K, matrix_mul, matrix_id)

res = 0

for i in range(N):
    for j in range(N):
        res += P[i][j]
        res %= MOD

print(res)

### FIXED CODE ###

MOD = 10**9+7

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

def power(base, exp, op=lambda x, y: x * y, ie=1):
    res = ie
    while exp:
        if exp & 1:
            res = op(res, base)
        base = op(base, base)
        exp >>= 1
    return res

matrix_id = [[i == j for j in range(N)] for i in range(N)]

def matrix_mul(A, B):
    res = [[0 for j in range(N)] for i in range(N)]
    for i in range(N):
        for j in range(N):
            for k in range(N):
                res[i][j] += A[i][k] * B[k][j]
                res[i][j] %= MOD
    return res

P = power(A, K, matrix_mul, matrix_id)

res = 0

for i in range(N):
    for j in range(N):
        res += P[i][j]
        res %= MOD

print(res)
### BUGGY CODE ###

input = raw_input

n, m = map(int, input().split(" "))

graph = {}
for node in range(1, n+1):
    graph[node] = []

for i in range(m):
    a, b = map(int, input().split(" "))
    graph[a].append(b)
    graph[b].append(a)

#print("graph", graph)

michi = [None] * (n+1)
uses = [False] * (n+1)

def set(x):
    return x
def f(pnode, cur_node):
    michi[cur_node] = pnode
    ret = set([(cur_node, child_node) for child_node in graph[cur_node] if child_node != pnode])
    return ret

uses[1] = True
pnode = -1
cur_node = 1
cur_nodes= set([(cur_node, child_node) for child_node in graph[cur_node] if child_node != pnode])
depth = 1
while True:
    next_nodes = set([])
    done = False
    for pnode, cur_node in cur_nodes:
        if not uses[cur_node]:
            ret = f(pnode, cur_node)
            next_nodes = next_nodes + ret
            #next_nodes = next_nodes | ret
            uses[cur_node] = True
            done = True

    #print(done, depth, next_nodes)
    #print("uses", uses)
    if not done:
        break
    depth += 1
    cur_nodes = next_nodes

michi = michi[2:]
if None in michi:
    print("No")
else:
    print("Yes")
    for node in michi:
        print(node)

### FIXED CODE ###

#input = raw_input

n, m = map(int, input().split(" "))

graph = {}
for node in range(1, n+1):
    graph[node] = []

for i in range(m):
    a, b = map(int, input().split(" "))
    graph[a].append(b)
    graph[b].append(a)

#print("graph", graph)

michi = [None] * (n+1)
uses = [False] * (n+1)

def set(x):
    return x

uses[1] = True

cur_node = 1
cur_nodes = {}
child_nodes = graph[cur_node]
for child_node in child_nodes:
    cur_nodes[child_node] = cur_node
depth = 1
while True:
    next_nodes = {}
    done = False
    for cur_node, pnode in cur_nodes.items():
        if not uses[cur_node]:
            michi[cur_node] = pnode
            uses[cur_node] = True
            for child_node in graph[cur_node]:
                if child_node == pnode or uses[child_node]:
                    continue
                next_nodes[child_node] = cur_node
            done = True

    if not done:
        break
    depth += 1
    cur_nodes = next_nodes
    #print("michi", michi[1:])

michi = michi[2:]
if None in michi:
    print("No")
else:
    print("Yes")
    for node in michi:
        print(node)
### BUGGY CODE ###

# 解説を見ながら
N = int(input())
A = list(map(int,input().split()))

# リストを作って，Amaxまでの数字について，aiの約数ならば足す，最終的には，要素が１のやつが求めるもの
# 一回検討した要素はsetに入れて次出たときは使わないようにする
import numpy as np
#L = np.zeros((10**6+10,))
MAX=10**6+1
L = [0]*(10**6+1)
used = set()
first = True
for a in A:
    if a in used and first:
        first = False
        for i in range(0,MAX,a):
            L[i] += 1
        # L[::a] += 1　要素アクセスだから遅くなった?
        continue
    used.add(a)
    # L[1:][::a] += 1こういう書き方はリストではできないので注意
    for i in range(0,MAX,a):
        L[i] += 1
    #L[::a] += 1
count = 0
for a in A:
    if L[a] == 1:
        count += 1
print(count)







### FIXED CODE ###

# 解説を見ながら
N = int(input())
A = list(map(int,input().split()))

# リストを作って，Amaxまでの数字について，aiの約数ならば足す，最終的には，要素が１のやつが求めるもの
# 一回検討した要素はsetに入れて次出たときは使わないようにする
import numpy as np
#L = np.zeros((10**6+10,))
A.sort()
MAX=10**6+1
L = [0]*MAX
used = set()
#first = True  # firstのフラッグの使い回しをしていた．複数に分かれる条件分岐はしっかりとどのような分岐をするか書く癖をつけたほうがよい
for a in A:
    if L[a] == 2:
        continue
    if a in used:
        for i in range(0,MAX,a):
            L[i] = 2
        # L[::a] += 1　要素アクセスだから遅くなった?
        continue
    used.add(a)
    # L[1:][::a] += 1こういう書き方はリストではできないので注意
    L[a] = 1
    for i in range(2*a,MAX,a):
        L[i] = 2
    #L[::a] += 1
count = 0
for a in A:
    if L[a] == 1:
        count += 1
print(count)
### BUGGY CODE ###

#dt = {} for i in x: dt[i] = dt.get(i,0)+1
import sys;input = sys.stdin.readline
inp,ip = lambda :int(input()),lambda :[int(w) for w in input().split()]

#from fractions import gcd

def gcd(a, b): 
    if a == 0: return b 
    if b == 0: return a 
    k = 0
    while ((a | b) & 1) == 0: 
        a >>= 1
        b >>= 1
        k += 1
    while (a & 1) == 0: 
        a >>= 1
    while b:  
        while (b & 1) == 0: 
            b >>= 1
        if a > b : 
            a,b = b,a
        b = b - a 
    return a << k 

from math import sqrt
def pfact(num):
    d = set()
    while num%2==0:
        d.add(2)
        num //= 2
    for i in range(3,int(sqrt(num))+1,2):
        while num%i==0:
            d.add(i)
            num //= i
    if num>2:
        d.add(num)
    return list(d)

n = inp()
x = ip()
t = x[0]
for i in range(1,n):
    t = gcd(t,x[i])
    if t == 1:
        break
if t != 1:
    ans = 'not coprime'
else:
    ans = 'pairwise coprime'
    dt = {i+1:1 for i in range(10**6)}
    for i in x:
        for j in pfact(i):
            if dt[j]:
                dt[j] = 0
            else:
                ans = 'setwise coprime'
                break
print(ans)


### FIXED CODE ###

#dt = {} for i in x: dt[i] = dt.get(i,0)+1
import sys;input = sys.stdin.readline
inp,ip = lambda :int(input()),lambda :[int(w) for w in input().split()]

#from fractions import gcd

def gcd(a, b): 
    if a == 0: return b 
    if b == 0: return a 
    k = 0
    while ((a | b) & 1) == 0: 
        a >>= 1
        b >>= 1
        k += 1
    while (a & 1) == 0: 
        a >>= 1
    while b:  
        while (b & 1) == 0: 
            b >>= 1
        if a > b : 
            a,b = b,a
        b = b - a 
    return a << k 

from math import sqrt
def pfact(num):
    global dt
    if num&1 == 0:
        num >>= 1
        if dt[2]:
            dt[2] = 0
        else:
            return 'setwise coprime'
    while num&1 == 0:
        num >>= 1
    for i in range(3,int(sqrt(num))+1,2):
        if num%i == 0:
            num //= i
            if dt[i]:
                dt[i] = 0
            else:
                return 'setwise coprime'
        while num%i == 0:
            num //= i
    if num>2:
        if dt[num]:
            dt[num] = 0
        else:
            return 'setwise coprime'
    return 'pairwise coprime'

n = inp()
x = ip()
x.sort(reverse=True)
t = x[0]
for i in range(1,n):
    t = gcd(t,x[i])
    if t == 1:
        break
if t != 1:
    ans = 'not coprime'
else:
    ans = 'pairwise coprime'
    dt = {i+1:1 for i in range(10**6)}
    for i in x:
        if pfact(i) == 'setwise coprime':
            ans = 'setwise coprime'
            break
print(ans)
### BUGGY CODE ###

#!python3

LI = lambda: list(map(int, input().split()))

# input
S = input()

MOD = 10 ** 9 + 7


def main():
    n = len(S)
    m = 5
    w = []
    p = 1
    for i in range(n):
        s = S[-1 - i]
        if s == "?":
            w.append(p)
        else:
            m = (m - int(s) * p) % 13
        p = p * 10 % 13

    n = len(w)
    l1 = [0] * 13
    l1[0] = 1
    for i in range(1, n + 1):
        l2 = [0] * 13
        for j in range(10):
            x = w[i - 1] * j % 13
            for k in range(13):
                t = (x + k) % 13
                l2[t] += l1[k]
        l1 = [y % MOD for y in l2]
    
    ans = l1[m]
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

#!python3

LI = lambda: list(map(int, input().split()))

# input
S = input()

MOD = 10 ** 9 + 7


def main():
    n = len(S)
    m = 5
    w = []
    p = 1
    for i in range(n):
        s = S[-1 - i]
        if s == "?":
            w.append(p)
        else:
            m = (m - int(s) * p) % 13
        p = p * 10 % 13

    n = len(w)
    l1 = [0] * 13
    l1[0] = 1
    for i in range(1, n + 1):
        l2 = [0] * 13
        for j in range(10):
            x = w[i - 1] * j % 13
            for k in range(13):
                t = (x + k) % 13
                l2[t] += l1[k]
        l1 = [y % MOD for y in l2]
    
    ans = l1[m]
    print(ans)


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

import sys
readline = sys.stdin.readline

N,X,Y = map(int,readline().split())
G = [[] for i in range(N)]

for i in range(N - 1):
  G[i].append(i + 1)
  G[i + 1].append(i)
  
G[X - 1].append(Y - 1)
G[Y - 1].append(X - 1)

ans = [0] * N

from collections import deque
for i in range(N):
  q = deque([])
  q.append([i, -1, 0])
  seen = set()
  while q:
    v, parent,cost = q.popleft()
    if v in seen:
      continue
    seen.add(v)
    ans[cost] += 1
    for child in G[v]:
      if child == parent:
        continue
      q.append([child, i, cost + 1])
      
for i in range(1, N):
  print(ans[i] // 2)


### FIXED CODE ###

N,X,Y=map(int,input().split())

E=[[] for i in range(N)]

for i in range(N-1):
  E[i].append(i+1)
  E[i+1].append(i)
  
E[X-1].append(Y-1)
E[Y-1].append(X-1)

INF=10**4

ans=[0 for i in range(N)]
from collections import deque
for i in range(N):
  score=[INF for i in range(N)]
  q=deque([[i,0]])
  while q:
    v,dist=q.pop()
    if score[v]>dist:
      score[v]=dist
    else:
      continue
    for child in E[v]:
      q.append([child,dist+1])
  for s in score:
    ans[s]+=1
    
for i in range(1,N):
  print(ans[i]//2)
### BUGGY CODE ###

import sys
inputs = sys.stdin.readline
N, M = map(int,inputs().split())
K = [None]*M
for t in range(M):
	x, y, z = map(int,inputs().split())
	K[t] = {x, y}
for p in range(M):
	for q in range(M - p -1):
		if K[q].isdisjoint(K[M - p - 1]) == False:
			K[q] = K[q] | K[M - p -1]
			K[M - p -1] = {0}
			continue
c = 0
for p in range(M):
	c += len(K[p]) - 1
print(N - c)

### FIXED CODE ###

import sys
inputs = sys.stdin.readline
N, M = map(int,inputs().split())
K = [None]*M
for t in range(M):
	x, y, z = map(int,inputs().split())
	K[t] = (x, y)
c = 0

U = [0]*(N+1)

for k in K:
	if U[k[0]] and U[k[1]]:
		a = U[k[0]]
		b = U[k[1]]
		while(U[a] != a ):
			a = U[a]
		while(U[b] != b ):
			c = b
			b = U[b]
			U[c] = a
		U[b] = a
	elif U[k[1]]:
		U[k[0]] = U[k[1]]
	elif U[k[0]]:
		U[k[1]] = U[k[0]]
	else:
		U[k[0]] = k[0]
		U[k[1]] = k[0]

ans = 0
c = 0
group = set()
for n in range(1,N+1):
	if U[n] == 0:
		ans += 1
		continue
	elif n == U[n]:
		ans += 1
		group.add(U[n])
	elif U[n] in group:
		continue
	else:
		while(n != U[n] and U[n] not in group):
			group.add(U[n])
			n = U[n]
		group.add(U[n])
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

class UnionFind():
    def __init__(self, n=0):
        self.d = [-1]*n
        self.g = set()
    
    def find(self, x):
        if self.d[x] < 0: return x
        self.d[x] = self.find(self.d[x])
        return self.d[x]

    def unite(self, x, y):
        x,y=self.find(x),self.find(y)
        if x==y:return False
        if self.d[x] > self.d[y]: x,y=y,x
        self.d[x] += self.d[y]
        self.g.add(x)
        if y in self.g:self.g.remove(y)
        self.d[y] = x
        return True

    def same(self,x,y): return self.find(x)==self.find(y)
    def size(self,x): return -self.d[self.find(x)]
    
def comb2(n):
  return n*(n-1)//2
    
N,M=map(int,input().split())
edges=[list(map(int,input().split())) for _ in range(M)]

total=comb2(N)
ans = [total]
uf = UnionFind(N+1)
for i in range(M-1):
  if uf.unite(edges[-1-i][0],edges[-1-i][1]):
  	ans.append(total-sum(map(lambda x: comb2(uf.size(x)),uf.g)))
  else:
    ans.append(ans[-1])

for i in range(M):
  print(ans[-1-i])

### FIXED CODE ###

from collections import defaultdict

class UnionFind():
    def __init__(self, n=0):
        self.d = [-1]*n
        self.g = set()
    
    def find(self, x):
        if self.d[x] < 0: return x
        self.d[x] = self.find(self.d[x])
        return self.d[x]

    def unite(self, x, y):
        x,y=self.find(x),self.find(y)
        if x==y:return False
        if self.d[x] > self.d[y]: x,y=y,x
        self.d[x] += self.d[y]
        self.g.add(x)
        if y in self.g:self.g.remove(y)
        self.d[y] = x
        return True

    def same(self,x,y): return self.find(x)==self.find(y)
    def size(self,x): return -self.d[self.find(x)]
    
def comb2(n):
  return n*(n-1)//2
    
N,M=map(int,input().split())
E = [tuple(map(int,input().split())) for _ in range(M)]

total=comb2(N)
uf = UnionFind(N+1)
ans = [total]
for i in range(M-1):
  a,b = E[-i-1]
  if uf.same(a,b):
    ans.append(ans[-1])
    continue
  else:
    size1,size2 = uf.size(a),uf.size(b)
    uf.unite(a,b)
    size3 = uf.size(a)
    tmp = ans[-1]+comb2(size1)+comb2(size2)-comb2(size3)
    ans.append(tmp)
print(*ans[::-1])
### BUGGY CODE ###

from functools import lru_cache

def main(S):
    con = 10**9 + 7

    @lru_cache(maxsize=1024, typed=True)
    def get_c(iii):
        return [(j * iii) % 13 for j in l10]

    l10 = list(range(10))
    l13 = list(range(13))
    m13 = {i: {j: (i + j) % 13 for j in l13} for i in l13}
    c = []
    iii = 1
    for i in range(len(S)):
        s = S[len(S) - i - 1]
        if s != "?":
            c.append([(int(s) * iii) % 13])
        else:
            c.append(get_c(iii))
        iii = (iii * 10) % 13

    _tdp = {i: 0 for i in l13}
    it = iter(c)
    pdp = {i: 1 for i in next(it)}
    d = 1
    for v in it:
        tdp = _tdp.copy()
        for r in v:
            for _r, _v in pdp.items():
                tdp[m13[_r][r]] += _v
        if d == 0:
            for i in l13:
                tdp[i] = tdp[i] % con
        d = (d + 1) % 50
        pdp = tdp

    ans = pdp.get(5, 0)
    print(ans % con)

if __name__ == "__main__":
    S = input()
    main(S)


### FIXED CODE ###

S = input()
con = 10**9 + 7

T = [s if s != "?" else "0" for s in S]
T = int(''.join(T))
SS = T % 13

def get_mod(S):
    c = {}
    iii = 1
    for i in range(len(S)):
        if S[len(S) - i - 1] != "?":
            iii *= 10
            iii %= 13
            continue
        c[i] = {(j * iii) % 13: 1 for j in range(0, 10)}
        iii *= 10
        iii %= 13
    return c
c = get_mod(S)

def get_tdp(pdp):
    tdp = {i: 0 for i in range(13)}
    for r in v.keys():
        for _r, _v in pdp.items():
            tdp[(_r + r) % 13] += _v
    for i in range(13):
        tdp[i] %= con
    return tdp

pdp = {i: 0 for i in range(13)}
pdp[SS] += 1
for k, v in c.items():
    pdp = get_tdp(pdp)

ans = pdp[5]
print(ans)
### BUGGY CODE ###

N = int(input())
c = input()
ans = 0
for _ in range(N):
    fs = 0
    ls = len(c)
    for i, ci in enumerate(c):
        fs = i
        if ci == 'W':
            break
    for i , ci in enumerate(c[::-1]):
        if i + fs >= N:
            break
        ls -= 1
        if ci == 'R':
            break
    if fs == ls:
        break
    ans += 1
    c = c[fs + 1:ls]
    #print(c)
    if len(c) <= 1:
        break
print(ans)

### FIXED CODE ###

N = int(input())
C = input()
a = b = ans = 0
for c in C:
    if c == 'R':
        a += 1
ans = max(a, b)
for c in C:
    if c == 'R':
        a -= 1
    else:
        b += 1
    ans = min(ans, max(a, b))
print(ans)
### BUGGY CODE ###

def product(list):
    i=1
    for j in list:
        if j!=0:
            i*=j
        else:
            return 0
    return i
 
N=int(input())
A=list(map(int,input().split()))

ans=product(A)
if ans>10**18:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
ans=1
flag=True
if 0 in A:
    print(0)
else:
    for j in A:
        ans*=j
        if ans>10**18:
            print(-1)
            flag=False
            break
    if flag:
        print(ans)