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

N, M = list(map(int, input().split()))
tmp=0

if N==1:
  print(M)
  tmp=1
else:
  for i in range(M-N):
    k = i + N
    if M % k == 0:
      print(int(M/k))
      tmp=1
      break

if tmp==0:
  print(1)

### FIXED CODE ###

N, M = list(map(int, input().split()))
tmp=0

if N==1:
  print(M)
  tmp=1
else:
  for i in range(int(M**0.8)+1):
    k = i + N
    if M % k == 0:
      print(int(M/k))
      tmp=1
      break

if tmp==0:
  print(1)
### BUGGY CODE ###

(N,K) = map(int,input().split())
A = list(map(int,input().split()))
route = [1]
past = 1
for i in range(K):
    past = A[past-1]
    if past in route:
        loop = (route.index(past),i+1)
        flag = 0
        break
    else:
        flag = 1
        route.append(past)
if flag == 1:
    print(route[-1])
else:
    print(route[loop[0]+(K-loop[0])%(loop[1]-loop[0])])


### FIXED CODE ###

(N,K) = map(int,input().split())
A = list(map(int,input().split()))
route = [1]
App = [0]*N
past = 1
for i in range(K):
    past = A[past-1]
    if App[past-1]==1:
        loop = (route.index(past),i+1)
        flag = 0
        break
    else:
        App[past-1] = 1
        flag = 1
        route.append(past)
if flag == 1:
    print(route[-1])
else:
    print(route[loop[0]+(K-loop[0])%(loop[1]-loop[0])])
### BUGGY CODE ###

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

sum_div = 0
for i in range(N):
  temp_div = A[i]
  while True:
    if temp_div%2 == 0:
      sum_div += 1
      temp_div = A[i]//2
    else:
      break
print(sum_div)

### FIXED CODE ###

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

sum_div = 0
for i in range(N):
  temp_div = A[i]
  while True:
    if temp_div%2 == 0:
      sum_div += 1
      temp_div = temp_div//2
    else:
      break
print(sum_div)
### BUGGY CODE ###

import sys
#from collections import defaultdict, deque, Counter
#import bisect
#import heapq
#import math
#from itertools import accumulate
#from itertools import permutations as perm
#from itertools import combinations as comb
#from itertools import combinations_with_replacement as combr
#from fractions import gcd
#import numpy as np

stdin = sys.stdin
sys.setrecursionlimit(10 ** 7)
MIN = -10 ** 9
MOD = 10 ** 9 + 7
INF = float("inf")
IINF = 10 ** 18

def main():
    n = int(stdin.readline().rstrip())
    #A, B = map(float, stdin.readline().rstrip().split())
    A = list(map(int, stdin.readline().rstrip().split()))
    #numbers = [[int(c) for c in l.strip().split()] for l in sys.stdin]
    #word = [stdin.readline().rstrip() for _ in range(n)]
    #number = [[int(c) for c in stdin.readline().rstrip()] for _ in range(n)]
    #zeros = [[0] * w for i in range(h)]
    import functools
    import operator
    result = functools.reduce(operator.mul, A)
    if result > 10**18:
        print(-1)
    else:
        print(result)


main()


### FIXED CODE ###

import sys

stdin = sys.stdin

def main():
    n = int(stdin.readline().rstrip())
    A = list(map(int, stdin.readline().rstrip().split()))
    A.sort()
    ans = 1
    for i in range(n):
        if ans > 10**18:
            if A[0] == 0:
                print(0)
                exit()
            print(-1)
            exit()
        ans *= A[-i]
    print(ans if ans <= 10**18 else -1)


main()
### BUGGY CODE ###

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

ans = 0
for i in range(n-1):
    for j in range(i+1, n):
        temp = 0
        for k in range(j - i):
            if j + k >= n:
                break
            if s[i+k] == s[j+k]:
                temp += 1
            else:
                break
        ans = max(temp, ans)

print(ans)


### FIXED CODE ###

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

def z_algorithm(str):
    len_str = len(str)
    p = [0] * len_str
    j = 0
    for i in range(1, len_str):
        if i + p[i-j] < j + p[j]:
            p[i] = p[i-j]
        else:
            k = max(0, j+p[j]-i)
            while i + k < len_str and str[k] == str[i+k]:
                k += 1
            p[i] = k
            j = i
    p[0] = len_str
    return p

