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

def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d


n, m, l = map(int, input().split())
d = [[float("inf") for i in range(n)] for i in range(n)]
for i in range(m):
    ai, bi, ci = map(int, input().split())
    d[ai-1][bi-1] = ci
    d[bi-1][ai-1] = ci
for i in range(n):
    d[i][i] = 0 #自身のところに行くコストは０

d = warshall_floyd(d)
for i in range(n):
    for j in range(n):
        if d[i][j] <= l:
            d[i][j] = 1
        else:
            d[i][j] = float("inf")

d = warshall_floyd(d)

q = int(input())
for i in range(q):
    si, ti = map(int, input().split())
    if d[si-1][ti-1] == float('inf'):
        print(-1)
    else:
        print(d[si-1][ti-1]-1)

### FIXED CODE ###

def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d


n, m, l = map(int, input().split())
d = [[10**12 for i in range(n)] for i in range(n)]
for i in range(m):
    ai, bi, ci = map(int, input().split())
    d[ai-1][bi-1] = ci
    d[bi-1][ai-1] = ci
for i in range(n):
    d[i][i] = 0 #自身のところに行くコストは０

d = warshall_floyd(d)
for i in range(n):
    for j in range(n):
        if d[i][j] <= l:
            d[i][j] = 1
        else:
            d[i][j] = 10**12

d = warshall_floyd(d)

q = int(input())
for i in range(q):
    si, ti = map(int, input().split())
    if d[si-1][ti-1] >= 10**12:
        print(-1)
    else:
        print(d[si-1][ti-1]-1)
### BUGGY CODE ###

x, y = map(int, input().split())
if x == y:
  print(-1)
else:
  n = 0
  while n % x != 0 or n % y == 0:
    n += 1
  print(n)

### FIXED CODE ###

x, y = map(int, input().split())
if x % y == 0:
  print(-1)
else:
  i = 1
  n = x
  while n % y == 0:
    n = i * x
    i += 1
  print(n)
### BUGGY CODE ###

from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

def dijkstra(s,n,w,cost):
    #始点sから各頂点への最短距離
    #n:頂点数,　w:辺の数, cost[u][v] : 辺uvのコスト(存在しないときはinf)
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    
    while True:
        v = -1
        #まだ使われてない頂点の中から最小の距離のものを探す
        for i in range(n):
            if (not used[i]) and (v == -1):
               v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
               break
        used[v] = True
               
        for j in range(n):
               d[j] = min(d[j],d[v]+cost[v][j])
    return d
n,m = inpl()
a = [inpl() for i in range(m)]
cost = [[float('inf')] * n for i in range(n)]
for i in range(n-1):
    cost[i+1][i] = 0
for i in a:
    cost[i[0]-1][i[1]-1] = i[2]
res = dijkstra(0,n,m+n-1,cost)
if res[n-1] == float('inf'):
    print(-1)
else:
    print(res[n-1])

### FIXED CODE ###

from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

def dijkstra_heap(s):
    #始点sから各頂点への最短距離
    d = [float("inf")] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heappush(edgelist,e)
    while len(edgelist):
        minedge = heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heappush(edgelist,[e[0]+d[v],e[1]])
    return d

################################
n,w = map(int,input().split()) #n:頂点数　w:辺の数

edge = [[] for i in range(n)]
#edge[i] : iから出る道の[重み,行先]の配列
for i in range(w):
    x,y,z = map(int,input().split())
    edge[x-1].append([z,y-1])
for i in range(n-1):
    edge[i+1].append([0,i])
res = dijkstra_heap(0)
if res[-1] == float('inf'):
    print(-1)
else:
    print(res[-1])
### BUGGY CODE ###

