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

#float型を許すな
#numpyはpythonで
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

n=I()
seq=LI()
c=Counter(seq)
seq=list(set(seq))
seq.sort()
lis=[seq[0]]
for i in range(1,len(seq)):
    count=0
    for x in lis:
        if seq[i]%x!=0:
            count+=1
    if count==len(lis):
        lis.append(seq[i])
#print(lis)
ans=len(lis)
for x in lis:
    if c[x]>1:
        ans-=1
print(ans)
        


        
        
        


### FIXED CODE ###

from collections import Counter
n = int(input())
a = list(map(int, input().split()))
c = Counter(a)
p = [True] * (10 ** 6 + 1)
s = list(set(a))
for x in s:
    t = x * 2
    while t <= 10 ** 6:
        p[t] = False
        t += x
ans = 0
for x in a:
    if c[x] == 1 and p[x] == True:
        ans += 1
print(ans)
### BUGGY CODE ###

if __name__ == "__main__":
    input()
    aList = list(map(int, input().split()))
    result = 1
    for num in aList:
        result *= num
    print(result if result <= 10**18 else -1)

### FIXED CODE ###

from functools import reduce

def m(l):
    result = 1
    for num in l:
        result *= num
        if result == 0:
            return 0
        elif result > 10**18:
            return -1
    return result

if __name__ == "__main__":
    input()
    aList = list(map(int, input().split()))
    aList.sort()
    print(m(aList))
### BUGGY CODE ###

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

n = raw_input()
n = int(n)

dl = raw_input()
dl = dl.split()
dl = map(int,dl)

m = raw_input()
m = int(m)

tl = raw_input()
tl = tl.split()
tl = map(int,tl)

status = 0

for t in tl:
    if t in dl:
        dl.remove(t)
    else:
        status = 1
        break

if status == 0:
    print "YES"
else:
    print "NO"
    


### FIXED CODE ###

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

n = raw_input()
n = int(n)

dl = raw_input()
dl = dl.split()
dl = map(int,dl)
dl.sort()

m = raw_input()
m = int(m)

tl = raw_input()
tl = tl.split()
tl = map(int,tl)
tl.sort()

status = 0
i = 0
j = 0
while j < m:
    d = dl[i]
    t = tl[j]
    #print d,t
    if d > t:
        status = 1
        break
    elif d == t:
        i += 1
        j += 1
    else:
        i += 1

if status == 0:
    print "YES"
else:
    print "NO"
### BUGGY CODE ###

import numpy as np
N, K = map(int,input().split())
H = np.array([int(input()) for _ in range(0, N)])
H = np.sort(H)
#print(H)
H_diff = abs(H[1:]-H[:-1])
#print(H_diff)
best = (H[-1] - H[0])*K
for i in range(0, len(H_diff)-K+2):
    #print(i)
    if np.sum(H_diff[i:i+K-1]) < best:
        #print(H_diff[i:i+K-1])
        best = np.sum(H_diff[i:i+K-1])
#print('best:{}'.format(best))
print(best)

### FIXED CODE ###

import numpy as np
N, K = map(int,input().split())
H = np.array([int(input()) for _ in range(0, N)])
H = np.sort(H)
H_diff = np.diff(H)
best = int(np.min(np.convolve((H_diff), np.ones(K-1), mode='valid')))
print(best)
### BUGGY CODE ###

n=int(input())

t_prev,a_prev=map(int,input().split())
for i in range(n-1):
  t,a=map(int,input().split())
  i=1
  t_now=t
  a_now=a
  
  while not (t_prev<=t_now and a_prev<=a_now):
    t_now=t*i
    a_now=a*i
    i+=1
    
  t_prev=t_now
  a_prev=a_now

print(t_prev+a_prev)

### FIXED CODE ###

import math

n=int(input())

t_prev,a_prev=1,1
for i in range(n):
  t,a=map(int,input().split())
  #n_koho1=math.ceil(t_prev/t)
  #n_koho2=math.ceil(a_prev/a)

  n_koho1 = t_prev // t
  n_koho2 = a_prev // a
  if t_prev % t != 0:
      n_koho1 += 1
  if a_prev % a != 0:
      n_koho2 += 1
        
  n=max(n_koho1,n_koho2)
  t=n*t
  a=n*a
    
  t_prev=t
  a_prev=a