ans = 0
for x in range(n):
    temp = [] + z_algorithm(s[x:])
    for y in range(n - x):
        z = min(temp[y], y)
        ans = max(ans, z)

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


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

ans = 1
for i in l:
    ans *= i

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


### FIXED CODE ###


n = int(input())
l = list(map(int,input().split()))
l = sorted(l)

ans = 1
for i in l:
    ans *= i
    if ans > 10**18:
        print(-1)
        break
else:
    print(ans)
### BUGGY CODE ###

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

def solve_knapsack(capacity):
    # basic checks
 
    
    # populate the capacity = 0 columns, with '0' capacity we have '0' profit
    dp = [0]*(W + 1)
    

    for i in range(0, N):
        weights,profits = map(int,input().split())
        for c in range(capacity, weights-1, -1):
            dp[c] = profits + dp[c - weights] if profits + dp[c - weights] > dp[c] else dp[c]
 
    # maximum profit will be at the bottom-right corner.
    return dp[capacity]
  
def main():
    
 
    res = solve_knapsack(W)
 
    print(res)
if __name__ == "__main__":
	main()

### FIXED CODE ###

def main():
  n, w = [int(e) for e in input().split()]
  t = [-1 for i in range(w + 1)]
  t[w] = 0
  for _ in range(n):
    nw, nv = [int(e) for e in input().split()]
    for i in range(nw, w + 1):
      if t[i] == -1:
        continue
      if t[i - nw] < t[i] + nv:
        t[i - nw] = t[i] + nv
  print(max(t))
main()
### BUGGY CODE ###

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

l=[]
la=[]
i=0
c=0
while True:
    if S[i]=="o":
        l.append(i)
        i+=C
        c+=1
    i+=1
    if i>=N:
        break

if c>K:
    exit()

i=N-1
c=0

while True:
    if S[i]=="o":
        la.append(i)
        i-=C
        c+=1
    i-=1
    if c==K:
        break
    
for i in l:
    if i in la:
        print(i+1)

### FIXED CODE ###

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

l=[0]*N
la=[0]*N
i=0
c=0
while True:
    if S[i]=="o":
        l[i]=1
        i+=C
        c+=1
    i+=1
    if i>=N:
        break

if c>K:
    exit()

i=N-1
c=0

while True:
    if S[i]=="o":
        la[i]=1
        i-=C
        c+=1
    i-=1
    if c==K:
        break
    
for i in range(N):
    if l[i]==1 and la[i]==1:
        print(i+1)
### BUGGY CODE ###

import sys
readline = sys.stdin.readline

def main():

	#s = tuple(input())
	s = input()
	length = len(s)

	dp = [[0]*13 for _ in range(length)]
	MOD = 10**9+7
	if s[-1] == '?':
		for i in range(10):
			dp[0][i] = 1
	else:
		dp[0][int(s[-1])] = 1

	for i in range(1,length):
		if s[-i-1] != '?':
			num = (int(s[-i-1]) * (10**i)) % 13
			for j in range(13):
				dp[i][j] = dp[i-1][(13-num+j)%13]
				dp[i][j] %= MOD
		else:
			num = (10**i) % 13
			a = 0
			for j in range(10):
				for k in range(13):
					dp[i][k] += dp[i-1][(13-a+k)%13]
					dp[i][k] %= MOD
				a += num

	print(dp[-1][5] % MOD)

if __name__ == '__main__':
	main()

### FIXED CODE ###

INF = 10 ** 9 + 7

S = input()
# dp[i][j]はうしろからi桁を13で割った余りがjであるものの個数
dp = [[0] * 13 for _ in range(len(S) + 1)]
dp[0][0] = 1
mul = 1

for i in range(len(S)):
    x = S[-(i + 1)]
    if x == "?":
        for k in range(10):
            for j in range(13):
                dp[i + 1][(mul * k + j) % 13] += dp[i][j]
                dp[i + 1][(mul * k + j) % 13] %= INF
    else:
        k = int(x)
        for j in range(13):
            dp[i + 1][(mul * k + j) % 13] += dp[i][j]
            dp[i + 1][(mul * k + j) % 13] %= INF
    mul = mul * 10 % 13  # 計算量削減のためここで13で割っている

print(dp[len(S)][5])
### BUGGY CODE ###

