Harryxun/stf_run huggingface dataset:
from collections import deque

MOD = 10 ** 9 + 7
ans = 1

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

if n == k:
    for x in a:
        ans *= x
        ans %= MOD
    print(ans % MOD)
    exit()

p = []
m = []

for x in a:
    if x >= 0:
        p.append(x)
    else:
        m.append(x)

p.sort(reverse=True)
m.sort()

pos = deque(p)
neg = deque(m)

if len(p) == 0:
    for i in range(k):
        ans *= neg[-1]
        neg.pop()
        ans %= MOD
    print(ans % MOD)
    exit()

if k % 2:
    ans *= pos.popleft()
    k -= 1

while k > 0:
    if len(pos) >= 2:
        sp = pos[0] * pos[1]
    else:
        sp = 0
    
    if len(neg) >= 2:
        sn = neg[0] * neg[1]
    else:
        sn = 0
    
    if sp > sn:
        ans *= sp
        pos.popleft()
        pos.popleft()
    else:
        ans *= sn
        neg.popleft()
        neg.popleft()
    
    ans %= MOD
    k -= 2

print(ans % MOD)


### FIXED CODE ###

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

MOD = 10 ** 9 + 7
ans = 1

#全部取る
if n == k:
    for x in a:
        ans *= x
        ans %= MOD
    print(ans % MOD)

#全部負かつ奇数個取る
elif max(a) < 0 and k % 2:
    a.sort()
    for i in range(1, k+1):
        ans *= a[-i]
        ans %= MOD
    print(ans % MOD)

