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

import math
X = int(input())
def expo(x):
    ans = 1
    for i in reversed(range(1,x+1)):
        for j in range(int(math.sqrt(x))+1):
            for k in range(2,x+1):
                if i == j**k:
                    ans = i
                    return ans
    return ans
print(expo(X))

### FIXED CODE ###

#B - Exponential
import math
X = int(input())
def expo(x):
    ans = 1
    for i in reversed(range(1,x+1)):
        for j in range(int(math.sqrt(x))+1):
            for k in range(2,int(math.sqrt(x))):
                if i == j**k:
                    ans = i
                    return ans
    return ans
print(expo(X))
### BUGGY CODE ###

import numpy as np
N = int(input())
A = list(map(int,input().split()))

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


### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
L = [[] for i in range(N)]
for i in range(N):
    L[i] = [A[i], i+1]
L = sorted(L)
for i in range(N):
    print(L[i][1])
### BUGGY CODE ###

S=input()
l=len(S)
dp=[[0 for i in range(13)] for j in range(l)]
mod=10**9+7

if S[0]=='?':
  for i in range(10):
    dp[0][i]=1
else:
  dp[0][int(S[0])]=1
for i in range(1,l):
  if S[i]=='?':
    for j in range(13):
      for k in range(10):
        dp[i][(10*j+k)%13]+=dp[i-1][j]%mod
  else:
    for j in range(13):
      dp[i][(10*j+int(S[i]))%13]+=dp[i-1][j]%mod

print(dp[l-1][5]%mod)

### FIXED CODE ###

S=input()
l=len(S)
dp=[0 for i in range(13)] 
mod=10**9+7
 
if S[0]=='?':
  for i in range(10):
    dp[i]=1
else:
  dp[int(S[0])]=1
  
for i in range(1,l):
  count=[0 for i in range(13)]
  if S[i]=='?':
    for j in range(13):
      for k in range(10):
        count[(10*j+k)%13]+=dp[j]%mod
  else:
    for j in range(13):
      count[(10*j+int(S[i]))%13]+=dp[j]%mod
  dp=count
 
print(dp[5]%mod)
### BUGGY CODE ###


import numpy as np
n = int(input())
a = list(map(int,input().split()))
ans = np.array(a)
k = 2
for i in reversed(range(1, n+1)):
    if n/k < i:
        for x in range(2, k):
            ans[i-1] += ans[x * i - 1]
        ans[i-1] = ans[i-1] % 2
    else:
        while n/k >= i:
            k += 1
        else:
            for x in range(2, k):
                ans[i-1] += ans[x * i - 1]
            ans[i-1] = ans[i-1] % 2
print(np.sum(ans))
for p in np.ndarray.flatten(np.argwhere(ans) + 1):
    print(p, end=' ')

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
ans = []
k = 2
for i in range(n, 0, -1):
    if n/k < i:
        for x in range(2, k):
            a[i-1] += a[x * i - 1]
        a[i-1] = a[i-1] % 2
    else:
        while n/k >= i:
            k += 1
        else:
            for x in range(2, k):
                a[i-1] += a[x * i - 1]
            a[i-1] = a[i-1] % 2
    if a[i-1] == 1:
        ans.append(i)
print(len(ans))
print(*ans)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(1000000)


def lcd(x0, y0):
    lx, ly = len(x0), len(y0)
    memo = [[None] * ly for _ in range(lx)]

    def memoize(x, y):
        if x < 0 or y < 0:
            return 0
        if memo[x][y] is not None:
            return memo[x][y]
        result = memo[x][y] = main(x, y)
        return result

    def main(x, y):
        if x0[x] == y0[y]:
            return memoize(x - 1, y - 1) + 1
        return max(memoize(x - 1, y), memoize(x, y - 1))

    return main(lx - 1, ly - 1)


n = int(input())
while n:
    print(lcd(input(), input()))
    n -= 1

### FIXED CODE ###