h,a,*m=open(0)
h,w,k,a,b,f,g=map(int,(h+a).split())
I=h*w
d=[I]*I
m+=d,
a=~w+a*w+b
d[a]=1
q=[a]
for s in q:
 for y,x in(1,0),(-1,0),(0,1),(0,-1):
  for z in range(k):
   i,j=s//w+y*~z,s%w+x*~z;t=i*w+j;p=d[s]+1
   if'.'!=m[i][j]:break
   if d[t]>p:q+=t,;d[t]=p
print(d[~w+f*w+g]%I-1)

### FIXED CODE ###

I=9**9
h,a,*m=open(0)
h,w,k,a,b,f,g=map(int,(h+a).split())
d=[I]*h*w
a=~w+a*w+b
d[a]=1
q=[a]
for s in q:
 for y,x in(1,0),(-1,0),(0,1),(0,-1):
  for z in range(k):
   i,j=s//w+y*~z,s%w+x*~z;t=i*w+j
   if(h>i>-1<j<w)-1or'.'<m[i][j]or d[t]<=d[s]:break
   if d[t]==I:q+=t,;d[t]=d[s]+1
print(d[~w+f*w+g]%I-1)
### BUGGY CODE ###

N,M,Q=map(int,input().split())
import numpy as np
trains=np.zeros((N+1,N+1),dtype=int)
for i in range(M):
  l,r=map(int,input().split())
  trains[l][r]+=1
  
np.cumsum(trains,axis=1,out=trains)
np.cumsum(trains,axis=0,out=trains)

for i in range(Q):
  p,q=map(int,input().split())
  print(trains[q][q]-trains[p-1][q]-trains[q][p-1]+trains[p-1][p-1])


### FIXED CODE ###

N,M,Q=map(int,input().split())
pos=[[0 for i in range(N+1)] for j in range(N+1)]

for i in range(M):
  l,r=map(int,input().split())
  pos[l][r]+=1

for l in range(N+1):
  sums=0
  for r in range(N):
    pos[l][r+1]=pos[l][r]+pos[l][r+1]
    
for r in range(N+1):
  sums=0
  for l in range(N):
    pos[l+1][r]=pos[l][r]+pos[l+1][r]

for i in range(Q):
  p,q=map(int,input().split())
  print(pos[q][q]-pos[p-1][q]-pos[q][p-1]+pos[p-1][p-1])
### BUGGY CODE ###

N = int(input())
sum = 0
for i in range(1, N):
  sum += i

print(sum)

### FIXED CODE ###

N = int(input())
N -= 1
print((N*(N+1))//2)
### BUGGY CODE ###

#!/usr/bin/env python3

n, m = list(map(int, input().split()))
xyz = [list(map(int, input().split())) for i in range(n)]

dp = [[0 for i in range(m+1)] for j in range(n+1)]


# eval
eval_list = ["+xyz[i-1][0]+xyz[i-1][1]+xyz[i-1][2]",
             "+xyz[i-1][0]+xyz[i-1][1]-xyz[i-1][2]",
             "+xyz[i-1][0]-xyz[i-1][1]+xyz[i-1][2]",
             "+xyz[i-1][0]-xyz[i-1][1]-xyz[i-1][2]",
             "-xyz[i-1][0]+xyz[i-1][1]+xyz[i-1][2]",
             "-xyz[i-1][0]+xyz[i-1][1]-xyz[i-1][2]",
             "-xyz[i-1][0]-xyz[i-1][1]+xyz[i-1][2]",
             "-xyz[i-1][0]-xyz[i-1][1]-xyz[i-1][2]", ]

ans = []
for k in range(len(eval_list)):
    for i in range(1, n+1):
        for j in range(1, min(i+1, m+1)):
            tmp = eval(eval_list[k])
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-1] + tmp)

    ans.append(dp[-1][-1])
print(max(ans))


### FIXED CODE ###

#!/usr/bin/env python3
from itertools import product
n, m = list(map(int, input().split()))
xyz = [list(map(int, input().split())) for i in range(n)]

dp = [[0 for i in range(m+1)] for j in range(n+1)]


