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

#!/usr/bin/env python3

import sys

def main():
    sys.setrecursionlimit(10 ** 6)
    n, q = map(int, input().split())
    adj = [[] for i in range(n)]
    for i in range(n - 1):
        a, b = map(int, input().split())
        adj[a - 1].append(b - 1)
        adj[b - 1].append(a - 1)
    add_node = [0 for i in range(n)]
    for i in range(q):
        p, x = map(int, input().split())
        add_node[p - 1] += x
    counter = [0 for i in range(n)]
    visited = [False for i in range(n)]
    dfs(0, adj, visited, counter, 0, add_node)
    print(" ".join(str(x) for x in counter))

def dfs(i, adj, visited, counter, add, add_node):
    visited[i] = True
    add += add_node[i]
    counter[i] += add
    for j in adj[i]:
        if not visited[j]:
            dfs(j, adj, visited, counter, add, add_node)

if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python3

import sys

def dfs(i, p, add):
    add += add_node[i]
    counter[i] += add
    for j in adj[i]:
        if j != p:
            dfs(j, i, add)

sys.setrecursionlimit(10 ** 6)
n, q = map(int, input().split())
adj = [[] for i in range(n)]
for i in range(n - 1):
    a, b = map(int, sys.stdin.readline().split())
    adj[a - 1].append(b - 1)
    adj[b - 1].append(a - 1)
add_node = [0 for i in range(n)]
for i in range(q):
    p, x = map(int, sys.stdin.readline().split())
    add_node[p - 1] += x
counter = [0 for i in range(n)]
dfs(0, -1, 0)
print(" ".join(str(x) for x in counter))
### BUGGY CODE ###

N=int(input())
A=[int(input()) for i in range(N)]
M=max(A)
sort_A=sorted(A, reverse=True)

for j in range(N):
    if A[j]==M:
        if A.count(M)==1:
            print(sort_A[1])
        else:
            print(M)
    else:
        print(M)


### FIXED CODE ###

N=int(input())
a=[int(input()) for i in range(N)]
sw=True
b=sorted(a,reverse=True)

if b[0]>b[1]:
    max2=b[1]
    max1=b[0]
    sw=False

if sw==True:
    max1=b[0]
    for k in range(N):
        print(max1)
else:
    for k in range(N):
        if a[k]==max1:
            print(max2)
        else:
            print(max1)
### BUGGY CODE ###

N,K = map(int,input().split())
X = list(map(int,input().split()))
ANS = []
for i in range(N-K+1) :
    L = X[i:K+i]
    l1 = abs(min(L))+abs(max(L)-min(L))
    l2 = abs(max(L))+abs(max(L)-min(L))
    ANS.append(min(l1,l2))
print(min(ANS))



### FIXED CODE ###

N,K = map(int,input().split())
L = list(map(int,input().split()))
ANS = []
for i in range(len(L)-K+1) :
    p = L[i]
    q = L[i+K-1]
    if p*q == 0 :
        r = abs(p-q)
    elif p*q < 0 :
        r = 2*min(abs(p),q) + max(abs(p),q)
    else :
        if p > 0 :
            r = q
        else :
            r = abs(p)
    ANS.append(r)
ans = min(ANS)
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
n = int(input())
a = [int(input())-1 for _ in range(n)]
# -1をしたので、if a[s] == 1になったら終了
#print(a)
cnt = 0
visit = [0] #出発点は訪れてる
i = 0
while cnt <= n:
    cnt += 1
    #print(visit)
    if a[i] in visit:#循環するのでbreak
        print(-1)
        exit(0)
    elif a[i] == 1: #ボタン２を押すので今までの回数を答える
        print(cnt)
        exit(0)
    else:# i を更新　visitに現在のボタンを追加する
        visit.append(a[i])
        i = a[i]

### FIXED CODE ###