from collections import deque
def bfs():
    move=[[1,0],[0,1],[-1,0],[0,-1]]
    
    queue=deque()

    queue.append((0,(sy,sx))) #queue=deque([[sy,sx]])でもよい
    visited[sy][sx]=0 #スタート地点の距離は0
    while queue:
        cnt,(y,x)=queue.popleft()
        
        
        for dy,dx in move:
            my,mx=y+dy,x+dx 
            if my<0 or my>=tate:
                continue
            if mx<0 or mx>=yoko:
                continue
            if maze[my][mx]=="#":
                continue
            if visited[my][mx]>cnt:
                queue.append((cnt,(my,mx)))
                visited[my][mx]=cnt # visitedは距離も兼ねてる
        for my in range(y-2,y+3):
            for mx in range(x-2,x+3):
                if my<0 or my>=tate:
                    continue
                if mx<0 or mx>=yoko:
                    continue
                if maze[my][mx]=="#":
                    continue
                if visited[my][mx]>cnt+1:
                    queue.append((cnt+1,(my,mx)))
                    visited[my][mx]=cnt+1
    if visited[gy][gx]==inf:
        print(-1)
    else:
        print(visited[gy][gx])


tate,yoko=map(int,input().split())
sy,sx=map(int,input().split())
gy,gx=map(int,input().split())
sy,sx,gy,gx=sy-1,sx-1,gy-1,gx-1
maze=[]
inf=float('inf')
visited=[[inf]*yoko for i in range(tate)]

for i in range(tate):
    line=list(input())
    maze.append(line)
bfs()




### FIXED CODE ###

from collections import deque
def bfs():
    move=[[1,0],[0,1],[-1,0],[0,-1]]
    
    queue=deque()
    queue.append([sy,sx]) #queue=deque([[sy,sx]])でもよい
    visited[sy][sx]=0 #スタート地点の距離は0
    while queue:
        y,x=queue.popleft()
        cnt=visited[y][x]
        
        for dy,dx in move:
            my,mx=y+dy,x+dx 
            if my<0 or my>=tate:
                continue
            if mx<0 or mx>=yoko:
                continue
            if maze[my][mx]=="#":
                continue
            if visited[my][mx]>cnt:
                queue.appendleft([my,mx])
                visited[my][mx]=cnt # visitedは距離も兼ねてる
        for my in range(y-2,y+3):
            for mx in range(x-2,x+3):
                if my<0 or my>=tate:
                    continue
                if mx<0 or mx>=yoko:
                    continue
                if maze[my][mx]=="#":
                    continue
                if visited[my][mx]>cnt+1:
                    queue.append([my,mx])
                    visited[my][mx]=cnt+1
    if visited[gy][gx]==inf:
        print(-1)
    else:
        print(visited[gy][gx])


tate,yoko=map(int,input().split())
sy,sx=map(int,input().split())
gy,gx=map(int,input().split())
sy,sx,gy,gx=sy-1,sx-1,gy-1,gx-1
maze=[]
inf=float('inf')
visited=[[inf]*yoko for i in range(tate)]

for i in range(tate):
    line=list(input())
    maze.append(line)
bfs()
### BUGGY CODE ###

K, S = map(int, input().split() )
cnt = 0
for x in range(K+1):
  for y in range(K+1):
    for z in range(K+1):
      if x+y+z == S:
        cnt+=1
print(cnt)

### FIXED CODE ###

K, S = map(int, input().split() )
cnt=0
for x in range(K+1):
  for y in range(K+1):
    if 0<=S-(x+y)<=K:
      cnt+=1
print(cnt)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
N = input()
input_line = input()
Ai = input_line.split(" ")
Comment = "YES"
for i in range(int(N)):
  for j in range(i+1,int(N)):
    if(Ai[i] == Ai[j]):
      Comment = "NO"
      break
      
print(Comment)

### FIXED CODE ###

# -*- coding: utf-8 -*-
import numpy as np

N = input()
input_line = input()
Ai = input_line.split(" ")
NumAi = np.array(Ai)
Comment = "NO"
N = int(N)
if(len(NumAi) == len(np.unique(NumAi))):
  Comment = "YES"

#if(NumAi != set)
      
print(Comment)
### BUGGY CODE ###

N = int(input())

s_list = []
cnt = 0
for i in range(N):
    candidate = input()
    for s in s_list:
        if candidate == s:
            break
    else:
       cnt += 1
       s_list.append(candidate)

print(cnt)

### FIXED CODE ###

s_list = []
N = int(input())
for _ in range(N):
    s_list.append(input())