# eval
# eval_list = ["+xyz[i-1][0]+xyz[i-1][1]+xyz[i-1][2]",
#              "+xyz[i-1][0]+xyz[i-1][1]-xyz[i-1][2]",
#              "+xyz[i-1][0]-xyz[i-1][1]+xyz[i-1][2]",
#              "+xyz[i-1][0]-xyz[i-1][1]-xyz[i-1][2]",
#              "-xyz[i-1][0]+xyz[i-1][1]+xyz[i-1][2]",
#              "-xyz[i-1][0]+xyz[i-1][1]-xyz[i-1][2]",
#              "-xyz[i-1][0]-xyz[i-1][1]+xyz[i-1][2]",
#              "-xyz[i-1][0]-xyz[i-1][1]-xyz[i-1][2]", ]

ans = 0
for a, b, c in product([1, -1], repeat=3):
    total = []
    for x, y, z in xyz:
        s = x*a+y*b+z*c
        total.append(s)
    total.sort(reverse=True)
    ans = max(ans, sum(total[:m]))
print(ans)
### BUGGY CODE ###

N = int(input()) 
A=list(map(int,input().split())) 
i=0 
s=[i for i in range(N)]
sumall=0
for i in range(N):
    s[i]=A.count(i+1)
    sumall=sumall+s[i]
    print(s[i])
    i=i+1
    if sumall>=N-1:
        break
for _ in range(i,N):
    print(0)

### FIXED CODE ###

import collections
n = int(input())
base = map(int,input().split())
c = collections.Counter(base)
for i in range(1,n):
    print(c[i])
print(0)
### BUGGY CODE ###

from collections import defaultdict
import sys

n = int(input())
orders = [[x - 1 for x in list(map(int, input().split()))] for _ in range(n)]

d = defaultdict(list)
e = defaultdict(list)

for i in range(n):
	for j in range(n - 2):
		a1, a2 = min(i, orders[i][j]), max(i, orders[i][j])
		b1, b2 = min(i, orders[i][j + 1]), max(i, orders[i][j + 1])
		d[(a1, a2)].append((b1, b2))
		e[(b1, b2)].append((a1, a2))

visited = [[0 for _ in range(n)] for _ in range(n)]

tpsort = []
def visit(cur):
	a, b = cur
	if visited[a][b] == -1:
		print(-1)
		sys.exit()
	elif visited[a][b] == 0:
		visited[a][b] = -1
		for nxt in e[cur]:
			visit(nxt)
		visited[a][b] = 1
		tpsort.append(cur)

for i in range(n):
	for j in range(i + 1, n):
		if visited[i][j] == 0:
			#print((i, j))
			visit((i, j))
#print(tpsort)

def dfs(a, cnt):
	if len(d[a]) == 0:
		return cnt
	else:
		return max([dfs(x, cnt + 1) for x in d[a]])

i = 0
max_ans = 0
while True:
	if len(e[tpsort[i]]) > 0:
		break
	max_ans = max(max_ans, dfs(tpsort[i], 1))
	i += 1

print(max_ans)

### FIXED CODE ###

from collections import deque

n = int(input())
orders = [deque([x - 1 for x in list(map(int, input().split()))] + [-1]) for _ in range(n)]

nxt = [orders[i].popleft() for i in range(n)]
days = [0 for _ in range(n)]

q = deque([i for i in range(n)])
while q:
	a = q.popleft()
	b = nxt[a]
	if nxt[nxt[a]] == a:
		days[a], days[b] = [max(days[a], days[b]) + 1 for _ in range(2)]
		nxt[a] = orders[a].popleft()
		nxt[b] = orders[b].popleft()
		q.append(a)
		q.append(b)

if sum(nxt) == -n:
	print(max(days))
else:
	print(-1)
### BUGGY CODE ###

S = str(input())
T = str(input())


for i,j in zip(S,T):
    if S.count(i) == T.count(j):
        pass
    else:
        print("No")
        break
else:
    print("Yes")

### FIXED CODE ###

S = str(input())
T = str(input())
S_d = {}
T_d = {}
trans_d = {}
for i,j in zip(S,T):
    if i in S_d and j in T_d:
        if S_d[i] == T_d[j]:
            if trans_d[i] == j:
                pass
            else:
                print("No")
                break            
        else:
            print("No")
            break
    else:
        if i in S_d or j in T_d:
            print("No")
            break
        else:
            if S.count(S) == T.count(T):
                S_d[i] = S.count(S)
                T_d[j] = T.count(T)
                trans_d[i] = j
            else:
                print("No")
                break
        
else:
    print("Yes")
### BUGGY CODE ###

# from line_profiler import LineProfiler
from collections import deque