n = int(input())
for _ in range(n):
    a, b = input(), input()
    indices = []
    for cb in b:
        bgn_idx = 0
        for i, cur_idx in enumerate(indices):
            chr_idx = a.find(cb, bgn_idx) + 1
            if not chr_idx:
                break
            if chr_idx < cur_idx:
                indices[i] = chr_idx
            bgn_idx = cur_idx
        else:
            chr_idx = a.find(cb, bgn_idx) + 1
            if chr_idx:
                indices.append(chr_idx)
    print(len(indices))
### BUGGY CODE ###

def check(ary, div):
    c = 0
    for i in range(len(ary)):
        if ary[i] % div == 0:
            c += 1
    if c >= len(ary) - 1:
        return True
    else:
        return False 
 
N = int(input())
data = list(map(int, input().split()))
ans = 1
for i in range(1, max(data) + 1):
    if check(data, i):
        ans = i
 
print(ans)


### FIXED CODE ###

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

def gcd(a, b):
    while b:
        a, b = b, a % b
        # print("a b", a, b)
    return a

left_ = [0] * (n + 1)
right_ = [0] * (n + 1)
ans = []

for i in range(n):
    left_[i] = gcd( left_[i-1], data[i] )

for i in range(n-1, 0, -1):
    right_[i] = gcd( right_[i+1], data[i] )

for i in range(n):
    ans += [ gcd( left_[i-1], right_[i+1] ) ]

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

all,rolls=map(int,input().split())
List=list(map(int,input().split()))

sum = 0
sumList =[]

for i in range(all - rolls + 1):
	all_sum = 0
	for j in range(rolls):
		sum = 0
		for k in range(List[i + j] + 1):
			sum = sum + k
		sum = sum / List[i + j]
		all_sum = all_sum + sum
	sumList.append(all_sum)
sumList.sort(reverse=True)
print(sumList[0])

### FIXED CODE ###

all,rolls=map(int,input().split())
inputList=list(map(int,input().split()))

sum = 0
sumList =[]

# 初めに全期待値計算
for i in range(all):
	inputList[i] = (inputList[i] + 1) / 2

# 最初の組み合わせの期待値計算
for i in range(rolls):
	sum = sum + inputList[i]
sumList.append(sum)

# 2番目以降の期待値計算
for i in range(all - rolls):
	sum = sum + inputList[i + rolls] - inputList[i]
	sumList.append(sum)

sumList.sort(reverse=True)
print(sumList[0])
### BUGGY CODE ###

def gcd(a,b):
	return gcd(b,a%b) if b else a
n = int(input())
a = list(map(int,input().split()))
lcm = 1
for v in a:
	lcm *= v//gcd(v,lcm)
ans = 0
for v in a:
	ans += lcm // v
print(ans%1000000007)

### FIXED CODE ###

def gcd(a,b):
	return gcd(b,a%b) if b else a
n = int(input())
a = list(map(int,input().split()))
lcm = 1
for v in a:
	lcm *= v//gcd(v,lcm)
ans = 0
for v in a:
	ans += lcm // v
print(ans%1000000007)
### BUGGY CODE ###

N=int(input())
ANi=input().split()
AN=list(map(int,ANi))


Xhairetsu={}


for i in range(len(AN)):
    for X in range(1,10**5):
        if AN[i]<=X+1 and AN[i]>=X-1 and X  not in Xhairetsu.keys():
            Xhairetsu[X]=1
        elif AN[i]<=X+1 and AN[i]>=X-1 and X in Xhairetsu.keys():
            Xhairetsu[X]+=1
        
print(max(Xhairetsu.values()))

### FIXED CODE ###

N=int(input())
ANi=input().split()
AN=list(map(int,ANi))

Whairetsu={}
Xhairetsu={}
Yhairetsu={}


for i in range(len(AN)):
    if AN[i] not in Xhairetsu.keys():
        Xhairetsu[AN[i]]=1
    elif AN[i] in Xhairetsu.keys():
        Xhairetsu[AN[i]]+=1
    
    if AN[i] -1 not in Whairetsu.keys():
        Whairetsu[AN[i]-1]=1
    elif AN[i]-1 in Whairetsu.keys():
        Whairetsu[AN[i]-1]+=1
    
    if AN[i] +1 not in Yhairetsu.keys():
        Yhairetsu[AN[i]+1]=1
    elif AN[i]+1 in Yhairetsu.keys():
        Yhairetsu[AN[i]+1]+=1
    