#!/usr/bin/env python3
n = int(input())
a = [int(input())-1 for _ in range(n)]
# -1をしたので、if a[s] == 1になったら終了
#print(a)
cnt = 0
visit = [0] #出発点は訪れてる
i = 0 # bottom position a[i] = next_bottom
while cnt <= n:#無限ループになる理由がわからん in が最悪のケースでO(nlogn)
    cnt += 1
    #print(visit)
    """if a[i] in visit:#循環するのでbreak
        print(-1)
        exit(0)"""
    if a[i] == 1: #ボタン２を押すので今までの回数を答える
        print(cnt)
        exit(0)
    else:# i を更新　visitに現在のボタンを追加する
        #visit.append(a[i])
        i = a[i]
print(-1)
### BUGGY CODE ###

import math
N,D,A = map(int,input().split(' '))
XHn = [ list(map(int,input().split(' '))) for _ in range(N)]
ans = 0
XHn.sort()
for i  in range(N):
    x = XHn[i][0]
    h = XHn[i][1]
    need_bom = 0
    distance_bom = x + D*2
    if h > 0:
        need_bom = math.ceil(h/A)
        for i2 in range(i,N):
            x2 = XHn[i2][0]
            if x2 <= distance_bom:
                XHn[i2][1] -= A*need_bom
            else:
                break
        ans += need_bom
print(ans)

### FIXED CODE ###

import math
from collections import deque
N,D,A = map(int,input().split(' '))
XHn = [ list(map(int,input().split(' '))) for _ in range(N)]
ans = 0
XHn.sort()
attacks = deque([]) # (区間,攻撃回数)
attack = 0
ans = 0
for i  in range(N):
    x = XHn[i][0]
    h = XHn[i][1]
    while len(attacks) > 0 and x > attacks[0][0]:
        distance,attack_num = attacks.popleft()
        attack -= attack_num*A
    if h > attack:
        diff = h - attack 
        distance_attack = x + D*2
        need_attack = math.ceil(diff/A)
        attacks.append((distance_attack,need_attack))
        attack += A*need_attack
        ans += need_attack
print(ans)
### BUGGY CODE ###

#from collections import deque,defaultdict
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 998244353

def ddprint(x):
  if DBG:
    print(x)

def modinv2(x,r):
  return pow(x,r-2,r)

def comb(n,a,R):
    return (fact[n]*modinv2(fact[n-a]*fact[a],R))

def factinit(n,R):
    global fact
    fact = [1]*(n+1)
    for i in range(2,n+1):
        fact[i] = (fact[i-1]*i)%R


n,a,b,k = inm()
sm = 0
factinit(n,R)
for pq in range(n+1):
    if (k-a*pq)%b>0:
        continue
    qr = (k-a*pq)//b
    if qr>n:
        continue
    q1 = max(0,pq+qr-n)
    q2 = min(pq,qr)
    for q in range(q1,q2+1):
        p = pq-q
        r = qr-q
        s = n-p-q-r
        sor = ((fact[p]*fact[q]%R)*(fact[r]*fact[s]%R))%R
        sm = (sm+fact[n]*modinv2(sor,R))%R
print(sm)


### FIXED CODE ###

#from collections import deque,defaultdict
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 998244353

def ddprint(x):
  if DBG:
    print(x)

def modinv2(x,r):
  return pow(x,r-2,r)

def comb(n,a,R):
    return (fact[n]*modinv2(fact[n-a]*fact[a],R))

def factinit(n,R):
    global fact
    fact = [1]*(n+1)
    for i in range(2,n+1):
        fact[i] = (fact[i-1]*i)%R


n,a,b,k = inm()
sm = 0
factinit(n,R)
for pq in range(n+1):
    if k<a*pq or (k-a*pq)%b>0:
        continue
    qr = (k-a*pq)//b
    if qr>n:
        continue
    sm = (sm+comb(n,pq,R)*comb(n,qr,R))%R
print(sm)
### BUGGY CODE ###

n = int(input())
num = [int(x) for x in input().split()]
a = 1

for i in num:
  a *= i
  
if a > 10**18:
    a = -1

print(a)

### FIXED CODE ###

n = int(input())
l = [int(x) for x in input().split()]

if 0 in l:
    r=0
else:
    r = 1
    for x in range(n):
        r = r * l[x]
        if r > 10**18:
            r=-1
            break
  
print(r)
### BUGGY CODE ###

n = int(input())
i = 0
s = list()
while i<n:
    s.append(str(input()))
    i+=1