def main():
    while(True):
        W, H = map(int, input().split())
        # print(W,H)
        if not W: break
        tx,ty = map(int, input().split())
        kx,ky = map(int, input().split())
        ma = [[False]*(W+2) for _ in range(H+2)]
        for i in range(1,H+1):
            for j,a in enumerate(input().split()):
                ma[i][j+1] = bool(1-int(a))
        from pprint import pprint
        que = deque([[tx,ty,kx,ky,0]])
        # pa = [[[[False]*(W+2) for ii in range(H+2)] for jj in range(W+2)] for kk in range(H+2)]
        pas = []
        ans = "NA"
        while(que):
            # if len(que)>10:break
            # pprint(que)
            tx,ty,kx,ky,c = que.popleft()
            # import copy
            # toprint = copy.deepcopy(ma)
            # toprint[ty][tx] = "tt"
            # toprint[ky][kx] = "kk"
            # for i in range(H+2):
            #     print("".join(( toprint[i][j] if toprint[i][j] in ["tt","kk"] else "  ") if toprint[i][j] else "**" for j in range(W+2)))
            if c > 100: break
            if tx == kx and ty == ky:
                ans = c
                break
            for dx,dy in [[-1,0],[0,-1],[1,0],[0,1]]:
                tdx, tdy = [ dx, dy] if ma[ty+dy][tx+dx] else [0,0]
                kdx, kdy = [-dx,-dy] if ma[ky-dy][kx-dx] else [0,0]
                # if pa[tx+tdx][ty+tdy][kx+kdx][ky+kdy]: continue
                if [tx+tdx,ty+tdy,kx+kdx,ky+kdy] in pas: continue
                que.append([tx+tdx,ty+tdy,kx+kdx,ky+kdy,c+1])
                # pa[tx+tdx][ty+tdy][kx+kdx][ky+kdy] = True
                pas.append([tx+tdx,ty+tdy,kx+kdx,ky+kdy])
        print(ans)
        # pprint(ma)

if __name__ == "__main__":
    # prf = LineProfiler()
    # prf.add_function(main)
    # prf.runcall(main)
    # prf.print_stats()
    main()


### FIXED CODE ###

# from line_profiler import LineProfiler
from collections import deque
from sys import stdin

def main():
    while(True):
        W, H = map(int, stdin.readline().split())
        if not W: break
        tx,ty = map(int, stdin.readline().split())
        kx,ky = map(int, stdin.readline().split())
        ma = [[False]+[bool(1-int(a)) for a in stdin.readline().split()]+[False] for i in range(H)]
        ma = [[False]*(W+2)] + ma + [[False]*(W+2)]
        que = deque([[tx,ty,kx,ky,0]])
        pas = set()
        ans = "NA"
        while(que):
            tx,ty,kx,ky,c = que.popleft()
            if tx == kx and ty == ky:
                ans = c
                break
            if c+1 > 100: continue
            for dx,dy in [[-1,0],[0,-1],[1,0],[0,1]]:
                tdx, tdy = ( dx, dy) if ma[ty+dy][tx+dx] else (0,0)
                kdx, kdy = (-dx,-dy) if ma[ky-dy][kx-dx] else (0,0)
                if (tx+tdx,ty+tdy,kx+kdx,ky+kdy) in pas: continue
                que.append([tx+tdx,ty+tdy,kx+kdx,ky+kdy,c+1])
                pas.add((tx+tdx,ty+tdy,kx+kdx,ky+kdy))
        print(ans)

if __name__ == "__main__":
    # prf = LineProfiler()
    # prf.add_function(main)
    # prf.runcall(main)
    # prf.print_stats()
    main()
### BUGGY CODE ###

MOD = 1000000007

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

dp = [[0 for j in range(K+1)] for i in range(N+1)]
dp[0][0] = 1

for i in range(1,N+1):
    cum = [0 for j in range(K+2)]
    cum[0] = 0
    for j in range(1,K+2):
        cum[j] = cum[j-1]+dp[i-1][j-1]
        cum[j] %= MOD
    for j in range(K+1):
        dp[i][j] = cum[j+1]-cum[max(0,j-A[i-1])]
        dp[i][j] %= MOD

print(dp[N][K])

### FIXED CODE ###

MOD = 1000000007

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

dp = [[0 for j in range(K+1)] for i in range(N+1)]
dp[0][0] = 1