print(len(set(s_list)))
### BUGGY CODE ###

n=int(input())

def fac(n):
    f = []
    c = 0
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            #f.append(i)
            c += 1
            if i != n // i:
                #f.append(n//i)
                c += 1
    return c*n

result = 0
for i in range(1,n+1):
  result += fac(i)
print(result)

### FIXED CODE ###

n=int(input())

a=[0]*(n+1)
for i in range(1,n+1):
  for j in range(i,n+1,i):
    a[j] += 1

result = 0
for i in range(n+1):
  result += i*a[i]
print(result)
### BUGGY CODE ###

s = input()
_q = int(input())
rev = 0
l, r = "", ""
for _ in range(_q):
    *q, = map(str, input().split())
    q.extend([" ", " "])
    t = q[0]
    f = q[1]
    c = q[2]

    if t == "1":
        rev += 1
    else:
        if rev%2 == 0:
            if f == "1":
#                s.insert(0, c)
                l = c+l
            else:
#                s.append(c)
                r += c
        else:
            if f == "1":
#                s.append(c)
                r += c
            else:
#                s.insert(0, c)
                l = c+l

s = l + s + r

if rev%2 == 1:
    *s, = reversed(s)

print("".join(s))


### FIXED CODE ###

*s, = input()
_q = int(input())
rev = 0
l, r = [], []
for _ in range(_q):
    *q, = map(str, input().split())

    if q[0] == "1":
        rev += 1
        continue

    t = q[0]
    f = q[1]
    c = q[2]

    if rev%2 == 0:
        if f == "1":
            l.append(c)
        else:
            r.append(c)
    else:
        if f == "1":
            r.append(c)
        else:
            l.append(c)

*l, = reversed(l)

s = l + s + r

if rev%2 == 1:
    *s, = reversed(s)

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

import sys
input = sys.stdin.readline

_a, _b = map(int, input().split())


def gcd(a, b):
    while b:
        a, b = b, a % b

    return a


def chker(a, b):
    if gcd(a, b) == 1:
        print(1)
        return

    klist = [item for item in range(1, min(a, b) + 1) if _a % item == 0 and _b % item == 0]
    slist, klist = [klist[1]], klist[1:]
    for item1 in klist:
        tag = 0
        for item2 in slist:
            if item1 % item2 == 0:
                tag = 1
                break

        if tag == 0:
            slist.append(item1)

    print(len(slist) + 1)


chker(_a, _b)


### FIXED CODE ###

import sys
input = sys.stdin.readline

_a, _b = map(int, input().split())


def gcd(a, b):
    while b:
        a, b = b, a % b

    return a


def get_divisor(a):
    dvlist = []
    for i in range(1, int(a ** 0.5) + 1):
        if a % i == 0:
            dvlist.append(i)
            if i != a // i:
                dvlist.append(a // i)

    return sorted(dvlist)


def chker(a, b):
    a, b = min(a, b), max(a, b)
    mindiv = get_divisor(a)
    shdvlist = [item for item in mindiv if b % item == 0]
    if len(shdvlist) < 3:
        print(len(shdvlist))
        return

    slist, shdvlist = [shdvlist[1]], shdvlist[1:]
    for item1 in shdvlist:
        flg = 0
        for item2 in slist:
            if item1 % item2 == 0:
                flg = 1
                break

        if flg == 0:
            slist.append(item1)

    print(len(slist) + 1)


chker(_a, _b)
### BUGGY CODE ###

from decimal import *
from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush,heappop
import math
from collections import *
from functools import reduce,cmp_to_key
import sys
input = sys.stdin.readline

M = mod = 998244353
def factors(n):return sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))
def inv_mod(n):return pow(n, mod - 2, mod)

def li():return [int(i) for i in input().rstrip('\n').split()]
def st():return input().rstrip('\n')
def val():return int(input().rstrip('\n'))
def li2():return [i for i in input().rstrip('\n')]
def li3():return [int(i) for i in input().rstrip('\n')]
def li4():return [float(i) for i in input().rstrip('\n').split(' ')]