print(t_prev+a_prev)
### BUGGY CODE ###

from bisect import bisect_right
from collections import defaultdict
import sys
input=sys.stdin.readline


def solve():
    N, K = map(int, input().split())
    *A, = map(int, input().split())
    dd = defaultdict(list)

    for i, j in enumerate(A):
        dd[j].append(i)

    conv = [0] * (N+1)
    for i, j in enumerate(A):
        pos = i

        while pos < N:
            v = A[pos]
            p = bisect_right(dd[v], pos)
            size = len(dd[v])
            if p < size:
                pos = dd[v][p]+1
                if pos == N:
                    conv[i] = 0
                    break
            else:
                conv[i] = dd[A[pos]][0] + 1
                break
    conv[N] = 0

    dp = [[0]*(N+1) for _ in range(41)]
    for i in range(N+1):
        dp[0][i] = conv[i]

    for k in range(1, 41):
        for n in range(N+1):
            dp[k][n] = dp[k - 1][dp[k - 1][n]]

    res = []
    t = K-1
    for i in range(41):
        if (t>>i)&1:
            res.append(i)
        
    pos = 0
    for i in res:
        pos = dp[i][pos]

    ans = []
    while pos < N:
        num = A[pos]
        pp = bisect_right(dd[num], pos)
        if pp < len(dd[num]):
            pos = dd[num][pp]+1
        else:
            ans.append(num)
            pos += 1
    print(*ans)


if __name__ == "__main__":
    solve()


### FIXED CODE ###

from collections import defaultdict, Counter
from bisect import bisect_right, bisect_left

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

c = Counter(A)
target = []
d = defaultdict(list)

dd = defaultdict(list)
for i, j in enumerate(A):
    dd[j].append(i)

pos = 0
loop = 1
l = []

while pos < N:
    num = A[pos]
    
    pp = bisect_right(dd[num], pos)
    if pp < len(dd[num]):
        pos = dd[num][pp]+1
    else:
        pos = dd[num][0]+1            
        loop += 1
    l.append((num, pos, loop))

for v, pos, p in l:
    if (K-p)%loop==0:
        break

pos = pos if pos<N else 0
ans = []
while pos < N:
    num = A[pos]
    pp = bisect_right(dd[num], pos)
    if pp < len(dd[num]):
        pos = dd[num][pp]+1
    else:
        ans.append(num)
        pos += 1
print(*ans)
### BUGGY CODE ###

N = int( input() )
s_list = [ int(i) for i in input().split() ]
for i in range( 1, N+1):
    print(s_list.index(i) + 1,end=" ")

### FIXED CODE ###

N = int( input() )
s_list = [ int(i) for i in input().split() ]
b = [0] * (10**5)
for i in range( N ):
    b[s_list[i]-1] = i + 1
for i in b:
    if i == 0:
        break
    else:
        print(i,end = " ")
### BUGGY CODE ###

S = str(input())
s = len(S)
cnt = 0
A = [int(S)%2019]
for i in range(s-1):
    a = int(S[i])*10**(s-i-1)%2019
    A.append((A[-1]-a)%2019)
    y = A.count(A[-1])
    if y >= 2:
      cnt += y-1
cnt += A.count(0)
print(cnt)

### FIXED CODE ###

S = str(input())
s = len(S)
cnt = 0
A = [0]*2019
r = 0
for i in range(s):
  x = (r+pow(10, i, 2019)*int(S[s-i-1]))%2019
  A[x] += 1
  r = x
  
for i in range(1,2019):
  if A[i] >= 2:
    cnt += A[i]*(A[i]-1)//2
cnt += A[0]*(A[0]+1)//2

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

import numpy as np
N, K = map(int, input().split())
h = []

for _ in range(N):
    h.append(int(input()))

h_sorted = sorted(h, reverse=False)
diff_h_sorted = np.diff(h_sorted, n=1, axis=-1)
ans = 10**15

for i in range(len(diff_h_sorted) - K + 2):
    ans = min(ans, sum(diff_h_sorted[i:i+K-1]))

print(ans)

### FIXED CODE ###

N, K = map(int, input().split())
h = [int(input()) for i in range(N)]
h.sort()
print(min(h[i+K-1] - h[i] for i in range(N-K+1)))
### BUGGY CODE ###

def find(x):
    if parent[x]<0:
        return x
    else:
        parent[x]=find(parent[x])
        return parent[x]