i = 0
while i < n:
    j = n-1
    while j > 0:
        if s[j] >s[j-1]:
            x = s[j]
            s[j] = s[j-1]
            s[j-1] = x
        j-=1
    i+=1
i = 0
c = 0
x = "0"
while i<n:
    if s[i]!=x:
        x = s[i]
        c+=1
    i+=1

print(c)


### FIXED CODE ###

n = int(input())
i = 0
s = set()
while i<n:
    s.add(str(input()))
    i+=1


print(len(s))
### BUGGY CODE ###

from math import *

def main():
    m, n = [int(_) for _ in input().split()]
    print(int((m ** n) % 1000000007))

main()



### FIXED CODE ###

def main():
    m, n = [int(_) for _ in input().split()]
    print(pow(m, n, 1000000007))

main()
### BUGGY CODE ###

N = int(input())
Stemp = str(input())
S = []
for i in range(N):
  temp = int(Stemp[i])
  S.append(temp)
#print(S)
#i桁目までみて、1文字目がx、2文字目がy、3文字目がzのがあるか
dp = [[False]*10 for _ in range(N+1)]
dpp = [[[False]*10 for _ in range(10)] for _ in range(N+1)]
dppp = [[[[False]*10 for _ in range(10)] for _ in range(10)] for _ in range(N+1)]
 
for i in range(N):
  now = S[i] #i桁目 1index
  #dp[i+1][now] = 1
  for x in range(10):
    if x == now:
      dp[i+1][x] = True
      #print(dp[i+1][x])
    else:
      dp[i+1][x] = dp[i][x]|dp[i+1][x]
    for y in range(10):
      if y == now and dp[i][x]:
        dpp[i+1][x][y] = True
      else:
        dpp[i+1][x][y] = dpp[i][x][y]|dpp[i+1][x][y]
      for z in range(10):
        if z == now and dpp[i][x][y]:
          dppp[i+1][x][y][z] = True
        else:
          dppp[i+1][x][y][z] = dppp[i][x][y][z]|dppp[i+1][x][y][z]
#print(dp)
#print(dpp)
#print(dppp)
ans = 0
for i in range(10):
  for j in range(10):
    for k in range(10):
      if dppp[N][i][j][k]:
        ans += 1
        
print(ans)       

### FIXED CODE ###

N = int(input())
Stemp = str(input())
S = []
for i in range(N):
  temp = int(Stemp[i])
  S.append(temp)
ans = set([])
L = [[] for _ in range(10)]
for i in range(N):
  L[S[i]].append(i)
#print(L)
for v in range(1000):
  a = v//100
  b = (v-a*100)//10
  c = v-a*100-b*10
  if not L[a]:
    continue
  left = min(L[a])
  Flag = False
  for x in L[b]:
    if x > left:
      mid = x
      Flag = True
      break
  if not Flag:
    continue
  Flag = False
  for y in L[c]:
    if y > mid:
      right = y
      Flag = True
      break
  if not Flag:
    continue
  ans.add(v)
  #print(v,left,mid,right)
print(len(ans))
### BUGGY CODE ###

import heapq

n = int(input())
li = [-1 * int(i) for i in input().split()]
ans = 0

for a in range(len(li)):
  li2 = li[a:]
  for b in range(len(li2)):
    li3 = li2[:b+1]
    li4 = heapq.heapify(li3)
    if len(li3) >= 2:
      heapq.heappop(li3)
      ans += ((-1)*heapq.heappop(li3))

print(ans)

### FIXED CODE ###

n = int(input())
aa = list(map(int, input().split()))
ans = 0
pos = [0] * (n + 1)

for i, a in enumerate(aa):
    pos[a] = i + 2
Lnext = [1, 1] + list(range(1, n + 1)) + [n, n]
Rnext = [3, 3] + list(range(3, n + 3)) + [n + 2, n + 2]
for a in range(1,n + 1):
    i = pos[a]
    l0 = Lnext[i]
    l1 = Lnext[l0]
    r0 = Rnext[i]
    r1 = Rnext[r0]
    ans += a * ((l0 - l1) * (r0 - i) + (i - l0) * (r1 - r0))
    Lnext[r0] = l0
    Rnext[l0] = r0