anshairetsu={}
for i in range(10**5+1):
    if i in Whairetsu.keys():
        if i in anshairetsu.keys():
            anshairetsu[i]+=Whairetsu[i]
        else:
            anshairetsu[i]=Whairetsu[i]
            
    if i in Xhairetsu.keys():
        if i in anshairetsu.keys():
            anshairetsu[i]+=Xhairetsu[i]
        else:
            anshairetsu[i]=Xhairetsu[i]
            
    if i in Yhairetsu.keys():
        if i in anshairetsu.keys():
            anshairetsu[i]+=Yhairetsu[i]
        else:
            anshairetsu[i]=Yhairetsu[i]
print(max(anshairetsu.values()))
### BUGGY CODE ###

def main():
    import bisect
    from array import array
    B=bisect.bisect_left
    I=10**9+1
    n,q,*t=map(int,open(0).read().split())
    d=t[-q:]
    N0=2**(q-1).bit_length()
    data=array('I',[I]*2*N0)
    for x,l,r in sorted((x,B(d,s-x),B(d,t-x))for s,t,x in zip(t[:-q:3],t[1:-q:3],t[2:-q:3]))[::-1]:
        L,R=l+N0,r+N0
        while L<R:
            if R&1:
                R-=1
                data[R-1]=x
            if L&1:
                data[L-1]=x
                L+=1
            L>>=1
            R>>=1
    for k in range(q):
        k+=N0-1
        s=I
        while k+1:
            if data[k]<s:s=data[k]
            k=(k-1)//2
        print(-(s==I)or s)
if __name__=='__main__':
    main()

### FIXED CODE ###

def main():
    from bisect import bisect_left
    def update(l,r,v):
        L,R=l+N0,r+N0
        while L<R:
            if R&1:
                R-=1
                data[R-1]=v
            if L&1:
                data[L-1]=v
                L+=1
            L>>=1
            R>>=1
    def query(k):
        k+=N0-1
        s=10**18
        while k+1:
            if data[k]<s:s=data[k]
            k=~-k//2
        return s
    n,*t=open(0)
    n,q=map(int,n.split())
    d=[-10**18]+list(map(int,t[n:]))+[10**18]
    N0=2**(q+1).bit_length()
    data=[10**18]*2*N0
    for x,t,s in sorted(list(map(int,t.split()))[::-1]for t in t[:n])[::-1]:
        l=bisect_left(d,s-x)
        r=bisect_left(d,t-x)
        update(l,r,x)
    for i in range(q):
        a=query(i+1)
        print(-(a==10**18)or a)
if __name__=='__main__':
    main()
### BUGGY CODE ###

import bisect

n = int(input())
ll = list(map(int, input().split()))
ll.sort()

ans = 0
for i in range(n-2):
    e1 = ll[i]
    for j in range(i+1, n-1):
        e2 = ll[j]
        ans += bisect.bisect_left(ll[j+1:], e1+e2)

print(ans)

### FIXED CODE ###

import bisect

n = int(input())
ll = list(map(int, input().split()))
ll.sort()

ans = 0
for i in range(n-2):
    e1 = ll[i]
    for j in range(i+1, n-1):
        e2 = ll[j]
        ans += bisect.bisect_left(ll[j+1:], e1+e2)

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

r,g,b,n = map(int, input().split())