for i in range(1,N+1):
    cum = [0 for j in range(K+2)]
    cum[0] = 0
    for j in range(1,K+2):
        cum[j] = cum[j-1]+dp[i-1][j-1]
        cum[j] %= MOD
    for j in range(K+1):
        dp[i][j] = cum[j+1]-cum[max(0,j-A[i-1])]
        dp[i][j] %= MOD

print(dp[N][K])
### BUGGY CODE ###

# E - ∙ (Bullet)

from collections import defaultdict

MOD = 1000000007
N = int(input())

# イワシの傾きをA/Bとする。
# A/Bは予めgcdで割って約分し、同じ傾きのものを揃えておく。
# このとき、仲の悪い組合せは(A, B)に対して(B, -A)となるもの。 
# 前者をS、後者をTとして考える。
d_S = defaultdict(int)
d_T = defaultdict(int)

def gcd(x, y):
    if x == 0:
        return y
    else:
        return gcd(y%x, x)

zeros = 0
for i in range(N):
    A, B = map(int, input().split())
    # (0, 0)のイワシは他の全てのイワシと仲が悪いため、
    # 1匹のみでしか選ぶことができない。最後にこの数を足す。
    if A == 0 and B == 0:
        zeros += 1
    # (?, 0),(0, ?)のイワシは、?がどのような数字であろうとも
    # この組合せであれば仲が悪い。一律、(1,0)(0,-1)として考える。
    elif A == 0:
        d_S[(1, 0)] += 0
        d_T[(0, -1)] += 1
    elif B == 0:
        d_S[(1, 0)] += 1
        d_T[(0, -1)] += 0
    else:
        g = gcd(A, B)
        A //= g
        B //= g
        # いずれもマイナスの場合、傾きはプラスになる
        if A < 0 and B < 0:
            A *= -1
            B *= -1
        if A * B > 0:
            d_S[(A, B)] += 1
            d_T[(B, -A)] += 0
        # 片方がマイナスの場合、必ずAがマイナスになるよう揃える
        else:
            if A > B:
                A, B = B, A
            d_S[(-A, B)] += 0
            d_T[(B, A)] += 1

ans = 1
for (si, sj), s_cnt in d_S.items():
    t_cnt = d_T[(sj, -1*si)]
    tmp = 0
    tmp += pow(2, s_cnt, MOD) - 1
    tmp += pow(2, t_cnt, MOD) - 1
    tmp += 1
    ans = (ans * tmp)%MOD

ans -= 1
ans += zeros

print(ans%MOD)

### FIXED CODE ###

# E - ∙ (Bullet)
import sys
from collections import defaultdict

readline = sys.stdin.readline
MOD = 1000000007
N = int(readline())

# イワシの傾きをA/Bとする。
# A/Bは予めgcdで割って約分し、同じ傾きのものを揃えておく。
# このとき、仲の悪い組合せは(A, B)に対して(B, -A)となるもの。 
# 前者をS、後者をTとして考える。
d_S = defaultdict(int)
d_T = defaultdict(int)

def gcd(x, y):
    if x == 0:
        return y
    else:
        return gcd(y%x, x)

zeros = 0
for i in range(N):
    A, B = map(int, readline().split())
    # (0, 0)のイワシは他の全てのイワシと仲が悪いため、
    # 1匹のみでしか選ぶことができない。最後にこの数を足す。
    if A == 0 and B == 0:
        zeros += 1
    # (?, 0),(0, ?)のイワシは、?がどのような数字であろうとも
    # この組合せであれば仲が悪い。一律、(1,0)(0,-1)として考える。
    elif A == 0:
        d_S[(1, 0)] += 0
        d_T[(0, -1)] += 1
    elif B == 0:
        d_S[(1, 0)] += 1
        d_T[(0, -1)] += 0
    else:
        g = gcd(A, B)
        A //= g
        B //= g
        # いずれもマイナスの場合、傾きはプラスになる
        if A < 0 and B < 0:
            A *= -1
            B *= -1
        if A * B > 0:
            d_S[(A, B)] += 1
            d_T[(B, -A)] += 0
        # 片方がマイナスの場合、必ずAがマイナスになるよう揃える
        else:
            if A > B:
                A, B = B, A
            d_S[(-A, B)] += 0
            d_T[(B, A)] += 1