print(ans)
### BUGGY CODE ###

H, W = list(map(int, input().split()))
maps = [[None]*(W+2) for _ in range(H+2)]
maps[0] = ['#']*(W+2)
for i in range(H):
    maps[i+1] = ['#']+list(input())+['#']
maps[H+1] = ['#']*(W+2)
# pprint.pprint(maps)
# L[i][j]:それぞれ該当マスから上下左右に'.'が続く数
ans = 0
L = [[[0]*4 for _ in range(W+2)] for _ in range(H+2)]
for i in range(1, H+1):
    for j in range(1, W+1):
        if maps[i][j] == '.':
            L[i][j][0] = L[i-1][j][0]+1
            L[i][j][2] = L[i][j-1][2]+1
        if maps[H+1-i][W+1-j] == '.':
            L[H+1-i][W+1-j][1] = L[H+2-i][W+1-j][1]+1
            L[H+1-i][W+1-j][3] = L[H+1-i][W+2-j][3]+1
for i in range(H+2):
    for j in range(W+2):
        ans = max(ans, sum(L[i][j])-3)
print(ans)


### FIXED CODE ###

H, W = list(map(int, input().split()))
maps = [['']*(W+2) for _ in range(H+2)]
maps[0] = ['#']*(W+2)
for i in range(H):
    maps[i+1] = ['#']+list(input())+['#']
maps[H+1] = ['#']*(W+2)

ans = 0
L = [[[0, 0] for _ in range(W)] for _ in range(H)]
for i in range(H):
    for j in range(W):
        if maps[i+1][j+1] == '#':
            continue
        if j >= 1 and L[i][j-1][1] > 0:
            L[i][j][1] = L[i][j-1][1]
        else:
            u = j+1
            while maps[i+1][u] == '.':
                u += 1
            L[i][j][1] = u-j-1
        if i >= 1 and L[i-1][j][0] > 0:
            L[i][j][0] = L[i-1][j][0]
        else:
            u = i+1
            while maps[u][j+1] == '.':
                u += 1
            L[i][j][0] = u-i-1
        ans = max(ans, L[i][j][0]+L[i][j][1]-1)
print(ans)
### BUGGY CODE ###

from collections import deque

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

sum_even = sum(A[::2])
sum_odd = sum(A[1::2]) + A[0]
ANS = A[:]
A = deque(A)
minus = False
for _ in range(n - 1):
    A.rotate(-1)
    for i in range(n):
        if minus:
            ANS[i] -= A[i]
        else:
            ANS[i] += A[i]
    minus = not minus
ANS = deque(ANS)
ANS.rotate()
print(*ANS)


### FIXED CODE ###

from collections import deque

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

B = [0] * n
B[0] = A[0]
B[1] = A[1]
for i in range(2, n):
    B[i] = B[i - 2] + A[i]

ANS = [0] * n
for i in range(n):
    ans = 0
    if i % 2 == 0:
        ans += B[-1] - B[-2]
    else:
        ans += B[-2] - B[-1]

    if i - 2 >= 0:
        ans -= B[i - 2] * 2

    if i - 1 >= 0:
        ans += B[i - 1] * 2

    ANS[i] = ans

print(*ANS)
### BUGGY CODE ###

n, t = map(int, input().split())
ab = sorted([ list(map(int, input().split())) for _ in range(n)])
A, B = zip(*ab)
dp = [[0]*(t+1) for _ in range(n+1)]
for i in range(n):
  for j in range(t+1):
    if A[i] >= j:
      dp[i+1][j] = dp[i][j]
    else:
      dp[i+1][j] = max(dp[i][j-A[i]] + B[i], dp[i][j])
maxB = [B[-1]]*n
for i in range(n-2, 0, -1):
  maxB[i] = max(B[i], maxB[i+1])
ans = 0
for i in range(n-1):
  ans = max(ans, dp[i+1][t] + maxB[i+1])
print(ans)

### FIXED CODE ###