def same(x,y):
    return find(x)==find(y)

def union(x,y):
    root_x=find(x)
    root_y=find(y)
    if root_x==root_y:
        return
    if parent[root_x]>parent[root_y]:
        root_x,root_y=root_y,root_x
    parent[root_x]+=parent[root_y]
    parent[root_y]=root_x

def members(n,x):
    root=find(x)
    return [i for i in range(n) if find(i)==root]

def get_size(x):
    return -parent[find(x)]

def get_root():
    return [i for i, root in enumerate(parent) if root<0]

N,M=map(int,input().split())
parent=[-1 for i in range(N)]
for i in range(M):
    a,b=map(int,input().split())
    a=a-1
    b=b-1
    union(a,b)

poe=[]
for i in range(N):
    if i==find(i):
        poe.append((members(N,i)))

ans=len(poe)-1

print(ans)

### FIXED CODE ###

def find(x):
    if parent[x]<0:
        return x
    else:
        parent[x]=find(parent[x])
        return parent[x]

def same(x,y):
    return find(x)==find(y)

def union(x,y):
    root_x=find(x)
    root_y=find(y)
    if root_x==root_y:
        return
    if parent[root_x]>parent[root_y]:
        root_x,root_y=root_y,root_x
    parent[root_x]+=parent[root_y]
    parent[root_y]=root_x

def members(n,x):
    root=find(x)
    return [i for i in range(n) if find(i)==root]

def get_size(x):
    return -parent[find(x)]

def get_root():
    return [i for i, root in enumerate(parent) if root<0]

N,M=map(int,input().split())
parent=[-1 for i in range(N)]
for i in range(M):
    a,b=map(int,input().split())
    a=a-1
    b=b-1
    union(a,b)

ans=0
for i in parent:
    if i<0:
        ans+=1

print(ans-1)
### BUGGY CODE ###

N,Q = map(int, input().split())
S = input()
for i in range(Q):
  l, r = map(int, input().split())
  s = S[l-1:r]
  s_list= s.split('AC')
  print(len(s_list)-1)

### FIXED CODE ###

import sys
sy = sys.stdin.readlines()
N,Q = map(int, sy[0].split())
S = sy[1]
ACindex = [0 for _ in range(N+1)]
count = 0
for n in range(1, N):
  if S[n-1]=="A" and S[n]=="C":
    count += 1
  ACindex[n+1] = count

for i in range(Q):
  l, r = map(int, sy[2+i].split())
  print(ACindex[r]-ACindex[l])
### BUGGY CODE ###

import itertools

N = int(input())

l = list()
for i in range(N):
    l.append(int(input()))

lsum = list()

for i in range(N+1):
    lc = list(itertools.combinations(l, i))
    lsum.extend(list(map(sum, lc)))

lsum = sorted(lsum, reverse=True)


for i in range(len(lsum)):
    if lsum[i] % 10 != 0:
        print(lsum[i])
        break
    elif lsum[i] == 0:
        print(0)
        break

### FIXED CODE ###

import itertools

N = int(input())

l = list()
lm = list()
for i in range(N):
    x = int(input())
    l.append(x)
    if x % 10 != 0:
        lm.append(x)

lm = sorted(lm)

a = sum(l)
if a % 10 == 0:
    if lm == []:
        print(0)
    else:
        print(a - lm[0])
else:
    print(a)
### BUGGY CODE ###

n, m, k = map(int, input().split())
MOD = 998244353