ans = 1
for (si, sj), s_cnt in d_S.items():
    t_cnt = d_T[(sj, -1*si)]
    tmp = 0
    tmp += pow(2, s_cnt, MOD) - 1
    tmp += pow(2, t_cnt, MOD) - 1
    tmp += 1
    ans = (ans * tmp)%MOD

ans -= 1
ans += zeros

print(ans%MOD)
### BUGGY CODE ###

N=int(input())
a_list=[]
for i in range(N):
    a_list.append(int(input()))
 
for i in range(len(a_list)):
    tmp=[x for j,x in enumerate(a_list) if i!=j]
    print(max(tmp))

### FIXED CODE ###

N=int(input())
a_list=[]
for i in range(N):
    a_list.append(int(input()))

tmp=sorted(a_list)[::-1]
one=tmp[0]
two=tmp[1]
for i in range(len(a_list)):
    if a_list[i]==one:
        print(two)
    else:
        print(one)
### BUGGY CODE ###

a,b,k = map(int,input().split())
nums = [i for i in range(a,b+1)]
apply_nums = set()

for i in nums[:k]:
    apply_nums.add(i)
for i in nums[-k:]:
    apply_nums.add(i)

apply_list = list(apply_nums)
apply_list.sort()

for i in apply_list:
    print(i)

### FIXED CODE ###

a, b, k = [int(m) for m in input().split(" ")]

for i in range(a, min(a+k, b+1)):
    print(i)
for i in range(max(b+1-k, a+k), b+1):
    print(i)
### BUGGY CODE ###

from sys import stdin
import math
a, b = [int(x) for x in stdin.readline().rstrip().split()]
nums = [x for x in range(a,b+1)]
li1 = nums[::2]
li2 = list(set(nums)-set(li1))
if len(li1) > len(li2):
    li2.append(0)
elif len(li2) > len(li1):
    li1.appen(0)
from operator import xor
combined2 = list(map(xor, li1, li2))
def constructXOR(A, n):
    XOR = 0
    for i in range(0, n):
        XOR ^= A[i]
    return XOR
result = constructXOR(combined2, len(combined2))
print(result)

### FIXED CODE ###

from sys import exit, stdin

A, B = [int(_) for _ in stdin.readline().rstrip().split()]

def oddsolve(x):
    return int((x+1)/2)%2

def solve(x):
    if x % 2 == 1:
        return oddsolve(x)
    else:
        return oddsolve(x+1) ^ (x+1)

print(solve(B) ^ solve(A-1))
### BUGGY CODE ###

n, k = map(int, input().split())
hL = list(map(int, input().split()))

dp = [10**10]*(n)
dp[0] = 0
for i in range(0,n):
    if i+k<=n-1:
        for j in range(1,k+1):
            dp[i+j] = min(dp[i+j], dp[i]+abs(hL[i+j]-hL[i]))
    else:
        for j in range(1, n-i):
            dp[i+j] = min(dp[i+j], dp[i]+abs(hL[i+j]-hL[i]))

print(dp[n-1])



### FIXED CODE ###

n, k = map(int, input().split())
hL = list(map(int, input().split()))

dp = [10**10]*(n)
dp[0] = 0
for i in range(0,n):
    if i+k<=n-1:
        for j in range(1,k+1):
            dp[i+j] = min(dp[i+j], dp[i]+abs(hL[i+j]-hL[i]))
    else:
        for j in range(1, n-i):
            dp[i+j] = min(dp[i+j], dp[i]+abs(hL[i+j]-hL[i]))

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

from fractions import gcd

def lcm(x, y):
    return (x // gcd(x, y)) * y

MOD = 10 ** 9 + 7  
n = int(input())
A = list(map(int, input().split()))

A.sort()

l = 1
for i in A:
  if l % i != 0:
    l = lcm(l, i)

num = [0] * (10 ** 6 + 1)

ans = 0
for i in A:
  if num[i] == 0:
    v = l // i
    num[i] = v
  else:
    v = num[i]
  ans = (ans + v) % MOD

print(ans)


### FIXED CODE ###

from fractions import gcd

def lcm(x, y):
  return (x * y) // gcd(x, y)

MOD = 10 ** 9 + 7  
n = int(input())
A = list(map(int, input().split()))

l = 1
for i in A:
  l = lcm(l, i)
l %= MOD

ans = 0
for i in A:
  ans += l * pow(i, MOD - 2, MOD)
  ans %= MOD
print(ans)