n, t = map(int, input().split())
ab = sorted([ list(map(int, input().split())) for _ in range(n)])
A, B = zip(*ab)
dp = [[0]*(t+1) for _ in range(n+1)]
for i in range(n):
  for j in range(t+1):
    if A[i] >= j:
      dp[i+1][j] = dp[i][j]
    else:
      dp[i+1][j] = max(dp[i][j-A[i]] + B[i], dp[i][j])
maxB = [B[-1]]*n
for i in range(n-2, 0, -1):
  maxB[i] = max(B[i], maxB[i+1])
ans = 0
for i in range(n-1):
  ans = max(ans, dp[i+1][t] + maxB[i+1])
print(ans)
### BUGGY CODE ###

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

passengers = sorted([int(input()) for i in range(N)])
res = {}
key = False
for p in passengers:
    #    if len(res):
    #        res[p] = 1
    for k, val in res.items():
        if k <= p and p <= k + K and val <= C - 1:
            res[k] += 1
            key = True
            break
    if not key:
        res[p] = 1
    else:
        key = False
print(len(res))

### FIXED CODE ###

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

passengers = sorted([int(input()) for i in range(N)])
res = 0
bus_time = passengers[0]
bus_count = C
for p in passengers:
    if bus_count == 0 or p - bus_time > K:
        res += 1
        bus_time = p
        bus_count = C - 1
    else:
        bus_count -= 1
if bus_count != C:
    res += 1
print(res)
### BUGGY CODE ###

N = int(input())
Alst = list(map(int, input().split()))
Blst = [0]*(N+1)
num = 0
for i in range(1, N+1):
    tmp = Alst.count(i)
    Blst[i] = tmp
    num = num + tmp*(tmp-1)//2

for i in range(N):
    k = Blst[Alst[i]] -1
    print(num - k)

### FIXED CODE ###

N = int(input())
Alst = list(map(int, input().split()))
Blst = [0]*(N+1)
num = 0
for i in Alst:
    num = num + Blst[i]
    Blst[i] += 1

for i in Alst:
    k = Blst[i] -1
    print(num - k)
### BUGGY CODE ###


n,m=map(int,input().split())
d=[[] for i in range(n)]
l=[]
g=[]
for i in range(m):
    a,b=map(int,input().split())
    d[a-1].append(b)
    l.append(a)
    g.append(b)
x=[{} for i in range(n)]
for i in range(n):
    for j in range(len(d[i])):
        ds=sorted(d[i])
        x[i][ds[j]]=j
for i in range(m):
    b=x[l[i]-1][g[i]]
    b+=1
    p=len(list(str(l[i])))
    q=len(list(str(b)))
    ans=''
    for j in range(6-p):
        ans+='0'
    ans+=str(l[i])
    for j in range(6-q):
        ans+='0'
    ans+=str(b)
    print(ans)


### FIXED CODE ###

n,m=map(int,input().split())
l=[]
for i in range(m):
    a,b=map(int,input().split())
    l.append([a,b])
x=sorted(l)
dic={}
x.append([0,0])
f=1
for i in range(m):
    if x[i][0]==x[i+1][0]:
        dic[str(x[i][0])+'000000'+str(x[i][1])]=f
        f+=1
    else:
        dic[str(x[i][0])+'000000'+str(x[i][1])]=f
        f=1
for i in range(m):
    b=dic[str(l[i][0])+'000000'+str(l[i][1])]
    p=len(list(str(l[i][0])))
    q=len(list(str(b)))
    ans=''
    for j in range(6-p):
        ans+='0'
    ans+=str(l[i][0])
    for j in range(6-q):
        ans+='0'
    ans+=str(b)
    print(ans)
### BUGGY CODE ###

import sys
s = sys.stdin.readlines()
N, K = map(int, s[0].split())
A = list(map(int, s[1].split()))
A.insert(0,0)
tmp = 1
for i in range(K):
    now = tmp
    next_town = A[tmp]
#    print(str(now) + "→" + str(next_town))
    tmp = next_town
print(next_town)

### FIXED CODE ###

N, K = map(int, input().split())
A = list(map(int,input().split()))
b = [0]*N
next_town = 1
for i in range(N+1):
    if b[next_town-1] != 0:
        start = next_town
        cycle = i - b[next_town-1]