else:
    pos = []
    neg = []
    
    for x in a:
        if x >= 0:
            pos.append(x)
        else:
            neg.append(x)
    
    pos.sort(reverse=True)
    neg.sort()
    
    
    if k % 2:
        ans *= pos.pop(0)
        k -= 1
     
    #2個ずつ取る
    num = []
    for x, y in zip(pos[::2], pos[1::2]):
        num.append(x * y)
    for x, y in zip(neg[::2], neg[1::2]):
        num.append(x * y)

    num.sort(reverse=True)

    for i in range(k // 2):
        ans *= num[i]
        ans %= MOD
    
    print(ans % MOD)
import itertools

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

ab_list = []

for _ in range(0, m):
    a, b = list(map(int, input().split()))
    ab_list.append((a, b))
    ab_list.append((b, a))

# 全探索で解く場合
l = range(1, n+1)
count = 0
roots = [v for v in itertools.permutations(l, n) if v[0] == 1]

for v in roots:
    is_ok = True
    for i, _ in enumerate(list(v)[:-1]):
        # 探索対象となるエッジ
        target_edge = (list(v)[i], list(v)[i+1])
        if (target_edge not in ab_list):
            is_ok = False

    if is_ok:
        count += 1

print(count)


### FIXED CODE ###

# https://atcoder.jp/contests/abc054/tasks/abc054_a
# A - One Card Poker
a, b = list(map(int, input().split()))

if a == 1:
    a = 100
if b == 1:
    b = 100

if a == b:
    answer = 'Draw'
elif a < b:
    answer = 'Bob'
elif a > b:
    answer = 'Alice'

print(answer)
a,b,c = map(int,input().split())
print(rount(0.5*a*b))

### FIXED CODE ###

a,b,c = map(int,input().split())
print(round(0.5*a*b))
a,b=map(int,input().split());s=input();print(['No','Yes'][s[a]=='-'and s.count('-')>0])

### FIXED CODE ###

print(48-int(input()))
s=input().relpace("hi","")
if len(s)==0:
    print("Yes")
else:
    print("No")


### FIXED CODE ###

s=input().replace("hi","")
if len(s)==0:
    print("Yes")
else:
    print("No")
n=int(input())
a_list=[int(i) for i in input().split(' ')]

c = collections.Counter(a_list)
[print(c[i+1]) for i in range(n)]

### FIXED CODE ###

n=int(input())
a_list=[int(i) for i in input().split(' ')]

import collections

c = collections.Counter(a_list)
[print(c[i+1]) for i in range(n)]
N,K=map(int,input().split())
td=[[int a for a in input().split()]for i in range(N)]

td=sorted(td,key=lambda x:-x[1])

ans=0
eat=[]
noteat=[]
for t,d in td[:K]:
  ans+=d
  if t not in eat:
    eat.append(t)
  else:
    noteat.append(d)
temp_result=ans+sum(eat)**2
max_result=temp_result

for t,d in td[K:]:
  if not noteat:
    break
  if t not in eat:
    temp_result+=2*len(eat)+1
    temp_result+=d-noteat.pop()
    eat.add(t)
    max_result=max(max_result,temp_result)
print(max_result)
 

### FIXED CODE ###

N,K=map(int,input().split())
td=[[int(a) for a in input().split()]for i in range(N)]

td=sorted(td,key=lambda x:-x[1])

ans=0
eat=set([])
noteat=[]
for t,d in td[:K]:
  ans+=d
  if t not in eat:
    eat.add(t)
  else:
    noteat.append(d)
temp_result=ans+len(eat)**2
max_result=temp_result

for t,d in td[K:]:
  if not noteat:
    break
  if t not in eat:
    temp_result+=2*len(eat)+1
    temp_result+=d-noteat.pop()
    eat.add(t)
    max_result=max(max_result,temp_result)
print(max_result)
while 1:
    N = int(input())
    if N == 0:
        break
   print(0)


### FIXED CODE ###

import math
while 1:
    N = int(input())
    if N == 0:
        break
    xs = list(map(int, input().split()))
    avg = 0
    for x in xs:
        avg += x
    avg /= len(xs)
    var = 0
    for x in xs:
        var += (x - avg) ** 2
    var /= len(xs)
    print(math.sqrt(var))
#再帰回数が多すぎてエラー

S = list(input()) + ['D']*100
N = len(S)-10

# print (S)
# print (N)

memo = [-1] * (N+100) 

# print (memo)

def check(k):
    if memo[k] != -1:
        return memo[k]
    if S[k+1] == 'B' and S[k+2] == 'C':
        memo[k] = check(k+2) + 1
        return memo[k]
    if S[k+1] == 'A':
        memo[k] = check(k+1)
        return memo[k]
    memo[k] = 0
    return memo[k]

ans = 0
for i in range(N):
    if S[i] =='A':
        ans += check(i)
print (ans)


### FIXED CODE ###

#再帰回数が多すぎてエラー
import sys

sys.setrecursionlimit(210000)
S = list(input()) + ['D']*100
N = len(S)-10

# print (S)
# print (N)

memo = [-1] * (N+100) 

# print (memo)

def check(k):
    if memo[k] != -1:
        return memo[k]
    if S[k+1] == 'B' and S[k+2] == 'C':
        memo[k] = check(k+2) + 1
        return memo[k]
    if S[k+1] == 'A':
        memo[k] = check(k+1)
        return memo[k]
    memo[k] = 0
    return memo[k]

ans = 0
for i in range(N):
    if S[i] =='A':
        ans += check(i)
print (ans)
N, X = map(int, input().split())
l = list(map(int, input().split()))
m=[]
from functools import reduce
from math import gcd
for i in l:
    m.append(abs(i-N))
print(reduce(gcd,m))

### FIXED CODE ###

from functools import reduce
from fractions import gcd
N,X=map(int,input().split())
x=[abs(X-int(i)) for i in input().split()]
print(reduce(gcd,x))
from collections import defaultdict


def resolve():
    n = int(input())
    v = list(map(int, input().split()))
    d_o = defaultdict(int)
    d_e = defaultdict(int)
    for i in range(n):
        if i % 2:
            d_o[v[i]] += 1
        else:
            d_e[v[i]] += 1
    de = sorted(d_e.items(), key=lambda x: x[1])
    do = sorted(d_o.items(), key=lambda x: x[1])
    if de == do:
        p = max(de[0][1], do[0][1])
        print(n - p)
    if de[0] != do[0]:
        print(n - de[0][1] - do[0][1])
    else:
        p = max(de[0][1] + do[1][1], de[1][1] + do[0][1])
        print(p)


if __name__ == "__main__":
    resolve()


### FIXED CODE ###

from collections import defaultdict


def resolve():
    n = int(input())
    v = list(map(int, input().split()))
    d_o = defaultdict(int)
    d_e = defaultdict(int)
    for i in range(n):
        if i % 2:
            d_o[v[i]] += 1
        else:
            d_e[v[i]] += 1
    d_e[0] = 0
    d_o[0] = 0
    de = sorted(d_e.items(), key=lambda x: -x[1])
    do = sorted(d_o.items(), key=lambda x: -x[1])
    if de[0][0] != do[0][0]:
        print(n - de[0][1] - do[0][1])
    else:
        p01 = de[0][1] + do[1][1]
        p10 = de[1][1] + do[0][1]
        print(n - max(p01, p10))


if __name__ == "__main__":
    resolve()
a,b=map(int,input().split())
if(a=1 or b=1):
  print(1)
else:
  print(int((a*b)/2)+(a*b)%2)

### FIXED CODE ###

a,b=map(int,input().split())
if(a==1 or b==1):
  print(1)
else:
  print(int((a*b)/2)+(a*b)%2)
from math import log
from math import ceil
n,k=map(int,input().split())
ans=0
for i in range(n):
  a=ceil(k/i)
  x=ceil(log(a,2))
  ans+=0.5**x
print(ans/n)

### FIXED CODE ###

from math import log
from math import ceil
n,k=map(int,input().split())
ans=0
for i in range(1,n+1):
  a=ceil(k/i)
  x=ceil(log(a,2))
  ans+=0.5**x
print(ans/n)
import math

def lcm(lst):
    if len(lst) == 2:
        return (lst[0] * lst[1]) // math.gcd(lst[0], lst[1])
    l = lcm(lst[1:])
    return (lst[0] * l) // math.gcd(lst[0], l)

n = int(input())
inputs = list(map(int, input().split(' ')))
x = lcm(inputs) - 1
s = 0
for i in inputs:
    s += x % i
print(s)


### FIXED CODE ###

import fractions

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

n = int(input())
inputs = list(map(int, input().split(' ')))
for i in range(len(inputs)):
    if i == 0:
        x = lcm(inputs[0], inputs[1])
        continue
    if i == 1:
        continue
    x = lcm(x, inputs[i])
x -= 1
s = 0
for i in inputs:
    s += x % i
print(s)
# -*- coding: utf-8 -*-
N = int(input())
A,B = map(int,input().split())
train = N*A
cab = B
result = train - cab

if result >= 0:
    print(cab)
else:
    print(train)

### FIXED CODE ###

# -*- coding: utf-8 -*-
N,A,B = map(int,input().split())
train = N*A
taxi = B
result = train - taxi

if result >= 0:
    print(taxi)
else:
    print(train)
#! /usr/bin/python
# -*- coding: utf-8 -*-

while 1:
    ans = 0
    (w, h) = map(int, raw_input().split())
    used = [[False]*w for i in range(h)]
    if h == 0:break
    que = [[0, 0, 1]]
    vir = []
    hor = []
    for i in range(h):
        vir.append(map(int, raw_input().split()))
        if i == h-1:break
        hor.append(map(int, raw_input().split()))
    while que!=[]:
        y = que[0][0]
        x = que[0][1]
        cost = que[0][2]
        used[y][x] = True
        que.pop(0)
        if y==h-1 and x==w-1:
            ans = cost
            break
        if x+1 < w and used[y][x+1] == False and vir[y][x] == 0:
            que.append([y, x+1, cost+1])
        if x-1 >= 0 and used[y][x-1] == False and vir[y][x-1] == 0:
            que.append([y, x-1, cost+1])
        if y+1 < h and used[y+1][x] == False and hor[y][x] == 0:
            que.append([y+1, x, cost+1])
        if y-1 >= 0 and used[y-1][x] == False and hor[y-1][x] == 0:
            que.append([y-1, x, cost+1])
    print ans
    

### FIXED CODE ###

#! /usr/bin/python
# -*- coding: utf-8 -*-

while 1:
    ans = 0
    (w, h) = map(int, raw_input().split())
    used = [[False]*w for i in range(h)]
    if h == 0:break
    que = [[0, 0, 1]]
    used[0][0] = True
    vir = []
    hor = []
    for i in range(h):
        vir.append(map(int, raw_input().split()))
        if i == h-1:break
        hor.append(map(int, raw_input().split()))
    while que!=[]:
        y = que[0][0]
        x = que[0][1]
        cost = que[0][2]
        que.pop(0)
        if y==h-1 and x==w-1:
            ans = cost
            break
        if x+1 < w and used[y][x+1] == False and vir[y][x] == 0:
            que.append([y, x+1, cost+1])
            used[y][x+1] = True
        if x-1 >= 0 and used[y][x-1] == False and vir[y][x-1] == 0:
            que.append([y, x-1, cost+1])
            used[y][x-1] = True
        if y+1 < h and used[y+1][x] == False and hor[y][x] == 0:
            que.append([y+1, x, cost+1])
            used[y+1][x] = True
        if y-1 >= 0 and used[y-1][x] == False and hor[y-1][x] == 0:
            que.append([y-1, x, cost+1])
            used[y-1][x] = True
    print ans
h,w = [int(_) for _ in input().split()]
board = [ list(input())  for _ in range(h)]

goodx = [False] * w
goody = [False] * h

for i in range(w):
  for j in range(h):
    if board[i][j] == '#':
      goodx[i] = True
      goody[j] = True

for i in range(w):
  if goodx[i]:
    for j in range(h):
      if goody[j]:
        print(board[i][j], end='')
    print("")

### FIXED CODE ###

h,w = [int(_) for _ in input().split()]
board = [ list(input())  for _ in range(h)]

goodx = [False] * h
goody = [False] * w

for i in range(h):
  for j in range(w):
#    print("i={}\tj={}\tboard={}".format(i,j,board[i][j]))
    if board[i][j] == '#':
      goodx[i] = True
      goody[j] = True

for i in range(h):
  if goodx[i]:
    for j in range(w):
      if goody[j]:
        print(board[i][j], end='')
    print("")
a,b,c=map(int,input().split())
if (a==b!=c) or (a!=b==c) or (a==c!=b):
    print("Yes")
else:
    prnit("No")


### FIXED CODE ###

a,b,c=map(int,input().split())
if (a==b!=c) or (a!=b==c) or (a==c!=b):
    print("Yes")
else:
    print("No")
H,W,D=map(int,input().split());S=H*W;A=[map(int,input().split())for _ in range(H)];Q,*L=open(0);d=[0]*S;e=[0]*S
for i,l in enumerate(A):
 for j,v in enumerate(l):d[v-1]=(i,j)
for i in range(S):
 if i>=D:e[i]=sum(abs(p-q)for p,q in zip(d[i-D],d[i]))+e[i-D]
for i in L:l,r=map(int,i.split());print(e[r-1]-e[l-1])

### FIXED CODE ###

H, W, D = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]
Q = int(input())
LR = [list(map(int, input().split())) for _ in range(Q)]