def power(n, k, mod):
    if k == 0:
        return 1
    elif k % 2 == 1:
        return (n * power(n, k - 1, mod)) % mod
    else:
        return power((n ** 2) % mod, k // 2, mod)


lp = [1]  # (m - 1) ** i
p = 1
for i in range(n - 1):
    p = (p * (m - 1)) % MOD
    lp.append(p)


lf = [1]  # i!
f = 1
for i in range(n - 1):
    f = (f * (i + 1)) % MOD
    lf.append(f)

fn = lf[-1]

answer = 0

fr = 1
for i in range(n - 1 - (k + 1)):
    fr = (fr * (i + 1)) % MOD


f = 1
for i, f, fr, p in zip(range(k + 1), lf, reversed(lf), reversed(lp)):
    # d = (lf[i] * lf[n - 1 - i]) % MOD
    d = (f * fr) % MOD
    dinv = power(d, MOD - 2, MOD)
    c = (fn * dinv) % MOD
    # n_pattern = (c * m * lp[n - 1 - i]) % MOD
    n_pattern = (c * m * p) % MOD

    answer = (answer + n_pattern) % MOD


# def n_pattern(n_pair):
#     return (lc[n_pair] * m * power(m - 1, n - 1 - n_pair, MOD)) % MOD


# answer = 0
# for i in range(k + 1):
#     answer = (answer + n_pattern(i)) % MOD


print(answer)






### FIXED CODE ###

n, m, k = map(int, input().split())
MOD = 998244353


class Combination:
    def __init__(self, n, mod):
        self.n = n
        self.mod = mod

        self.f = self._get_f()
        self.fi = self._get_fi()

    def __call__(self, k):
        if not 0 <= k <= self.n:
            return 0
        else:
            num = self.f[self.n]
            deninv = (self.fi[k] * self.fi[self.n - k]) % self.mod
            return (num * deninv) % self.mod

    def _get_f(self):
        f = 1
        lf = [1]

        for i in range(1, self.n + 1):
            f = (f * i) % self.mod
            lf.append(f)

        return lf

    def _get_fi(self):
        ii = 1
        lii = [0, 1]  # [i^-1 modulo mod for i in 0, ..., n]
        fi = 1
        lfi = [1, 1]

        for i in range(2, self.n + 1):
            ii = (-lii[self.mod % i] * (self.mod // i)) % self.mod
            lii.append(ii)

            fi = (fi * ii) % self.mod
            lfi.append(fi)

        return lfi


c = Combination(n - 1, MOD)


def n_pattern(i):
    result = m
    result *= c(i)
    result %= MOD
    result *= pow(m - 1, n - i - 1, MOD)
    result %= MOD
    return result


answer = sum(n_pattern(i) for i in range(k + 1)) % MOD
print(answer)
### BUGGY CODE ###

def main():

    from builtins import input, int, map

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

    ans = 0

    for i in range(n - 1):
        for j in range(i + 1, n):
            ans += (a[i] * a[j]) % (10**9 + 7)

    print(ans % (10**9 + 7))

main()

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
mod = 10**9 + 7
ans = 0
v = sum(a)

for i in range(n - 1):
    v -= a[i]
    ans += a[i]*v

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

def main(n,m,r):
    c_ac = 0
    c_wa = 0
    for i in range(n):
        wa = 0
        for j in range(len(r)):
            if int(r[j][0]) != i+1:
                continue
            if r[j][1] == "WA":
                wa += 1
            elif r[j][1] == "AC":
                c_ac += 1
                c_wa += wa
                break
    return "{0} {1}".format(c_ac, c_wa)


n,m = map(int, input().split())
r = list(input().split() for _ in range(m))
print(main(n,m,r))

### FIXED CODE ###

def main(n,m,r):
    ac = [0]*n
    wa = [0]*n
    for i in range(len(r)):
        seq = int(r[i][0])
        judge = r[i][1]
        if ac[seq-1] == 1:
            continue
        if judge == "WA":
            wa[seq-1] += 1
        else:
            ac[seq-1] = 1
    for i in range(len(ac)):
        if ac[i] == 0:
            wa[i] = 0
    return "{0} {1}".format(sum(ac), sum(wa))

n,m = map(int, input().split())
r = list(input().split() for _ in range(m))
print(main(n,m,r))
### BUGGY CODE ###

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

ans = 0

for i in range(len(P)-K+1):
    c = 0
    for j in range(i, i+K):
        e = (P[j] + 1)/2
        c += e

    if c > ans:
        ans = c

print(ans)

### FIXED CODE ###

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


ans = 0
for i in range(len(P)-K+1):
    if i == 0:
        c = sum(P[:K])
    else:
        c = c + P[i+K-1] - P[i-1]
    if c > ans:
        ans = c


print((ans+K)/2)
### BUGGY CODE ###

N = int(input())
l = []
c = 0
for _ in range(N):
    n = input()
    if n not in l:
        l.append(n)
        c+=1

print(c)

### FIXED CODE ###

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

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

import sys
import math
from operator import mul
from functools import reduce
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

x,y= (int(_) for _ in input().split()) 
if (x+y)%3!=0:
    print(0)
    sys.exit()
else:
    n=(x+y)/3
    n=int(n)
    if x<n or y<n:
         print(0)
         sys.exit()
    else:
        x=x-n
        y=y-n
        xy=[x,y]
        ans=int(cmb(x+y, x))
        print(ans%1000000007)

### FIXED CODE ###

import sys
import math
from operator import mul
from functools import reduce
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 
N = 10**6
g1 = [1, 1] 
g2 = [1, 1] 
inverse = [0, 1] 

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

x,y= (int(_) for _ in input().split()) 
if (x+y)%3!=0:
    print(0)
    sys.exit()
else:
    n=(x+y)/3
    n=int(n)
    if x<n or y<n:
         print(0)
         sys.exit()
    else:
        x=x-n
        y=y-n
        ans=int(cmb(x+y, x,mod))
        print(ans%1000000007)
### BUGGY CODE ###

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

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

### FIXED CODE ###

import collections

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

c = collections.Counter(A)

for i in range(1,N+1):
    print(c[i])
### BUGGY CODE ###

from itertools import accumulate
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

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

A_acc = [0]+list(accumulate(A))

ans = 0
for l in range(N):
    for r in range(l+1, min(l+K, N+1)):
        if r % K == (A_acc[r]-A_acc[l]+l) % K:
            ans += 1
print(ans)


### FIXED CODE ###

from collections import defaultdict
from itertools import accumulate
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

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

A_acc = [0]+list(accumulate(A))


ans = 0
D = defaultdict(int)
for l in range(N+1):
    t = (A_acc[l]-l) % K
    if l>=K:
      r = (A_acc[l-K]-(l-K))
      D[r%K]-=1
    ans += D[t]
    D[t] += 1


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

def cmb(n, r, p):
    if r < 0 or n < r:
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

n, a, b = map(int, input().split())

p = 10 ** 9 + 7
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]

for i in range(2, n + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

ma = cmb(n, a, p)
mb = cmb(n, b, p)

print((pow(2, n, p) - 1 - ma - mb) % p)

### FIXED CODE ###

n, a, b = map(int, input().split())

p = 10 ** 9 + 7
inv = [0] * (b + 1)
inv[1] = 1

for k in range(2, b + 1):
	inv[k] = pow(k, p - 2, p)

com = 1
for i in range(1, a + 1):
	com = (com * (n + 1 - i)) % p * inv[i]

coma = com

for j in range(a + 1, b + 1):
	com = (com * (n + 1 - j)) % p * inv[j]

comb = com

print((pow(2, n, p) - 1 - coma - comb) % p)
### BUGGY CODE ###

from bisect import bisect_left

n = int(input())
p = []

for i, x in enumerate(map(int, input().split())):
    p.append([x, i])

p.sort(reverse=True)

s = [-1, -1, p[0][1], n, n]

#print(p)

ans = 0
i = 2
for a, x in p[1:]:
    t = bisect_left(s, x)
    ans += a * ((x - s[t-1]) * (s[t+1] - s[t]) + (s[t] - x) * (s[t-1] - s[t-2]))
    #print(t, s)
    s.insert(t, x)
    i += 1


print(ans)




### FIXED CODE ###

from bisect import bisect_left
import array

n = int(input())
p = []

for i, x in enumerate(map(int, input().split())):
    p.append([x, i])

p.sort(reverse=True)

s = array.array('i', [-1, -1, p[0][1], n, n])

#print(p)

ans = 0
i = 2
for a, x in p[1:]:
    t = bisect_left(s, x)
    ans += a * ((x - s[t-1]) * (s[t+1] - s[t]) + (s[t] - x) * (s[t-1] - s[t-2]))
    #print(t, s)
    s.insert(t, x)
    i += 1


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

import bisect

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

ans=0
for i0 in range(N):
    a1 = bisect.bisect_left(B,A[i0]+1)
    for i1 in range(a1,N):
        a2 = bisect.bisect_left(C,B[i1]+1)
        ans += N - a2
print(ans)


### FIXED CODE ###

import bisect

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

a2=[]
for i1 in range(N):
    a2.append(bisect.bisect_left(C,B[i1]+1))

a2c=[0]*(N+1)
for i1 in range(N-1,-1,-1):
    a2c[i1] = a2c[i1+1] + N - a2[i1]

ans=0
for i0 in range(N):
    a1 = bisect.bisect_left(B,A[i0]+1)
    ans += a2c[a1]
print(ans)
### BUGGY CODE ###

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

ans = 0
for i in range(N+1):
  ans = max(ans, A * i // B - A * (i // B))

print(ans)

### FIXED CODE ###

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

def solve(i):
  return A * i // B - A * (i // B)

print(solve(min(B-1, N)))
### BUGGY CODE ###

n = int( input() )

judge_nums = []
for i in range( n ):
	judge_num = 10**27 # 一桁目はフェイク
	str = input()
	for s in str :
		judge_num += 10**(ord( s )-97)
	judge_nums.append( judge_num )
judge_nums.sort()


count = 0
for i in range( n ) :
	for j in range( i+1, n ) :
		if judge_nums[i] != judge_nums[j] :
			break
		if judge_nums[i] == judge_nums[j] :
			count += 1

print( count )


### FIXED CODE ###

from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

#=-------------------------------------  
n = int( input() )

dict = {}
for i in range( n ):
	sorted_input = "".join( sorted( list( input() ) ) )
	if dict.get( sorted_input ) == None:
		dict[ sorted_input ] = 1
	else :
		dict[ sorted_input ] += 1

count = 0
for eachValue in dict.values():
	if eachValue == 1 : continue
	count += cmb( eachValue, 2 )
print( count )
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
ans=""
for i in range(N):
  ans+=str(A.index(i+1)+1)
  if i!=N-1:
    ans+=" "
print(ans)


### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
#A=int(input().split())
#print(A)
B=[ 0 for _ in range(N)]
#print(B)
ans=""
for i in range(N):
  B[A[i]-1]=i+1
#  ans+=str(A.index(i+1)+1)
#  if i!=N-1:

for i in range(N):
  ans+=str(B[i])
  if i!=N-1:
    ans+=" "
#print(B)
print(ans)
### BUGGY CODE ###

N,K=map(int,input().split())
S=[]
for i in range(N):
  a,b=map(int,input().split())
  for i in range(b):
    S.append(a)
S=sorted(S)
print(S[K-1])

### FIXED CODE ###

N,K=map(int,input().split())
S={}
for i in range(N):
  a,b=map(int,input().split())
  if a in S:
    S[a]+=b
  else:
    S[a]=b
T=sorted(S.items())
count=0
for i in range(len(T)):
  count+=T[i][1]
  if count>=K:
    print(T[i][0])
    break
### BUGGY CODE ###

LARGE = 10 ** 9 + 7
 
 
def solve(n, a_list):
 
    # inverse
    res = 0
    for i in range(n):
        res += pow(a_list[i], LARGE - 2, LARGE)
        res %= LARGE
 
    # primes
    p_candidate_list = [1] * 10 ** 6
    p_candidate_list[0] = 0
    p_candidate_list[1] = 0
    for p in range(2, 10 ** 6):
        if p_candidate_list[p]:
            for q in range(p * p, 10 ** 6, p):
                p_candidate_list[q] = 0
    primes_1000000 = [p for p in range(1000000) if p_candidate_list[p]]

    lcm = 1
    for p in primes_1000000:
        r_max = 0
        for i in range(n):
            r = 0
            while a_list[i] % p == 0:
                r += 1
                a_list[i] = a_list[i] // p
            r_max = max(r_max, r)
        lcm *= pow(int(p), r_max, LARGE)
        lcm %= LARGE
 
    # for q in set(a_list):
    #     lcm *= q
    #     lcm %= LARGE
 
    return res * lcm % LARGE
 
 
def main():
    n = int(input())
    a_list = list(map(int, input().split()))
    res = solve(n, a_list)
    print(res)
 
 
def test():
    assert solve(3, [2, 3, 4]) == 13
    # assert solve(5, [12, 12, 12, 12, 12]) == 5
    # assert solve(3, [1000000, 999999, 999998]) == 996989508
 
 
if __name__ == "__main__":
    test()
    main()

### FIXED CODE ###

from functools import reduce
from fractions import gcd

N = int(input())
A = list(map(int, input().split()))
 
MOD = 10 ** 9 + 7
 
lcm = reduce(lambda x,y: x*(y//gcd(x,y)), A)
lcm %= MOD

coef = sum(pow(a, MOD-2, MOD) for a in A)
ans = lcm * coef % MOD

print(ans)