#        print("start: "+str(start))
#        print("cycle: "+str(cycle))
        break
    b[next_town-1] = i
    next_town = A[next_town-1]
    
next_town = 1
if b[start-1] >= K:
    for i in range(K):
        next_town = A[next_town-1]
    print(next_town)
else:
    next_town = start
    for i in range((K-b[start-1])%cycle):
        next_town = A[next_town-1]
    print(next_town)
### BUGGY CODE ###

N, W = map(int, input().split())

w = [0] * N
v = [0] * N
for i in range(N):
    w[i], v[i] = map(int, input().split())

dp = [0] * (W+1)
for i in range(N):
    for j in range(W, w[i]-1, -1):
        a = dp[j-w[i]] + v[i]
        if dp[j] < a:
            dp[j] = a

print(dp[W])

### FIXED CODE ###

N, W = map(int, input().split())

dp = [0] * (W+1)
for i in range(N):
    w, v = map(int, input().split())
    for j in range(W, w-1, -1):
        a = dp[j-w]+v
        if dp[j] < a:
            dp[j] = a

print(dp[W])
### BUGGY CODE ###

def calc_length(s: str, l1: int, l2: int, n: int) -> int:
  max_len = min([l2 - l1, n - l2])
  for i in range(1, max_len):
    if s[l1 + i] != s[l2 + i]:
      return i
  return max_len

n = int(input())
s = input()

longest = 0
for l1 in range(n - 1):
  for l2 in range(l1 + 1, n):
    if s[l1] == s[l2]:
      length = calc_length(s, l1, l2, n)
      if length > longest:
        longest = length

print(longest)

### FIXED CODE ###

n = int(input())
s = input()

l1 = l2 = length = 0

while l2 + length < n:
  if s[l1 : l2] in s[l2:]:
    length = l2 - l1
    l2 += 1
  else:
    l1 += 1
    l2 = l1 + length + 1

print(length)
### BUGGY CODE ###

n, k = map(int, input().split())
p = [(x+1)/2 for x in map(int, input().split())]
m = 0
for i in range(n-k+1):
    m = max(m, sum(p[i:i+k]))
print(m)

### FIXED CODE ###

n, k = map(int, input().split())
p = [(x+1)/2 for x in map(int, input().split())]
o = sum(p[:k])
m = o
for i in range(n-k):
    o = o-p[i]+p[i+k]
    m = max(m, o)
print(m)
### BUGGY CODE ###

a = int(input())
i = 1
q = 1
for a in range(1,a+1):
 i = i*q
 a = a+1
 q = q+1
w = i%(10**9+7)
print(w)

### FIXED CODE ###

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

n = int(input())

u = [0] * n
v = [0] * n
w = [0] * n

color = [-1] * n
dist = [-1] * n
adj_list = [[] for _ in range(n)]

for i in range(n - 1):
    u, v, w = map(int, input().split())
    u -= 1
    v -= 1

    adj_list[u].append([v, w])
    adj_list[v].append([u, w])

q = []
dist[0] = 0
color[0] = 0
q.append(0)

while len(q) > 0:
    node = q.pop(0)

    for next, d in adj_list[node]:
        if dist[next] > 0:
            continue

        if dist[next] == -1 or dist[next] > dist[node] + d:
            dist[next] = dist[node] + d

        q.append(next)

for i in range(n):
    if dist[i] % 2 == 0:
        dist[i] = 0
    else:
        dist[i] = 1
    print(dist[i])


### FIXED CODE ###

from collections import deque

n = int(input())

u = [0] * n
v = [0] * n
w = [0] * n

dist = [-1] * n
adj_list = [[] for _ in range(n)]

for i in range(n - 1):
    u, v, w = map(int, input().split())
    u -= 1
    v -= 1

    adj_list[u].append([v, w])
    adj_list[v].append([u, w])

q = deque()
dist[0] = 0
q.append(0)

while len(q) > 0:
    node = q.popleft()

    for next, d in adj_list[node]:
        if dist[next] > 0:
            continue

        if dist[next] == -1 or dist[next] > dist[node] + d:
            dist[next] = dist[node] + d
            q.append(next)