dp = [None for _ in range(H*W)]
for i, l in enumerate(A) :
    for j, v in enumerate(l) :
        dp[v-1] = (i, j)

def f(p, q) :
    x, y = dp[p]
    i, j = dp[q]
    return abs(x-i)+abs(y-j)

distance = [0 for _ in range(H*W)]
for i in range(H*W) :
    if i<D :
        pass
    else :
        distance[i] = f(i-D, i) + distance[i-D]

for l, r in LR :
    print(distance[r-1]-distance[l-1])
n,y = map(int,input().split())
ans = (-1,-1,-1)
for i in range(n+1): 
	for j in range(n+1-i):
		if y == 1000*(i + j * 5 + (n+1-i-j) * 10 ): 
			print( n+1-i-j j, i)
			exit()
print(-1,-1,-1)


### FIXED CODE ###

#!/usr/bin/env python3
n,y = map(int,input().split())
ans = (-1,-1,-1)
for i in range(n+1): 
	for j in range(n+1-i):
		if y == 1000*(i + j * 5 + (n-i-j) * 10 ): 
			print( n-i-j, j, i ) # 逆だった。出力は10000から出す
			exit(0)
print(-1,-1,-1)
N,X=map(int,input().split())
l=list(map(int,input().split()))
d=0
cnt=1
while True:
    
    d+=l[cnt-1]
    if d>X:
        print(cnt)
        break
    cnt+=1
    