n = val()
l = li4()
mihe = n//2 + 1


sumarray = [0 for i in range(n)] + [1]

dp = [0]*(n + 1)

for i in range(n-1,-1,-1):
    dp = [0] *(n + 1)
    for j in range(n-1,i - 1,-1):
        dp[j] += ( l[i] / (1 - l[i]) ) * sumarray[j + 1]

    
    for j in range(n):sumarray[j] += dp[j]
    # print(dp)


# for i in dp:print(*i)
# print(*sumarray)

curr = 1
for i in l:curr *= (1 - i)
ans = 0
for i in sumarray[:-mihe]:
    ans += i * curr
print(ans)


### FIXED CODE ###

from decimal import *
from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush,heappop
import math
from collections import *
from functools import reduce,cmp_to_key
import sys
input = sys.stdin.readline

M = mod = 998244353
def factors(n):return sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))
def inv_mod(n):return pow(n, mod - 2, mod)

def li():return [int(i) for i in input().rstrip('\n').split()]
def st():return input().rstrip('\n')
def val():return int(input().rstrip('\n'))
def li2():return [i for i in input().rstrip('\n')]
def li3():return [int(i) for i in input().rstrip('\n')]
def li4():return [float(i) for i in input().rstrip('\n').split(' ')]

n = val()
l = li4()
mihe = n//2 + 1


curr = 1
for i in l:curr *= (1 - i)
dp = [0 for i in range(n + 1)]
dp[0] = 1

for i in range(n):

    for j in range(i + 1,-1,-1):
        if not j:dp[j] *= 1 - l[i]
        else:dp[j] = dp[j-1] * l[i] + dp[j] *(1 - l[i])

ans = 0
for i in dp[-mihe:]:
    ans += i

print(round(ans,10))
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
while len(a)>1:
    m=min(a)
    def f(n):
        return n-m
    a=map(f,a)
    a=set(a)
    a.add(m)
    a.remove(0)
    a=list(a)
print(a[0])


### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
while len(a)>1:
    m=min(a)
    def f(n):
        return n%m
    a=map(f,a)
    a=set(a)
    a.add(m)
    a.remove(0)
    a=list(a)
print(a[0])
### BUGGY CODE ###

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

dp = [0] * N
for i in range(1, N):
    # 現在の足場を1~K前の足場から求める
    dp[i] = min([dp[j] + abs(h[j]-h[i]) for j in range(max(0,i-K),i)])

print(dp[-1])

### FIXED CODE ###

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

dp = [0] * N
for i in range(1, N):
    dp[i] = min([dp[j] + abs(h[j]-h[i]) for j in range(max(0,i-K),i)])

print(dp[-1])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10000000)
# input = sys.stdin.readline
from bisect import *
from collections import *
from heapq import *
import functools
import itertools
import math
INF = float('inf')
MOD = 10**9+7

M = 60
N = int(input())
A = [int(x) for x in input().split()]
f = [[0] * M for i in range(N+1)]
for i in range(N):
    a = A[i]
    for j in range(M):
        f[i+1][j] = f[i][j] + (a & 1)
        a >>= 1
ans = 0
for i in range(N):
    k = 1
    for j in range(M):
        if (A[i]>>j) & 1:
            ans += k * (N - i - 1 - f[N][j] + f[i+1][j])
        else:
            ans += k * (f[N][j] - f[i+1][j])
        ans %= MOD
        k <<= 1
        k %= MOD
print(ans)



### FIXED CODE ###

import sys
sys.setrecursionlimit(10000000)
# input = sys.stdin.readline
from bisect import *
from collections import *
from heapq import *
import functools
import itertools
import math
INF = float('inf')
MOD = 10**9+7

M = 60
N = int(input())
A = [int(x) for x in input().split()]
f = [[0] * M for i in range(N+1)]
for i in range(N):
    a = A[i]
    for j in range(M):
        f[i+1][j] = f[i][j] + (a & 1)
        a >>= 1
ans = 0
for i in range(N):
    k = 1
    for j in range(M):
        if (A[i]>>j) & 1:
            ans += k * (N - i - 1 - f[N][j] + f[i+1][j])
        else:
            ans += k * (f[N][j] - f[i+1][j])
        ans %= MOD
        k <<= 1
        k %= MOD