cnt = 0
for rr in range(n // r + 1):
  for gg in range(n // g + 1):
    sum = r * rr + g * gg
    rest = n - sum
    if rest < 0:
      continue
    if rest % b == 0:
      bb = (n-sum) // b
      cnt += 1

print(cnt)


### FIXED CODE ###

r,g,b,n = map(int, input().split())

cnt = 0
for rr in range(n // r + 1):
  for gg in range((n - r * rr) // g + 1):
    rest = n - r * rr - g * gg
    cnt += (rest % b == 0)

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

n, q = map(int, input().split())
s = input()
ans = []
for i in range(0, q):
    l, r = map(int, input().split())
    ans.append(s[l-1: r].replace('AC', ' ').count(' '))
for i in ans:
    print(i)

### FIXED CODE ###

n, q = map(int, input().split())
s = ' ' + input()
heap = [0] * (n + 1)
cnt = 0
for i in range(2, n + 1):
    if s[i - 1] == 'A' and s[i] == 'C':
        cnt += 1;
    heap[i] = cnt
ans = []
for i in range(q):
    l, r = map(int, input().split())
    ans.append(heap[r] - heap[l])
for i in ans:
    print(i)
### BUGGY CODE ###

#template
def inputlist(): return [int(k) for k in input().split()]
#template
def dijkstra(s,n,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

H,W = inputlist()
cost = [0]*10
for i in range(10):
    cost[i] = inputlist()
A = [0]*H
for i in range(H):
    A[i] = inputlist()

ans = 0

for x in range(H):
    for y in range(W):
        if A[x][y] == -1:
            continue
        d = dijkstra(A[x][y],10,cost)
        ans += d[1]
print(ans)

### FIXED CODE ###

from scipy.sparse.csgraph import shortest_path
import numpy as np
H,W = [int(i) for i in input().split()]
c = [0] * 10
for i in range(10):
    c[i] = [int(j) for j in input().split()]
c = np.array(c)
path = shortest_path(c,'D')
A = [0] * H
for i in range(H):
    A[i] = [int(j) for j in input().split()]
ans = 0
for i in range(H):
    for j in range(W):
        if A[i][j] == 1 or A[i][j] == -1:
            continue
        ans += path[A[i][j]][1]
print(int(ans))
### BUGGY CODE ###

n, m = map(int, input().split())
A = list(map(int, input().split()))
BC = [list(map(int, input().split())) for _ in range(m)]
BC.sort(key=lambda x: -x[1])

[A.extend([BC[i][1]] * BC[i][0]) for i in range(m)]

A.sort(reverse=True)
print(sum(A[:n]))

### FIXED CODE ###

import sys

input = sys.stdin.readline
n, m = map(int, input().split())
A = list(map(int, input().split()))
BC = [list(map(int, input().split())) for _ in range(m)]
BC.sort(key=lambda x: -x[1])

maxi = n*2
extend = A.extend
[extend([ls[1]] * ls[0]) for ls in BC if len(A) <= maxi]
A.sort(reverse=True)

print(sum(A[:n]))
### BUGGY CODE ###

from heapq import*;n,m,*a=[-int(i)for i in open(0).read().split()];heapify(a);exec('heappush(a,0--heappop(a)//2);'*-m);print(-sum(a))

### FIXED CODE ###

from heapq import*;n,m,*a=[-int(i)for i in open(0).read().split()];heapify(a);exec('heappush(a,0--heappop(a)//2);'*-m);print(-sum(a))
### BUGGY CODE ###

input = raw_input

def init():
    table = [True] * 2000001
    table[0] = False
    table[1] = False
    n = len(table)
    for i in range(2, n):
        for j in range(i + i, n, i):
            table[j] = False
    return table
    
def solve(price, ps, is_prime):
    dp = []
    for i in range(len(ps)):
        dp.append([False] * (price + 1))

    if ps[0] <= price:
        dp[0][ps[0]] = True
    dp[0][0]     = True

    for i in range(1, len(ps)):
        for p in range(price + 1):
            if p >= ps[i]:
                dp[i][p] = dp[i - 1][p] or dp[i][p - ps[i]]
            else:
                dp[i][p] = dp[i - 1][p]

    p = -1
    for i in range(0, price + 1):
        if is_prime[i] and dp[len(ps) - 1][i]:
            p = i
    if p == -1:
        print("NA")
    else:
        print(p)
    
def main():
    table = init()
    while True:
        n, price = map(int,input().split())
        if n == 0 and price == 0:
            return
        ps = []
        for i in range(n):
            ps.append(int(input()))
        solve(price, ps, table)

main()

### FIXED CODE ###

from datetime import datetime
import math

def measure(f):
    measure_start = datetime.now()
    v = f()
    print(datetime.now() - measure_start)
    return v

input = raw_input
range = xrange
    
def init():
    table = [True] * 1000001
    table[0] = False
    table[1] = False
    n = len(table)

    def prime(p):
        for i in range(p + p, n, p):
            table[i] = False
    prime(2)
    prime(3)
    prime(5)
    prime(7)
    prime(11)
    prime(13)

    for i in range(2, int(math.sqrt(n) + 1)):
        if (i % 2 != 0 and i % 3 != 0 and i % 5 != 0 and
            i % 7 != 0 and i % 11 != 0 and i % 13 != 0):
            for j in range(i * i, n, i):
                table[j] = False
#    for i in range(len(table)):
#        if table[i]:
#            print(i)
    return table
    
def solve(price, ps, is_prime):
    dp = [0] * ((price >> 5) + 1)

    for i in range(0, price + 1,ps[0]):
        dp[i >> 5] |= 1 << (i & 31)
    dp[0] = 1
    
    for i in range(1, len(ps)):
        cur_p = ps[i]
        r = cur_p & 31
        rest = 0
        if cur_p >= 32:
            for p in range(cur_p, price + 1, 32):
                i1 = (p - cur_p) >> 5
                i2 = p >> 5
                v = dp[i1]
                dp[i2] |= (v << r) | rest
                rest = (v >> (32 - r)) & ((1 << r) - 1)
        else:
            for p in range(cur_p, price + 1):
                dp[p >> 5] |= (dp[(p - cur_p) >> 5] >> ((p - cur_p) & 31) & 1) << (p & 31)
            
    p = -1
    for i in range(0, price + 1):
        if is_prime[i] and (dp[i >> 5] >> (i & 31)) & 1 == 1:
            p = i
    if p == -1:
        print("NA")
    else:
        print(p)
    
def main():
    table = init()
    while True:
        n, price = map(int,input().split())
        if n == 0 and price == 0:
            return
        ps = []
        for i in range(n):
            ps.append(int(input()))
        solve(price, ps, table)

main()
### BUGGY CODE ###

import sys
from sys import stdin, stdout

rem=10**9+7
sys.setrecursionlimit(10 ** 6)
take = lambda: map(int, stdin.readline().split())

n=input()
ans=[1 for i in range(n+1)]
pos={}
for i in range(1,n+1):
    x=input()
    pos[x]=i
for i in range(n-1,0,-1):
    if pos[i]<pos[i+1]:
        ans[i]=ans[i+1]+1
#print(ans)
print n-max(ans)

### FIXED CODE ###

import sys
from sys import stdin, stdout

rem=10**9+7
sys.setrecursionlimit(10 ** 6)
take = lambda: map(int, stdin.readline().split())

n=input()
ans=[1 for i in range(n+1)]
pos={}
for i in range(1,n+1):
    x=take()[0]
    pos[x]=i
for i in range(n-1,0,-1):
    if pos[i]<pos[i+1]:
        ans[i]=ans[i+1]+1
#print(ans)
print n-max(ans)
### BUGGY CODE ###

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

RL=(N+R-1)//R

cnt=0
for r in range(RL+1):
    if r*R>N:continue
    GL=(N-r*R+G-1)//G
    for g in range(GL+1):
        if (r*R+g*G)>N:continue
        if (N-r*R-g*G)%B==0:
            cnt+=1

print(cnt)

### FIXED CODE ###

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

ans = 0
for i in range(int(N / R) + 1):
    for j in range(int((N - i * R) / G) + 1):
        if ((N - (i * R + j * G)) % B == 0):
            ans += 1
print(ans)
### BUGGY CODE ###

import sys
def add_link(a, b):
    la = links[a]
    i, j = [(0, 1), (1, 0)][s[b] == 'B']
    if not la[i] and la[j]:
        able[a] = True
    la[i].add(b)

n, m = map(int, input().split())
s = input()
links = [[set(), set()] for _ in range(n)]
able = [False] * n
for line in sys.stdin.readlines():
    a, b = map(int, line.split())
    a -= 1
    b -= 1
    add_link(a, b)
    add_link(b, a)
flag = 1
while flag ==1:
  flag = 0
  for i in range(n):
    if not able[i]:
      continue
    for k in range(2):
      for j in links[i][k].copy():
        if not able[j]:
          links[i][k].remove(j)
    if (links[i][0] == set() or links[i][1] == set()):
      flag =1
      able[i] = False
if any(able):
  print("Yes")
else:
  print("No")

### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)
n, m = map(int, input().split())
s = input()
links = [[] for _ in range(2*n)]
visit = [0] * n *2
for line in sys.stdin.readlines():
    a, b = map(int, line.split())
    a -= 1
    b -= 1
    if s[a] == s[b]:
      links[a].append(b+n)
      links[b].append(a+n)
    else:
      links[a+n].append(b)
      links[b+n].append(a)
def dfs(v):
  visit[v] = 1
  for i in links[v]:
    if visit[i] == 1:
      print("Yes")
      exit()
    elif visit[i] == 0:
      dfs(i)
  visit[v] = -1
  
for i in range(n):
  if visit[i] == 0:
    dfs(i)
print("No")
### BUGGY CODE ###

S = input()
Q = int(input())
flag = 1

for i in range(Q):
    q = list(map(str, input().split()))
    if q==["1"]:
        flag *= -1
    else:
        if flag==1 and q[1]=="1":
            S = q[2]+S
        elif flag==1 and q[1]=="2":
            S += q[2]
        elif flag==-1 and q[1]=="1":
            S += q[2]
        else:
            S = q[2]+S

if flag==1:
    print(S)
else:
    print("".join(list(reversed(S))))


### FIXED CODE ###

S = input()
Q = int(input())
flag = 1
left = ""
right = ""

for i in range(Q):
    q = input().split()
    if q==["1"]:
        flag *= -1
    else:
        if flag==1 and q[1]=="1":
            left = q[2]+left
        elif flag==1 and q[1]=="2":
            right += q[2]
        elif flag==-1 and q[1]=="1":
            right += q[2]
        else:
            left = q[2]+left
# print(S)

if flag==1:
    print(left+S+right)
else:
    print(right[::-1]+S[::-1]+left[::-1])
### BUGGY CODE ###

N, M = map(int, input().split())
L, R = map(int, input().split())
ans = set(range(L, R + 1))
for i in range(M - 1):
    L, R = map(int, input().split())
    ans &= set(range(L, R + 1))
print(len(ans))


### FIXED CODE ###

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

min_n = 0
max_n = N
for l,r in LRlist:
    min_n = l if l>min_n else min_n
    max_n = r if r<max_n else max_n

if max_n-min_n >= 0:
    print(max_n-min_n+1)
else:
    print(0)
### BUGGY CODE ###

from functools import lru_cache

N, A = map(int, input().split())
X = tuple(int(x) for x in input().split())

# 平均を出すのに選んだ個数が必要
@lru_cache(maxsize=None)
def rec(x, a, k):
    """
    :param x: tuple
        数列
    :param a: int
        総和
    :param k: int
        選ぶ個数
    :return: int
        通り数
        Number of patterns
    """
    if k == 0:
        if a == 0:
            return 1
        else:
            return 0

    if a < 0 or len(x) < k:
        return 0

    ret = rec(x[1:], a, k)
    ret += rec(x[1:], a - x[0], k - 1)
    return ret
X = tuple(sorted(X))
m = (rec(X, k * A, k) for k in range(1, N + 1))
print(sum(m))

### FIXED CODE ###

from functools import lru_cache

N, A = map(int, input().split())
X = tuple(int(x) for x in input().split())

# 平均を出すのに選んだ個数が必要
@lru_cache(maxsize=None)
def rec(i, a, k):
    """
    :param i: int 
        数列の長さ
    :param a: int
        総和
    :param k: int
        選ぶ個数
    :return: int
        通り数
        Number of patterns
    """
    if k == 0:
        if a == 0:
            return 1
        else:
            return 0

    if a < 0 or i < k:
        return 0

    ret = rec(i - 1, a, k)
    ret += rec(i - 1, a - X[i - 1], k - 1)
    return ret

i = len(X)
m = (rec(i, k * A, k) for k in range(1, N + 1))
print(sum(m))
### BUGGY CODE ###

# seishin.py
from collections import deque
N = int(input())
*P, = map(int, input().split())
MOD = 10**9 + 7

G = [[] for i in range(N+1)]
for i, p in enumerate(P):
    G[p].append(i+1)
Q = [None]*(N+1)
A = [None]*(N+1)
PP = [1]*(N+1)
for i in range(N):
    PP[i+1] = PP[i]*2 % MOD

for i in range(N, -1, -1):

    # 子ノードのdequeを集める
    R = None
    for j in G[i]:
        S = Q[j]
        if not R:
            R = S
            continue

        # |R| > |S|
        if len(R) < len(S):
            R, S = S, R

        # dequeの小さい方から大きい方へマージする処理
        for s, r in zip(S, R):
            a0, a1, a2, c0 = s
            b0, b1, b2, c1 = r
            r[0] = a0*b0 % MOD
            r[1] = (a0*b1 + a1*b0) % MOD
            r[2] = (a0*b2 + a1*b1 + a2*b0 + a1*b2 + a2*b2 + a2*b1) % MOD
            r[3] = c0+c1

    k = len(G[i])
    if k:
        r = [PP[k] - k, k, 0, k]
    else:
        r = None
    if R:
        # a0 <- a2
        for e in R:
            e[0] += e[2]
            e[2] = 0
        R.appendleft(r)
        Q[i] = R
    else:
        if r:
            Q[i] = deque([r])
        else:
            Q[i] = deque()
ans = pow(2, N, MOD)
for a0, a1, a2, c in Q[0]:
    ans += PP[N+1-c] * a1 % MOD
print(ans % MOD)

### FIXED CODE ###

# seishin.py
from collections import deque
N = int(input())
*P, = map(int, input().split())
MOD = 10**9 + 7

G = [[] for i in range(N+1)]
U = [0]*(N+1)
C = [0]*(N+1)
for i, p in enumerate(P):
    G[p].append(i+1)
    U[i+1] = u = U[p]+1
    C[u] += 1
Q = [None]*(N+1)
PP = {}
def pp(k):
    if k not in PP:
        PP[k] = p = pow(2, k, MOD)
        return p
    return PP[k]
L = [0]*(N+1)

ept = []
sz = L.__getitem__
for i in range(N, -1, -1):
    g = G[i]
    if not g:
        continue

    # 子ノードのdequeを集める
    g.sort(key=sz, reverse=1)
    k = len(g)
    e = [pp(k) - k, k, 0]

    g0 = g[0]
    L[i] = L[g0] + 1
    if L[g0] == 0:
        Q[i] = deque([e])
        continue
    Q[i] = R = Q[g0]
    if k > 1:
        # a0 <- a2
        for s, r in zip(Q[g[1]] or ept, R):
            r[0] += r[2]; r[2] = 0

        for j in g[1:]:
            S = Q[j]
            if not S:
                break

            # dequeの小さい方から大きい方へマージする処理
            for (a0, a1, a2), r in zip(S, R):
                b0, b1, b2 = r; a0 += a2
                r[0] = a0*b0 % MOD
                r[1] = (a0*b1 + a1*b0) % MOD
                r[2] = ((a0+a1)*b2 + a1*b1) % MOD
    R.appendleft(e)
print((pp(N) + sum(pp(N+1-c) * a1 % MOD for (a0, a1, a2), c in zip(Q[0], C[1:]))) % MOD)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
x = 1
for ai in a:
    x*=ai
if x>10**18:
    print(-1)
else:
    print(x)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
if 0 in a:
    print(0)
else:
    x = 1
    m = 10**18
    for ai in a:
        x*=ai
        if x>m:
            x = -1
            break
    print(x)