else:
    
    print(cnt)

### FIXED CODE ###

N,X=map(int,input().split())
l=list(map(int,input().split()))
d=0
cnt=1
while True:
    
    d+=l[cnt-1]
    if d>X:
        print(cnt)
        break
    cnt+=1
    if cnt==N+1:
        print(N+1)
        break
else:
    
    print(cnt)
while True:
	x = raw_input()
	i += 1
	if x == 0:
		break
	print 'Case ' + str(i) + ': ' + str(x)

### FIXED CODE ###

i = 0
while 1:
	foo = raw_input()
	i += 1
	if foo == '0':break
	print 'Case %s: %s'%(i,foo)
t = list(map(int,(input().split())))
a = list(map(int,(input().split())))
b = list(map(int,(input().split())))
A = 0
B = 0
ans = 0
tmp = [[0,0],[0,0]]
for i in range(2):
    a[i] *= t[i]
    b[i] *= t[i]

if a[0] + a[1] == b[0] + b[1]:
    print('infinity')
    exit(0)
elif a[0] > b[0] and a[1] > b[1]:
    print(0)
    exit(0)
elif a[0] < b[0] and a[1] < b[1]:
    print(0)
    exit(0)


for i in range(2):
    for j in range(2):
        A += a[j]
        B += b[j]
        tmp[i][j] = abs(A-B)