print(ans)
### BUGGY CODE ###

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

flag = [True]*n
for i in range(n):
  for j in range(i+1,n):
    if flag[i] == True and flag[j] == True:
      if A[i]%A[j] == 0:
        flag[i] = False
      if A[j]%A[i] == 0:
        flag[j] = False
print(flag.count(True))

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
m=max(a)
alist=[0]*(m+1)
for i in a:
  for j in range(i,m+1,i):
    alist[j]+=1
cnt=0
for i in a:
  if alist[i]==1:
    cnt+=1
print(cnt)
### BUGGY CODE ###

N, K = map(int,input().split())
H = list(map(int,input().split()))
import numpy as np
dp = np.zeros(N,dtype=np.int)
harr = np.array(H)
for i in range(1,N):
  Hi = harr[i]
  dum = dp + np.abs(Hi - harr)
  dp[i]=min(dum[max(0,i-K):i])
print(dp[-1])

### FIXED CODE ###

N, K = map(int,input().split())
H = list(map(int,input().split()))
import numpy as np
dp = np.zeros(N,dtype=np.int)
harr = np.array(H)
for i in range(1,N):
  St = max(0,i-K)
  Hi = harr[i]
  dp[i] = min(dp[max(0,i-K):i] + np.abs(Hi - harr[max(0,i-K):i]))
print(dp[-1])
### BUGGY CODE ###

R,G,B,N = map(int,input().split())

ans_count = 0

for red in range(int(N/R)+1):
  for green in range(int((N-red*R)/G)+1):
    for blue in range(int((N-red*R-green*G)/B)+1):
      if red*R + green*G + blue*B == N:
        ans_count += 1

print(ans_count)
        
  

### FIXED CODE ###

R,G,B,N = map(int,input().split())

ans_count = 0

for red in range(int(N/R)+1):
  for green in range(int((N-red*R)/G)+1):
    if (N - red*R - green*G) % B ==0 :
      ans_count += 1

print(ans_count)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
B = [0]*N
n = N
for a in (reversed(A)):
    if n*2 > N:
        B[n-1] = a
        n -= 1
        continue
    total = 0
    for i in range(2,N+2):
        if n*i <= N:
            total += B[n*i-1]
        else:
            if a == total % 2:
                B[n-1] = 0
            else:
                B[n-1] = 1
    n -= 1

M = sum(B)
print(M)
C = [str(n+1) for n, v in enumerate(B) if v == 1]

print(' '.join(C))


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
B = [0]*N
n = N
for a in (reversed(A)):
    if n*2 > N:
        B[n-1] = a
        n -= 1
        continue
    total = 0
    for i in range(2,N+2):
        if n*i <= N:
            total += B[n*i-1]
        else:
            if a == total % 2:
                B[n-1] = 0
            else:
                B[n-1] = 1
            break
    n -= 1

M = sum(B)
print(M)
C = [str(n+1) for n, v in enumerate(B) if v == 1]
print(' '.join(C))
### BUGGY CODE ###

n, a = map(int, input().split())
x = list(map(int, input().split()))
dp = [[[0] * 2501 for _ in range(n + 1)] for _ in range(n + 1)]
dp[0][0][0] = 1

for i in range(n):
    for j in range(i + 1):
        for k in range(2451):
            dp[i + 1][j][k] += dp[i][j][k]
            dp[i + 1][j + 1][k + x[i]] += dp[i][j][k]

ans = 0
for j in range(1, n + 1):
    ans += dp[n][j][j * a]

print(ans)

### FIXED CODE ###

n, a = map(int, input().split())
x = list(map(int, input().split()))
dp = [[[0] * 2501 for _ in range(n + 1)] for _ in range(n + 1)]
dp[0][0][0] = 1

for i in range(n):
    for j in range(i + 1):
        for k in range(2451):
            dp[i + 1][j][k] += dp[i][j][k]
            dp[i + 1][j + 1][k + x[i]] += dp[i][j][k]