for i in range(n):
    if dist[i] % 2 == 0:
        dist[i] = 0
    else:
        dist[i] = 1
    print(dist[i])
### BUGGY CODE ###

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

if 0 in A:
    print(0)
    exit()

r = 1
for a in A:
    r *= a

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

### FIXED CODE ###

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

if 0 in A:
    print(0)
    exit()

r = 1
for a in A:
    r *= a

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

print(r)
### BUGGY CODE ###

from collections import deque
N, M = map(int, input().split())
adj = [[float("inf") for i in range(N)] for j in range(N)]
signs = [-1 for i in range(N)]
non_patrolled = set(range(1, N))
signs[0] = 1

for _ in range(M):
  x,y = map(int,input().split())
  adj[x - 1][y - 1] = 1
  adj[y - 1][x - 1] = 1

queue = deque([0])
dist = 0

while len(queue) > 0:
  cur = queue.popleft()
  used = set()
  for i in non_patrolled:
    c = adj[cur][i]
    if c == 1:
      if signs[i] == -1:
        queue.append(i)
        signs[i] = cur
        used.add(i)
  non_patrolled = non_patrolled - used

if all([sign != -1 for sign in signs]):
  print("Yes")
  for sign in signs[1:]:
    print(sign + 1)
else:
  print("No")

### FIXED CODE ###

from collections import deque
N, M = map(int, input().split())

adj = [[] for i in range(N)]
signs = [-1 for i in range(N)]
# not_patrolled = set(range(1, N))

for _ in range(M):
  x,y = map(int,input().split())
  adj[x - 1].append(y - 1)
  adj[y - 1].append(x - 1)

queue = deque([0])

while len(queue) > 0:
  cur = queue.popleft()
  for i in adj[cur]:
    if signs[i] == -1:
      queue.append(i)
      signs[i] = cur
      # not_patrolled.remove(i)

if all([sign != -1 for sign in signs[1:]]):
  print("Yes")
  for sign in signs[1:]:
    print(sign + 1)
else:
  print("No")
### BUGGY CODE ###

def my_gcd(x, y):
    if x >= y:
        m = x
        n = y
    else:
        m = y
        n = x
    r = m % n
    while r:
        m = n
        n = r
        r = m % n
    return n

def _is_prime(n):
    for i in range(n - 1):
        if (i + 1) ** (n - 1) % n != 1:
            return False
    return True

a, b = map(int, input().split())
g = my_gcd(a, b)
count = 1
for i in range(2, g + 1):
    if g % i == 0 and _is_prime(i):
        count += 1
print(count)

### FIXED CODE ###

def prime_decomposition(n):
    i = 2
    result = []
    while i ** 2 <= n:
        while not n % i:
            result.append(i)
            n //= i
        i += 1
    if n > 1:
        result.append(n)
    return result

a, b = map(int, input().split())
s = set(prime_decomposition(a))
t = set(prime_decomposition(b))
print(len(s & t) + 1)
### BUGGY CODE ###

K, S = map(int, input().split())

li = []
for x in range(K+1):
    for y in range(K+1):
        if S-x-y >= 0 and S-x-y <= K:
            li.append([x, y, S-x-y])
print(len(li))

### FIXED CODE ###

K, S = map(int, input().split())

cnt = 0
for x in range(K+1):
    for y in range(K+1):
        if S-x-y >= 0 and S-x-y <= K:
            cnt += 1
print(cnt)
### BUGGY CODE ###

N, M = map(int, input().split())
lista = []
for m in range(M):
    am = int(input())
    lista. append(am)
listans = [0]*N 
an = 0
an1 = 1 
for n in range(N):
    if n+1 in lista:
        an, an1 = an1, 0
    else:
        an, an1 = an1, an+an1
print(an1%1000000007)        


### FIXED CODE ###

N, M = map(int, input().split())
lista = []
for m in range(M):
    am = int(input())
    lista.append(am)
lista.append(0)    
an = 0
an1 = 1 
for n in range(N):
    if n+1 == lista[0]:
        del lista[0]
        #print(lista)
        an, an1 = an1, 0
    else:
        an, an1 = an1, (an+an1)%1000000007
print(an1)