#print(tmp)
if tmp[0][0] - tmp[1][0] < 0:
    if not tmp[0][1] % (tmp[0][1] - tmp[1][1]):
        ans += 1
    tmp[0][1] //= tmp[0][1] - tmp[1][1]
    ans = '11145147'
else:
    if not tmp[0][0] % (tmp[0][0] - tmp[1][0]):
        ans -= 1

    tmp[0][0] //= tmp[0][0] - tmp[1][0]
    ans += tmp[0][0] * 2 +1


print(max(ans,1))

### FIXED CODE ###

t1, t2 = map(int,input().split())
a1, a2 = map(int,input().split())
b1, b2 = map(int,input().split())

a1 = t1*a1
a2 = t2*a2
b1 = t1*b1
b2 = t2*b2

if (a1 + a2) == (b1 + b2):
    print('infinity')
    exit(0)

elif (a1 + a2) > (b1 + b2):
    a1, b1 = b1, a1
    a2, b2 = b2, a2
if b1 > a1:
    print(0)
    exit(0)

tmp00 = a1 - b1
tmp01 = b1 + b2 - a1 - a2

ans = tmp00 // tmp01 * 2 + 1
if tmp00 % tmp01 == 0:
    ans -= 1

print(ans)
x=int(input())
a=int(input())