ans = 0
for j in range(1, n + 1):
    ans += dp[n][j][j * a]

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

n = int(input())
arr = [list(map(int,input().split())) for _ in range(n-1)]
mod = 10**9+7

graph = [[] for _ in range(n)]
for a,b in arr:
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

vect = [1] + [0] * (n-1)
x_parent_stack = [0]
search_order = []
parent = [-1]*(n)
child = [[] for _ in range(n)]
while x_parent_stack:
    p_num = x_parent_stack.pop()
    search_order.append(p_num)
    for i in graph[p_num]:
        if vect[i] == 0:
            vect[i] = 1
            x_parent_stack.append(i)
            parent[i] = p_num
            child[p_num].append(i)

fac = [1] * (n+10)
inv = [1] * (n+10)
ifac = [1] * (n+10)
for i in range(2,n+10):
    fac[i]=(fac[i-1]*i)%mod
    inv[i]=-(inv[mod%i]*(mod//i))%mod
    ifac[i]=(ifac[i-1]*inv[i])%mod

size = [1]*n + [0]
dp = [1]*n + [0]
for child in search_order[::-1]:
    p = parent[child]
    size[p] += size[child]
    dp[child] = dp[child] * fac[size[child]-1] % mod
    dp[p] = dp[p] * ifac[size[child]] * dp[child] % mod

size2 = [n-i+1 for i in size]
dp2 = [1] * n
for i in search_order[1:]:
    p = parent[i]
    dp2[i] = (dp[p] * ifac[size[p]-1]) * \
             (dp2[p] * ifac[size2[p]-1]) * \
             pow(dp[i],mod-2,mod) * \
             fac[size[i]] * fac[size2[i]-2] \
             % mod

for i in range(n):
    print(dp[i] * dp2[i] * fac[size[i]+size2[i]-2] * ifac[size[i]-1] * ifac[size2[i]-1] % mod)

### FIXED CODE ###

n = int(input())
arr = [list(map(int,input().split())) for _ in range(n-1)]
mod = 10**9+7

graph = [[] for _ in range(n)]
for a,b in arr:
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

parents = [-1] * n
children = [[] for _ in range(n)]
flags = [True] * n; flags[0] = False
stack = [0]
orders = []

while stack:
    index = stack.pop()
    orders.append(index)
    for child in graph[index]:
        if flags[child]:
            parents[child] = index
            children[index].append(child)
            flags[child] = False
            stack.append(child)

fac = [1] * (n+10)
inv = [1] * (n+10)
ifac = [1] * (n+10)
for i in range(2,n+10):
    fac[i]=(fac[i-1]*i)%mod
    inv[i]= -(inv[mod%i]*(mod//i))%mod
    ifac[i]=(ifac[i-1]*inv[i])%mod

size = [1] * n
dp = [1] * n
for parent in orders[::-1]:
    for child in children[parent]:
        size[parent] += size[child]
        dp[parent] = dp[parent] * dp[child] * ifac[size[child]] % mod
    dp[parent] = dp[parent] * fac[size[parent]-1] % mod

size2 = [n-i+1 for i in size]
dp2 = [1] * n
for parent in orders[1:]:
    child = parents[parent]
    dp2[parent] = dp2[parent] * fac[size2[parent]-2] * dp[child] * dp2[child] * fac[size[parent]] * ifac[size2[child]-1] * ifac[size[child]-1] * pow(dp[parent], mod-2, mod) % mod
    
for i in range(n):
    print(fac[n-1] * ifac[size[i]-1] * ifac[size2[i]-1] * dp[i] * dp2[i] % mod)
### BUGGY CODE ###

N = int(input())
lst = list(map(int,input().split()))
if N == len(lst) :
    output = 1
    for m in lst :
        output *= m
    if output <= 1000000000000000000 :
        print(output)
    else :
        print(-1)
else :
    exit()

### FIXED CODE ###

n = int(input())
ls = list(map(int, input().split()))
res = 1
if 0 in ls:
    print(0)
    quit()
for x in ls:
    res *= x
    if res > 10**18:
        print(-1)
        quit()
print(res)