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

def isPrime(n):
    if n <= 2:
        return n == 2
    if (n % 2 == 0):
        return False
    for i in range(3, n // 2 + 1, 2):
        if n % i == 0:
            return False
    return True


N = int(input())
print(len(list(filter(isPrime, [int(input()) for i in range(N)]))))



### FIXED CODE ###

import math

def isPrime(n):
    if n <= 2:
        return n == 2
    if (n % 2 == 0):
        return False
    for i in range(3, int(math.sqrt(n)) + 1, 2):
        if n % i == 0:
            return False
    return True

N = int(input())
print(len(list(filter(isPrime, [int(input()) for i in range(N)]))))
### BUGGY CODE ###

N = int(input())
X = input()

n1 = X.count("1")
Xn = int(X, 2)

Xms = (Xn % (n1 - 1)) if n1 > 1 else 0
Xml = Xn % (n1 + 1)


def f(n):
    if n == 0:
        return 0
    return f(n % bin(n).count("1")) + 1


dp = [0] * ((10 ** 5) * 2 + 1)
for i in range(1, len(dp)):
    dp[i] = f(i)


for i in range(N):
    cnt = 0
    p2 = 2 ** (N - i - 1)
    Xim = 0

    if X[i] == "1" and n1 == 1:
        print(cnt)
    elif X[i] == "1":
        print(dp[(Xms - pow(2, N - i - 1, n1 - 1)) % (n1 - 1)] + 1)
    else:
        print(dp[(Xml + pow(2, N - i - 1, n1 + 1)) % (n1 + 1)] + 1)



### FIXED CODE ###

N = int(input())
X = input()

n1 = X.count("1")
Xn = int(X, 2)

Xms = (Xn % (n1 - 1)) if n1 > 1 else 0
Xml = Xn % (n1 + 1)

p2s = [1]
p2l = [1]
s2 = 1
l2 = 1
for i in range(N - 1):
    s2 = (s2 * 2) % (n1 - 1) if n1 > 1 else 0
    l2 = (l2 * 2) % (n1 + 1)
    p2s.append(s2)
    p2l.append(l2)

for i in range(N):
    cnt = 0
    p2 = 2 ** (N - i - 1)
    Xim = 0

    if X[i] == "1" and n1 == 1:
        print(cnt)
        continue
    elif X[i] == "1":
        Xim = (
            Xms - p2s[-i - 1]
            if Xms - p2s[-i - 1] >= 0
            else ((n1 - 1) + (Xms - p2s[-i - 1]))
        )
    else:
        Xim = (
            Xml + p2l[-i - 1]
            if Xml + p2l[-i - 1] < (n1 + 1)
            else (Xml + p2l[-i - 1] - (n1 + 1))
        )

    cnt += 1
    while Xim > 0:
        Xim %= bin(Xim).count("1")
        cnt += 1
    print(cnt)
### BUGGY CODE ###

n, m = list(map(int,input().split()))
for i in range(m//n,0,-1):
    if m % i == 0:
        print(i)
        break

### FIXED CODE ###

n, m = list(map(int,input().split()))
def solve():
    for i in range(m//n, 0, -1):
        if m % i == 0:
            if m//i>= n:
                print(i)
                break
solve()
### BUGGY CODE ###

import sys
readline=sys.stdin.readline

K = int(readline())
S = readline().rstrip()
N = len(S)

DIV = 10 ** 9 + 7

from functools import reduce
def nCr(n,r,DIV):
  if r<n-r:
    r=n-r
  if r==0:
    return 1
  f=lambda x,y:x*y%DIV
  X=reduce(f,range(n-r+1,n+1))
  Y=reduce(f,range(1,r+1))
  return X*pow(Y,DIV-2,DIV)%DIV

# N = |S|とする
# N + Kの長さの文字列で、N～N + K文字までが固定で、あとは任意の25文字
# の数が答え
ans = 0
for i in range(N,N + K + 1):
  # N + K文字からi文字を選ぶ場合の数
  pat = nCr(N + K, i ,DIV)
  
  # 残りN + K - i文字に対して25通り選べる場合の数
  pat *= pow(25, N + K - i, DIV)
  pat %= DIV
  ans += pat
  ans %= DIV
print(ans)

### FIXED CODE ###

import sys
readline = sys.stdin.readline

K = int(readline())
S = readline().rstrip()
S = len(S)
N = K + S

DIV = 10 ** 9 + 7
n = (10 ** 6) * 5
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

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

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

# K = 3, S = 5のとき
# ..X.X.X.
# Xが取る3か所を選んだ上で、
# 最も右のXよりも右のマス：各26通り
# 最も右のXを含む、それより左のマス：Xのマスは1通り、それ以外は各25通り
# 最も右のXが
# ..X.....　の状態から、
# .......X  
# の状態について、場合の数を求める

ans = 0
for xpos in range(S, N + 1):
  # xpos箇所からK箇所を選ぶ場合の数
  # 一番右に1個固定した状態で、残りのxpos - 1か所からS - 1個を選ぶ
  pat = nCr(xpos - 1, S - 1, DIV)
#  print("xpos",xpos,"ncr",ncr)
#  print(S,"from",xpos,"pat",pat)
  # その場合の数に対して、X以外の文字の選び方は25 ** (X - S)通りある
#  print("25 for",xpos - S,"boxes")
  pat *= pow(25, xpos - S, DIV)
  pat %= DIV
  
  # 残りのマスに対しては26通りずつ選べる
#  print("26 for ",N - xpos,"boxes")
  pat *= pow(26, N - xpos, DIV)
  pat %= DIV
#  print("xpos",xpos,"pat",pat)
  
  ans += pat
  ans %= DIV

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



s = input()


def main():
#    s = ['0' for _ in range(10**5)]
#   TLE check py3 だとちょっと遅いかもしれない？
    n = len(s)
    mod = 10**9 + 7

    dp = [[0]* 13 for _ in range(n+1)]
    dp[0][0] = 1

    #print(len(dp),len(dp[0]))

    # i : 桁数
    # j : 13で割った余り
    # k : ? をkと仮定
    # dp[i][j] : i+1 桁目 までの数字を13で割ったとき、余りがjになる数の個数
    for i in range(n):
        if s[i] != '?':

            c = int(s[i]) - int('0')
            for j in range(13):
                i_ = i+1
                j_ = (j*10+c); j_%=13
                dp[i_][j_] += dp[i][j]
                dp[i_][j_] %= mod
        else: 
            for j in range(13):
                for k in range(10):
                    i_ = i+1
                    j_ = j*10+k ; j_ %= 13
                    dp[i_][j_] += dp[i][j]
                    dp[i_][j_] %= mod

        # print(i,j,dp[i+1])
    print(dp[-1][5])      
     
main()
        


### FIXED CODE ###



s = input()


def main():
#    s = ['0' for _ in range(10**5)]
#   TLE check py3 だとちょっと遅いかもしれない？
    n = len(s)
    mod = 10**9 + 7

    dp = [[0]* 13 for _ in range(n+1)]
    dp[0][0] = 1

    #print(len(dp),len(dp[0]))

    # i : 桁数
    # j : 13で割った余り
    # k : ? をkと仮定
    # dp[i][j] : i+1 桁目 までの数字を13で割ったとき、余りがjになる数の個数
    for i in range(n):
        if s[i] != '?':

            c = int(s[i]) - int('0')
            for j in range(13):
                i_ = i+1
                j_ = (j*10+c); j_%=13
                dp[i_][j_] += dp[i][j]
                dp[i_][j_] %= mod
        else: 
            for j in range(13):
                for k in range(10):
                    i_ = i+1
                    j_ = j*10+k ; j_ %= 13
                    dp[i_][j_] += dp[i][j]
                    dp[i_][j_] %= mod

        # print(i,j,dp[i+1])
    print(dp[-1][5])      
     
main()
### BUGGY CODE ###

N = int(input())
ans = 0
for i in range(1, N+1):
  n = N//i
  cnt = (n*(2*i + (n-1) *i))//2
  ans += cnt
print(ans)

### FIXED CODE ###

N = int(input())
ans = 0
for i in range(1, N+1):
  n = N//i
  cnt = i*n*(n+1)//2
  ans += cnt
print(ans)
### BUGGY CODE ###

N, Q = map(int, input().split())
S = input()
q =[]
for i in range(Q):
    q.append(list(map(int, input().split())))
for i,j in q:
    tmp = 0
    for k in range(i-1,j):
        if S[k] == "A":
            if k+1<j and S[k+1] == "C":
                tmp += 1
    else:
        print(tmp)

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
q =[]
temp = [0] * (N+1)
tmp = 0
for i in range(1,N):
    if S[i-1] == "A":
        if S[i] == "C":
            tmp +=1
    temp[i+1] = tmp
for j in range(Q):
    inp = input().split()
    print(temp[int(inp[1])] - temp[int(inp[0])])
### BUGGY CODE ###

mod = 10**9 + 7

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

dp = [1] * (n + 1)
dp[1] = 0 if 1 in a else 1
for i in range(2, n + 1):
    if i in a:
        dp[i] = 0
    else:
        dp[i] = dp[i - 1] % mod + dp[i - 2] % mod

print(dp[n] % mod)


### FIXED CODE ###

mod = 10**9 + 7

n, m = list(map(int, input().split()))
a = set([int(input()) for _ in range(m)])

dp = {}
for i in range(n + 1):
    dp[i] = 1
dp[1] = 0 if 1 in a else 1
for i in range(2, n + 1):
    if i in a:
        dp[i] = 0
    else:
        dp[i] = dp[i - 1] % mod + dp[i - 2] % mod
        dp[i] %= mod

print(dp[n] % mod)
### BUGGY CODE ###

import functools
import collections
import fractions
N = int(input())
A = [int(i) for i in input().split()]


C = collections.Counter(A)

mod = 10**9 + 7

# lcm = 1
# for a in C.keys():
#     lcm = lcm*a//fractions.gcd(lcm, a)
# print(lcm)


def multiple(a, b):
    return a*b // fractions.gcd(a, b)


def lcm(nums):
    return functools.reduce(multiple, nums)


lcm = lcm(list(C.keys()))

ans = 0
for k, v in C.items():
    ans += lcm//k*v
    ans %= mod
print(ans)


### FIXED CODE ###

import functools
import fractions
N = int(input())
A = [int(i) for i in input().split()]
S = set(A)


mod = 10**9 + 7


def multiple(a, b):
    return a*b // fractions.gcd(a, b)


def lcm(nums):
    return functools.reduce(multiple, nums)


lcm = lcm(S)

ans = 0
for a in A:
    ans += lcm//a
    # ans %= mod
print(ans % mod)
### BUGGY CODE ###

N, M = input().split(" ")
if M == 1:
    a, b = input().split(" ")
    print(int(b)-int(a)+1)
else:    
    a, b = input().split(" ")
    sets = set([i for i in range(int(a),int(b)+1)])
    for m in range(int(M)-1):
        a, b = input().split(" ")
        sets = sets & set([i for i in range(int(a),int(b)+1)])
    print(len(sets))

### FIXED CODE ###

N, M = input().split(" ")
#S = []
if M == 1:
    a, b = input().split(" ")
    print(int(b)-int(a)+1)
else:    
    a, b = input().split(" ")
    aM, bm = int(a),int(b)
    #sets = set([i for i in range(int(a),int(b)+1)])
    for m in range(int(M)-1):
        a, b = input().split(" ")
        aM = max(aM,int(a))
        bm = min(bm,int(b))
        #sets = sets & set([i for i in range(int(a),int(b)+1)])
    if(bm<aM):
        print(0)
    else:
        print(int(bm)-int(aM)+1)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
B = range(-N//2 + 1, max(A))
S = list()
s = 0

for b in B:
    for idx, it in enumerate(A):
        s += abs(it - (b+idx))
    S.append(s)
    s = 0
    
print(min(S))

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
B = [it - (idx + 1) for idx, it in enumerate(A)]
S = []

B.sort()
if N%2 == 1:
    b = B[(N-1)//2]
else:
    b = (B[(N-1)//2] + B[(N-1)//2 + 1]) // 2
    
S = sum([abs(i-b) for i in B])
    
print(S)
### BUGGY CODE ###

import bisect

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

cnt = 0
for i in range(n - 2):
    for j in range(i + 1, n - 1):
        length = l[i] + l[j]
        cnt += bisect.bisect_left(l[j+1:], length)
print(cnt)

### FIXED CODE ###

import bisect

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

cnt = 0
for i in range(n - 2):
    for j in range(i + 1, n - 1):
        cnt += max(0, bisect.bisect_left(l, l[i] + l[j]) - j - 1)
print(cnt)
### BUGGY CODE ###

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

ans = N

for i in range(N):
  for j in range(N):
    if j == i:
      continue
    else:
      if A[i]%A[j] == 0:
        ans -= 1
        break
        
print(ans)

### FIXED CODE ###

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

A.sort()
maxA = A[-1]
DP = [-1 for i in range(maxA+1)]
for a in A:
  if DP[a] != 0:
    if DP[a] == 1:
      DP[a] = 0
      continue
    for i in range(2*a, maxA+1, a):
      DP[i] = 0
    DP[a] = 1
  
    
ans = 0
for i in DP:
  if i == 1:
    ans += 1
    
print(ans)
### BUGGY CODE ###

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

H, W = map(int,input().split())
sth, stw = 0, 0
glh, glw = H-1, W-1

INF = 10000
Gmap = [list(input()) for _ in range(H)]
Dist = [[INF]*W for _ in range(H)]
direc = {(1,0), (0,1)}

from collections import deque

def bfs(init):

    next_q = deque([])
    if Gmap[init[0]][init[1]]=="#":
        Dist[init[0]][init[1]] = 1
        next_q.append([0,0,"#"])
    else:
        Dist[init[0]][init[1]] = 0
        next_q.append([0,0,"."])

    while len(next_q)!=0:
        #キュー取り出し(先頭)
        h, w, fg = next_q.popleft()
        for d in direc:
            hs, ws = h + d[0], w + d[1]
            if not (0<=hs<H and 0<=ws<W):
                continue
            fgs = Gmap[hs][ws]
            if fgs=='#' and fg == '.':
                Dist[hs][ws] = min(Dist[h][w]+1, Dist[hs][ws])
            else:
                Dist[hs][ws] = min(Dist[h][w], Dist[hs][ws])
            next_q.append([hs,ws,fgs])
    return Dist

def main():
    ret = bfs([sth,stw])
    print(ret[glh][glw])

if __name__ == '__main__':
    main()


### FIXED CODE ###

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

def main():
    H, W = map(int,input().split())
    sth, stw = 0, 0
    glh, glw = H-1, W-1

    INF = 10000
    Gmap = [list(input()) for _ in range(H)]
    Dist = [[INF]*W for _ in range(H)]
    direc = {(1,0), (0,1)}

    if Gmap[0][0]=='#':
        Dist[0][0]=1
    else:
        Dist[0][0]=0

    for h in range(H):
        for w in range(W):
            nw = Gmap[h][w]
            for d in direc:
                hs, ws = h + d[0], w + d[1]
                if 0<=hs<H and 0<=ws<W:
                    cr = Gmap[hs][ws]
                    Dist[hs][ws] = min(Dist[hs][ws], Dist[h][w] + (cr=='#' and nw=='.'))
    print(Dist[glh][glw])

if __name__ == '__main__':
    main()
### BUGGY CODE ###

# coding: utf-8
# Your code here!

import sys
input = sys.stdin.readline

def main():
    K,S = (int(x) for x in input().split())

    count = 0

    for x in range(K+1):
        for y in range(K+1):
            for z in range(K+1):
                # for make turple (x,y,z)
                # and calculate Sum of turple
                if sum((x,y,z)) == S:
                    count += 1
                    
    print(count)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    K,S = (int(x) for x in input().split())

    count = 0

    for x in range(K+1):
        for y in range(K+1):
            z = S - (x + y)
            if z >= 0 and z <= K:
                count += 1

    print(count)

if __name__ == '__main__':
    main()
### BUGGY CODE ###

N = int(input())
num = 2
idx = 1
nums = [1]
while True:
  if num**idx > N:
    if idx == 2 or num ==1:
      break
    else:
      num += 1
      idx = 0
      continue
  else:
    nums.append(num**idx)
    idx += 1
nums.sort(key=lambda x:-x)
print(nums[0])


### FIXED CODE ###

N = int(input())
num = 2
idx = 1
nums = [1]
while True:
  if num**idx > N:
    if idx == 2 or N in range(1, 5):
      break
    else:
      num += 1
      idx = 0
      continue
  else:
    nums.append(num**idx)
    idx += 1
nums.sort(key=lambda x:-x)
print(nums[0])
### BUGGY CODE ###

from collections import defaultdict
def main():
    # Load data
    N = int(input())
    A = list(map(int, input().split()))
    p = 10**9 + 7
    # LCM: dict 最小公倍数の素因数分解
    LCM = defaultdict(int)
    # A2Factor: list A[i]の素因数分解
    A2Factor = []
    
    def factorization(n):
        arr = defaultdict(int)
        temp = n
        for i in range(2, int(-(-n**0.5//1))+1):
            if temp%i==0:
                cnt=0
                while temp%i==0:
                    cnt+=1
                    temp //= i
                arr[i] = cnt

        if temp!=1:
            arr[temp] = 1

        if not arr:
            arr[n] = 1

        return arr

    for idx in range(N):
        arr = factorization(A[idx])
        for key, value in arr.items():
            LCM[key] = max(LCM[key], value)
        A2Factor.append(arr)
    ans = 0
    for i in range(N):
        tmp = 1
        for key, value in LCM.items():
            cnt = 0 if key not in A2Factor[i].keys() else A2Factor[i][key]
            tmp *= pow(key, value-cnt, p)
            tmp %= p
        ans += tmp % p
        ans %= p

    print(ans % p)

main()

### FIXED CODE ###

from math import gcd

def lcm(a, b):
    return a*b//gcd(a,b)
def main():
    N = int(input())
    A = list(map(int, input().split()))
    mod = 10**9 + 7
    LCM = 1
    for a in A:
        LCM = lcm(LCM, a)
    ans = 0
    for a in A:
        ans += (LCM//a)
        

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

import numpy as np
n, a = [int(i) for i in input().split()]
x = [int(i) for i in input().split()]

dp= np.zeros((n+1,n*a+1),dtype=int)
dp[0][0]=1
ans=0

for k in range(1,n+1):
  for i in range(k,-1,-1):
    for j in range(0, a * n + 1):
      if j>=x[k-1] and i>=1:
        dp[i][j]= dp[i][j] + dp[i-1][j-x[k-1]]
      else:
        dp[i][j]= dp[i][j] 
      
for i in range(1,n+1):
  ans+=dp[i][a*i]

print(ans)

### FIXED CODE ###

n, a = [int(i) for i in input().split()]
x = [int(i) for i in input().split()]

dp=[[0 for i in range(a*n+1)] for j in range(n+1)]
dp[0][0]=1
ans=0
f=0

for k in range(1,n+1):
  kx=x[k-1]
  f+=kx
  for i in range(k,0,-1):
    for j in range(kx,a*n+1):
      dp[i][j] += dp[i-1][j-kx]
      if j > f:
        break
      
for i in range(1,n+1):
  ans+=dp[i][a*i]

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

N = int(input())
A = list(map(int,input().split()))
for i in range(1,N+1):
    print(A.count(i))

### FIXED CODE ###

n=int(input())
A=list(map(int,input().split()))
N=[0]*n
for a in A:
    N[a-1]+=1
 
for i in N:
    print(i)
### BUGGY CODE ###

h,n=map(int,input().split())
l=[[0,0] for _ in range(n)]
#dp=[0 for _ in range(h+1)]
mnc=100000
for i in range(n):
  d,m=map(int,input().split())
  l[i]=[d,m]
  c=d/m
  mnc=min(c,mnc)
r=int(h/mnc)+2
mxdm=[0 for _ in range(r)] #mp=i+1のときの最大ダメージ
for i in range(1,r):
  for j in range(n):
    d,m=l[j][0],l[j][1]
    if i>=m:
      mxdm[i]=max(mxdm[i],mxdm[i-m]+d)
      #print(mxdm[i])
  if mxdm[i]>=h:
    print(i)
    exit()






print(mxdm)


### FIXED CODE ###

h,n = map(int,input().split())
ab = [list(map(int,input().split())) for _ in range(n)]
inf = 10000000000
dp = [inf for _ in range(h+1)]
dp[0] = 0
for i in range(1,h+1):
    m = inf
    for a,b in ab:
        if i <= a:
            m = min(m,b)
        else:
            m = min(m,dp[i-a]+b)
    dp[i] = m
print(dp[-1])
### BUGGY CODE ###

# https://atcoder.jp/contests/abc120/tasks/abc120_d
n, m = map(int, input().split())

brides = []
for _ in range(m):
    a, b = map(int, input().split())
    brides.append((a, b))


class Union:
    def __init__(self, val):
        self.val = val
        self.parent = self
        self.rank = 0

    def get_root(self):
        n = self
        while n.parent != n:
            n = n.parent
        return n

    def find_set(self):
        return self.get_root().val

unions = []
for i in range(n):
    unions.append(Union(i))

def check_no_access(unions):
    roots = [u.find_set() for u in unions]
    counter = 0
    for i in range(len(roots)):
        for j in range(i + 1, len(roots)):
            if roots[i] != roots[j]:
                counter += 1
    return counter

ans = []
ans.append(check_no_access(unions))

for a, b in brides[::-1]:
    x, y = unions[a - 1], unions[b - 1]
    x_root = x.get_root()
    y_root = y.get_root()
    if x_root.rank == y_root.rank:
        y_root.parent = x_root
        x_root.rank += 1
    elif x_root.rank > y_root.rank:
        y_root.parent = x_root
    else:
        x_root.parent = y_root
    ans.append(check_no_access(unions))
ans.pop()
for a in ans[::-1]:
    print(a)

### FIXED CODE ###

# https://atcoder.jp/contests/abc120/tasks/abc120_d
from collections import Counter
n, m = map(int, input().split())

brides = []
for _ in range(m):
    a, b = map(int, input().split())
    brides.append((a, b))


class Union:
    def __init__(self, val):
        self.val = val
        self.parent = self
        self.rank = 0
        self.size = 1

    def get_root(self):
        n = self
        while n.parent != n:
            n = n.parent
        return n

    def find_set(self):
        return self.get_root().val

unions = []
for i in range(n):
    unions.append(Union(i))

ans = []
ans.append(n * (n - 1) // 2)

for a, b in brides[::-1]:
    x, y = unions[a - 1], unions[b - 1]
    x_root = x.get_root()
    y_root = y.get_root()
    if x_root.find_set() == y_root.find_set():
        ans.append(ans[-1])
        continue
    ans.append(ans[-1] - x_root.size * y_root.size)
    if x_root.rank == y_root.rank:
        y_root.parent = x_root
        x_root.rank += 1
        size = x_root.size + y_root.size
    elif x_root.rank > y_root.rank:
        y_root.parent = x_root
    else:
        x_root.parent = y_root
    size = x_root.size + y_root.size
    x_root.size = size
    y_root.size = size
ans.pop()
for a in ans[::-1]:
    print(a)
### BUGGY CODE ###

import sys

input = sys.stdin.readline

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

def lcm(a, b): return a * b // gcd(a, b)

def lcm_list(A):
    l = A[0]
    for a in A[1:]:
        l = lcm(l, a)
    return l

MOD = 10**9 + 7

N = int(input())
*A, = map(int, input().split())
L = lcm_list(A)
ans = 0
for a in A:
    ans = (ans + L // a) % MOD
print(ans)

### FIXED CODE ###

from collections import Counter

def extended_euclid(a, b):
    x1, y1, m = 1, 0, a
    x2, y2, n = 0, 1, b
    while m % n != 0:
        q, r = divmod(m, n)
        x1, y1, m, x2, y2, n = x2, y2, n, x1 - q * x2, y1 - q * y2, r
    return (x2, y2, n)

def modular_inverse(a, mod):
    x, _, g = extended_euclid(a, mod)
    if g != 1:
        return None # Modular inverse of a does not exist
    else:
        return x % mod

def prime_factorization(n):
    '''
    Trial division.
    Input: 
        n : a positive integer
    Output:
        a dictionary of #(each prime factors) of n,
    '''
    result = []
    app = result.append
    if n < 2:
        return Counter()
    while n % 2 == 0:
        app(2)
        n //= 2
    p = 3
    while p*p <= n:
        while n % p == 0:
            app(p)
            n //= p
        p += 2
    if n > 1:
        app(n)
    return Counter(result)

MOD = 10**9 + 7

N = int(input())
*A, = map(int, input().split())
ans = 0
lcm = {}
for a in A:
    for x, y in prime_factorization(a).items():
        if x not in lcm.keys():
            lcm[x] = y
        else:
            lcm[x] = max(lcm[x], y)
L = 1
for x, y in lcm.items():
    L *= pow(x, y, MOD)
    L %= MOD
for a in A:
    ans += L * modular_inverse(a, MOD)
    ans %= MOD
print(ans)
### BUGGY CODE ###

import sys
from collections import deque

sys.setrecursionlimit(10**6)
if sys.platform in (['ios','darwin','win32']):
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return [int(s) for s in input().split()]

N = INT()
A = MAP()

B = deque([])

# print(A, B)

for a in A:
	B.append(a)
	B = deque(reversed(B))
	# print(B)

print(' '.join(map(str, B)))

### FIXED CODE ###

import sys
from collections import deque

sys.setrecursionlimit(10**6)
if sys.platform in (['ios','darwin','win32']):
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return [int(s) for s in input().split()]

N = INT()
A = MAP()

B = deque([])

# print(A, B)

for i in range(N):
	if i%2:
		B.append(A[i])
	else:
		B.appendleft(A[i])
	# print(B)

if not N % 2: B = reversed(B)
print(' '.join(map(str, B)))
### BUGGY CODE ###

N, Q = (int(i) for i in input().split())
S = str(input())
LR = []
for i in range(Q):
  LR.append([int(i) for i in input().split()])

for l,r in LR:
  check_s = S[l-1:r]
  ans = 0
  start_index = 0
  for end_index in range(len(check_s)):
    if check_s[start_index] == "A":
      if check_s[end_index] == "C":
        ans +=1
      else:
        start_index = end_index
    else:
      start_index = end_index

  print(ans)


### FIXED CODE ###

N, Q = (int(i) for i in input().split())
S = str(input())

ac_count = [0] *(N+1)

for i in range(N):
  if S[i:i+2] == "AC":
    ac_count[i+1] = ac_count[i] + 1
  else:
    ac_count[i+1] = ac_count[i]

LR = []
for i in range(Q):
  LR.append([int(i) for i in input().split()])

for l,r in LR:
  ans = ac_count[r-1] - ac_count[l-1]
  print(ans)
### BUGGY CODE ###

import math

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

maxRBox = math.ceil(3000/R)
maxGBox = math.ceil(3000/G)
maxBBox = math.ceil(3000/B)

ans = 0
for ri in range(maxRBox+1):
	if N < ri*R:
		break
	for gi in range(maxGBox+1):
		if N < ri*R+gi*G:
			break
			
		if (N - (ri*R+gi*G)) % B == 0:
			bi = (N - (ri*R+gi*G)) // B
			if ri*R+gi*G+bi*B == N:
				ans +=1
				#print(ri,gi,bi,ri*R+gi*G+bi*B)
				
print(ans)

### FIXED CODE ###

import math
 
R,G,B,N = map(int,input().split())
 
maxRBox = math.ceil(3000/R)
maxGBox = math.ceil(3000/G)
maxBBox = math.ceil(3000/B)
 
ans = 0
for ri in range(maxRBox+1):
	if N < ri*R:
		break
	for gi in range(maxGBox+1):
		if N < ri*R+gi*G:
			break
			
		if (N - (ri*R+gi*G)) % B == 0:
			bi = (N - (ri*R+gi*G)) // B
			if ri*R+gi*G+bi*B == N:
				ans +=1
				#print(ri,gi,bi,ri*R+gi*G+bi*B)
				
print(ans)