(print(10) if x >= a else print(

### FIXED CODE ###

x,a = map(int,input().split())

(print(10) if x >= a else print(0))
s = input()
t = s[2:-1]
count = 0
q = [t[1]]
for i in range(len(t)):
    if t[i] == "C":
        count += 1
    else:
        q.append(t[i])
q.append(t[-1])
q = ''.join(q)
if s[0] == "A" and count == 1 and str(q).lower ==q:
    print("AC")
else:
    print("WA")
    

### FIXED CODE ###

s = input()
t = s[2:-1]
count = 0
q = [s[1]]
for i in range(len(t)):
    if t[i] == "C":
        count += 1
    else:
        q.append(t[i])
q.append(s[-1])
q =''.join(q)
if s[0] == "A" and count == 1 and str(q).lower() ==str(q):
    print("AC")
else:
    print("WA")
import string
a=string.ascii_lowercase
N=int(input())
ans=[]
count=1
n=26
while N>n:
    count+=1
    s=n
    n+=26**count
if N>26**count:
    for i in range(count):
        n=N//26**(count-i-1)
        if i!=count-1:
            m=N%26**(count-i-1)
        if n>=276:
            ans.append(a[25])
            N-=26**(count-i)
        else:
            ans.append(a[m-1])
else:
    while N>0:
        n=N//26
        m=N%26
        ans.append(a[m-1])
        N=n
Ans=[]
for i in range(len(ans)):
    Ans.append(ans[len(ans)-i-1])
print("".join(Ans))

### FIXED CODE ###

import string
a=string.ascii_lowercase
N=int(input())
ans=[]
count=1
n=26
s=0
while N>n:
    count+=1
    s=n
    n+=26**count
N-=s+1
for i in range(count):
    n=N//26
    m=N%26
    ans.append(a[m])
    N=n
Ans=[]
for i in range(len(ans)):
    Ans.append(ans[len(ans)-i-1])
print("".join(Ans))
_, w, *s = open(0).read().split()
a, b = divmod(s.index("snuke"), int(w))
print("ABCDEFGHIJJ"[b], a+1, sep="")

### FIXED CODE ###

_, w, *s = open(0).read().split()
a, b = divmod(s.index("snuke"), int(w))
print(chr(65+b), a+1, sep="")
N = int(input())
def prime_dict(n):
    a = {}
    if n%2 == 0:
        a[2] = 1
        n//=2
        exp2 = 2
    while n%(2**exp2) == 0 and (n > 2**exp2):
        a[2] += 1
        n //= 2**exp2
        exp2 += 1
    while n%2 == 0:
        n //= 2
    f = 3
    expn = 1
    while f**expn <= n:
        while f**expn <= n:
            if n%(f**expn) == 0:
                if f not in a:
                    a[f] = 1
                else:
                    a[f] += 1
                n //= f**expn
            expn += 1
        while n%f == 0:
            n //= f
        f += 2
        expn = 1
    if n!= 1:
        a[n] = 1
    return a

primes = prime_dict(N)
ans = sum(primes.values())
print(ans)



### FIXED CODE ###

from collections import Counter
N = int(input())
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
ans = 0
primes = prime_factorize(N)
pc = Counter(primes)
for v in pc.values():
    now = 1
    while now*(now+1)//2 <= v:
        now += 1
    ans += now-1
print(ans)
N = int(input())

T = [[] for i in range(N)]
F = [None for i in range(N-1)]
for i,n in enumerate(range(N-1)):
    a,b = map(int,input().split())
    T[a-1].append(b-1)
    F[i] = b-1

# print(T)

R = [None for i in range(N)]
def dfs(cur, mx, color):
    # R[cur] = color
    if color == -1:
        mx = max(len(T[cur]), mx)
    else:
        mx = max(len(T[cur])+1, mx)
    d = 0
    mmx = mx
    for i,t in enumerate(T[cur], start=1):
        if i==color:
            d=1
        mmx = max(mmx, dfs(t, mx, i+d))
        # dfs(t, mx, i)
    return mmx
M = dfs(0, 1, -1)
# print(R)
# print(F)
# print(M)
# for i,f in enumerate(F):
#     print(R[f])

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)

N = int(input())

E = []
T = [[] for i in range(N)]
for i,n in enumerate(range(N-1)):
    a,b = map(int,input().split())
    E.append((a-1,b-1))
    T[a-1].append(b-1)

# print(E)
# print(T)



R = [None for i in range(N)]
def dfs(using, cur):
    R[cur] = using
    i=0
    for t in T[cur]:
        if i==using:
            i+=1
        dfs(i,t)
        i+=1


dfs(-1, 0)

print(max(R)+1)
# print(K)
for e in E:
    print(R[e[1]]+1)

# print(K)
N, X = map(int, input().split())
L = list(map(int, input().split()))

x = 0
for i in range(N + 1):
    if i == 0:
        x = 0
    else:
        x += L[i - 1]
        if x > X:
            ans = i
            break

print(ans)

### FIXED CODE ###

# coding: utf-8
# Your code here!
# 行数を取得
import sys
list=[]
for line in sys.stdin:
    list.append(line)

NandX=list[0].split()

N=int(NandX[0])
X=int(NandX[1])

L=list[1].split()
D=0
i=0

if N==1:
    print(1)
else:
    while D<=X and i<=N-1:
        D=D+int(L[i])
        i+=1
        
    if i==N and D<=X:
        print(N+1)
    else:
        print(i)
import math
N = int(input())
As = list(map(int, input().split()))
lcm = 1

for a in As:
    gcd_now = math.gcd(lcm,a)
    lcm = lcm*a//gcd_now

mod = 10**9+7
ans = 0
for a in As:
    ans += (lcm//a)
    ans %= mod
print(ans)

### FIXED CODE ###

from fractions import gcd
N = int(input())
As = list(map(int, input().split()))

lcm = 1
mod = 10**9+7

def getprime(n):
    if not isinstance(n, int):
        raise TypeError("Input int")
    if n < 2:
        raise ValueError("N >= 2")
    prime = []
    # 約数はsqrt(N)まで調べればOK
    data = [i+1 for i in range(1,n)]
    while True:
        p = data[0]
        if p >= int(n**0.5):
            return prime+data
        prime.append(p)
        # pで割り切れないものだけを残す
        data = [d for d in data if d%p != 0]

from collections import defaultdict
def factorization(n):
    factors = defaultdict(int)
    if n == 2 or n == 3:
        factors[n] = 1
        return factors
    primes = getprime(int(n**0.5))
    for prime in primes:
        while n % prime == 0:
            factors[prime] += 1
            n //= prime
            # print(factors,n)
    if n != 1:
        factors[n] += 1
    return factors

d = defaultdict(int)
factors_list = []
cnt_1 = 0
for a in As:
    if a == 1:
        cnt_1 += 1
        continue
    factors = factorization(a)
    factors_list.append(factors)
    for f in factors.keys():
        d[f] = max(d[f],factors[f])

for f in d.keys():
    lcm *= f ** d[f]
    lcm %= mod

As_inv = [pow(a,mod-2,mod) for a in As]
a = sum(As_inv)%mod



print((lcm*a)%mod)
import math
n=int(input())
a=[int(input()) for i in range(n)]
w=math.ceil(n/min(a))
print(w+4)

### FIXED CODE ###

import math

n=int(input())
a=[int(input()) for i in range(5)]

print(4+math.ceil(n/min(a)))
import numpy as np


A, B, M = map(int, input().split())
a = list(map(int, input().split()))
a = np.array(a)
b = list(map(int, input().split()))
b = np.array(b)
z = [list(map(int, input().split())) for _ in range(M)]
z = np.array(z)


xx, yy = np.meshgrid(a, b)
xx1 = xx.flatten()
yy1 = yy.flatten()

xxyy = np.c_[xx1, yy1]
mem = xxyy.sum(axis=1)
mem = list(mem)

for x, y, c in z:
    mem.append(a[x - 1] + b[y - 1] - c)
   

print(min(mem))



### FIXED CODE ###

A, B, M = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
L = [[int(x) for x in input().split()] for _ in range(M)]

reg = min(a) + min(b)
for x, y, c in L:
    tmp = a[x-1] + b[y-1] - c
    reg = min(reg, tmp)
print(reg)
def nCr(n,r):
    nk = 1
    nrk = 1
    rk = 1
    for i in range (n):
        nk *= i + 1
    for i in range (n-r):
        nrk *= i + 1
    for i in range (r):
        rk *= i + 1
    return int(nk/(nrk*rk))

N,K = map(int,input().split())
for i in range(K):
    com1 = nCr(N - K + 1, i+1)
    com2 = nCr(K-1,i)
    print((com1*com2)%(10**9+7))


### FIXED CODE ###

def nCr(n,r):
    com = 1
    for i in range (1,r+1):
        com =com*(n+1-i)//i
    return com
N,K = map(int,input().split())
mod = (10**9)+7
for i in range(1,K+1):
    com1 = nCr(N - K + 1, i)
    com2 = nCr(K-1,i-1)
    print((com1*com2)%mod)
A,V = map(int,input().split())
B,W = map(int,input().split())
T = int(input())

A = A-B
B = 0

if A+V*T >= B+W*T:
  x = (B-A) / (V-W)
  print(x)
  if x <= T:
    print("YES")
  else:
    print("NO")
else:
  print("NO")


### FIXED CODE ###

a,v = map(int,input().split())
b,w = map(int,input().split())
t = int(input())
if v <= w:
  print("NO")
  exit()
d = abs(a-b)
if (v-w)*t >= d:
  print("YES")
else:
  print("NO")
def therefore(i):
  ichinokurai = i[-1]
  if ichinokurai in [2,4,5,7,9]:
    return "hon"
  else if ichinokurai in [0,1,6,8]:
    return "pon"
  else:
    return "bon"

### FIXED CODE ###

ichinikurai = int(input()[-1])
if ichinikurai in [2,4,5,7,9]:
    print("hon")
elif ichinikurai in [0,1,6,8]:
    print("pon")
else:
    print("bon")