Problem:
 Score : 500 points    Problem Statement Given are N positive integers A_1,...,A_N .  Consider positive integers B_1, ..., B_N that satisfy the following condition.  Condition: For any i, j such that 1 \leq i < j \leq N , A_i B_i = A_j B_j holds.  Find the minimum possible value of B_1 + ... + B_N for such B_1,...,B_N .  Since the answer can be enormous, print the sum modulo ( 10^9 +7 ).      Constraints  1 \leq N \leq 10^4  1 \leq A_i \leq 10^6  All values in input are integers.         Input Input is given from Standard Input in the following format:  N  A_1  ...  A_N       Output Print the minimum possible value of B_1 + ... + B_N for B_1,...,B_N that satisfy the condition, modulo ( 10^9 +7 ).        Sample Input 1 3
2 3 4      Sample Output 1 13  Let B_1=6 , B_2=4 , and B_3=3 , and the condition will be satisfied.       Sample Input 2 5
12 12 12 12 12      Sample Output 2 5  We can let all B_i be 1 .       Sample Input 3 3
1000000 999999 999998      Sample Output 3 996989508  Print the sum modulo (10^9+7) .

Solution (Python):
from collections import defaultdict
n = int(input())
a = list(map(int,input().split()))
MOD = 10**9+7
def prime_table(n):
  if n <= 1:
    return [],[],[]
  prime = [2]
  limit = int(n**0.5)
  data = [i+1 for i in range(2,n,2)]
  isprime = [0]*(n+1)
  isprime[2] = 1
  min_factor = [0 if i%2 != 0 else 2 for i in range(n+1)]
  while True:
    p = data[0]
    prime.append(p)
    isprime[p] = 1
    pdata,data = data,[]
    for e in pdata:
      if e%p != 0:
        data.append(e)
      else:
        min_factor[e] = p
    if limit <= p:
      for i in data:
        isprime[i] = 1
        min_factor[i] = i
      return prime + data,isprime,min_factor
def modinv(a,m=MOD):
  b,u,v = m,1,0
  while b:
    t = a//b
    a,u = a-t*b,u-t*v
    a,b,u,v = b,a,v,u
  u %= m
  if u < 0:
    u += m
  return u
ma = max(a)
data,isprime,min_factor = prime_table(ma)
prime = [0] * (ma+1)
for i in a:
  if i == 1:
    continue
  d = defaultdict(int)
  while isprime[i] == 0:
    d[min_factor[i]] += 1
    i = i // min_factor[i]
  d[i] += 1
  for j,k in d.items():
    prime[j] = max(prime[j],k)
lcm = 1
for i in range(ma+1):
  if prime[i] != 0:
    lcm = (lcm*pow(i,prime[i],MOD))%MOD
c = 0
for i in a:
  c += lcm*modinv(i,MOD)
  c %= MOD
print(c)

Solution (Python):
import fractions
from functools import reduce


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


def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)


def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)
N = int(input())
Alist = list(map(int, input().split()))
l = lcm_list(Alist)
ans = 0
for a in Alist:
    ans += l//a
print(ans%(10**9+7))

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

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

mod = 10**9+7
n = int(input())
a = list(map(int,input().split()))
L = a[0]
for i in a:
    L = lcm(L,i)
    
ans = 0
for i in a:
    ans += (L // i )
print(ans % mod)

Solution (Python):
from fractions import gcd
from functools import reduce


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

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)


def main():
    N = int(input())
    A = list(map(int, input().split()))
    MOD = 10 ** 9 + 7
    com = lcm_list(A) % MOD
    ans = 0
    for a in A:
        ans += com * pow(a, MOD - 2, MOD)
    ans %= MOD
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
from fractions import gcd


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


n = int(input())
a = list(map(int, input().split()))
mod = 10 ** 9 + 7
MAX = 10 ** 6

l = 1
for e in a:
    l = lcm(l, e)

l %= mod

inv = [1] * (MAX + 1)
for i in range(2, MAX + 1):
    inv[i] = inv[mod % i] * (mod - mod // i) % mod

ans = 0
for e in a:
    ans += l * inv[e]
    ans %= mod

print(ans)

Solution (Python):
from fractions import gcd


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


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

l = 1
for e in a:
    l = lcm(l, e)

l %= mod

ans = 0
for e in a:
    ans += l * pow(e, mod - 2, mod)
    ans %= mod

print(ans)

Solution (Python):
from fractions import gcd
from functools import reduce

MOD = 1000000007

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

n = int(input())
a = [int(_) for _ in input().split()]
LCM = reduce(lcm, a)

arr = [LCM // _ for _ in a]
print(sum(arr) % MOD)

Solution (Python):
MAX_PRIME = 10**3
is_prime = [1] * MAX_PRIME
primes = []
is_prime[0] = 0
is_prime[1] = 0
for i in range(MAX_PRIME):
    if is_prime[i]:
        primes.append(i)
        for j in range(2, ((MAX_PRIME-1)//i) + 1):
            is_prime[i*j] = 0

def factorization(n):
    factor = {}
    for p in primes:
        if p ** 2 > n:
            break
        while n % p == 0:
            n //= p
            if p not in factor:
                factor[p] = 1
            else:
                factor[p] += 1
    if n > 1:
        factor[n] = 1
    return factor
def extGCD(a, b):
    if b == 0:
        return a, 1, 0
    g, y, x = extGCD(b, a%b)
    y -= a//b * x
    return g, x, y
def moddiv(a, b):
    _, inv, _ = extGCD(b, law)
    return a * inv % law

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

ans = 0
l = {}
lmod = 1
law = 10 ** 9 + 7
for x in a:
    fx = factorization(x)
    for p, c in fx.items():
        if p not in l:
            ans *= p ** c
            lmod *= p ** c
            ans %= law
            lmod %= law
            l[p] = c
        elif c > l[p]:
            ans *= p ** (c - l[p])
            lmod *= p ** (c - l[p])
            ans %= law
            lmod %= law
            l[p] = c
    b = moddiv(lmod, x)
    ans += b
    ans %= law
print(ans)

Solution (Python):
def pow(x, n, mod):
    ret = 1
    while n > 0:
        if n % 2 == 1:
            ret = ret * x % mod
        x = x * x % mod
        n >>= 1
    return ret
def gcd(x,y):
    a,b = max(x,y),min(x,y)
    r = a % b
    while r != 0:
        a,b = b,r
        r = a % b
    return b
mod = 10**9+7
N = int(input())
a = list(map(int,input().split()))
g = a[0]
l = g
for i in range(1,N):
    g = gcd(l, a[i])
    l = (l*a[i])//g
ans = 0
l %= mod
for i in range(N):
    tmp = (pow(a[i], mod-2, mod)*l)%mod
    ans = (ans+tmp)%mod
print(ans%mod)

Solution (Python):









from fractions import gcd
n = int(input())

a = list(map(int, input().split()))
mod = 10**9 + 7


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

l = 1
for i in range(n):
    l = lcm(l,a[i])

ans = 0
for i in range(n):
    ans += l // a[i]

ans %= mod
print(ans)

Solution (Python):



import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def factorization(n: int):
    if n == 1:
        return []  
    
    arr = []
    temp = n
    for i in range(2, int(n**0.5) + 1):  
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append((i, cnt))

    if temp != 1:
        arr.append((temp, 1))

    if arr == []:
        arr.append((n, 1))

    return arr


MOD = 10**9 + 7

from collections import defaultdict, Counter, deque
from fractions import gcd


def ret_inv(a, p):
    return pow(a, p - 2, p)


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


N = read_a_int()
A = read_ints()

flat = defaultdict(lambda: 0)  
for a in A:  
    tmp = factorization(a)
    for k, v in tmp:
        flat[k] = max(flat[k], v)

flat_mod = 1
for k, v in flat.items():
    flat_mod *= pow(k, v, MOD)
    if flat_mod >= MOD:
        flat_mod %= MOD

ans = 0
for a in A:
    ans += flat_mod * ret_inv(a, MOD)
    if ans >= MOD:
        ans %= MOD
print(ans)

Solution (Python):
from fractions import gcd
import collections
from collections import defaultdict



def modinv(a, m):
    b = m
    u = 1
    v = 0
    while b:
        t = int(a / b)
        a -= t * b
        a, b = b, a
        u -= t * v
        u, v = v, u
    u %= m
    if u < 0:
        u += m
    return u
    

def pow_k_mod(x, n, m):
    """
    O(log n)
    """
    if n == 0:
        return 1

    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
            K %= m
        x *= x
        x %= m
        n //= 2

    return (K * x) % m
    
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

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

factor = defaultdict(lambda: -1)
for i in range(N):
    c = collections.Counter(prime_factorize(A[i]))
    for k, v in c.items():
        factor[k] = max(factor[k], v)

lcm = 1
for k, v in factor.items():
    lcm *= pow_k_mod(k, v, int(1e9+7))
    lcm %= int(1e9+7)

print(sum([(lcm * modinv(x, int(1e9+7)) % int(1e9+7)) for x in A]) % int(1e9+7))

Solution (Python):
import math

def pow_k(x, n, mod):
  if n == 0:
    return 1

  K = 1
  while n > 1:
    if n % 2 != 0:
      K = (x * K) % mod
        
    x = (x * x) % mod

    n //= 2

  return (x * K) % mod

def prime_fuctorization(n):
  result = {}
  count = 0
  while n % 2 == 0:
    n //= 2
    count += 1
    
  if count != 0:
    result[2] = count
  
  for i in range(3, n, 2):
    count = 0
    while n % i == 0:
      n //= i
      count += 1
    
    if count != 0:
      result[i] = count
      
    if math.sqrt(n) <= i:
      break
      
  if n != 1:
    result[n] = 1
    
  return result
    
MOD = 10 ** 9 + 7
n = int(input())
a = list(map(int, input().split()))

soinsu = []
result = {}
for i in range(n):
  dic = prime_fuctorization(a[i])
  soinsu.append(dic)
  
  for k in dic.keys():
    item = dic[k]
    if item >= result.get(k, 0):
      result[k] = item
      
m = 1
tmp = 1
for k, v in result.items():
  m *= pow_k(k, v, MOD)
  tmp *= k ** v
  m %= MOD
  
ans = 0
for i in range(n):
  ans += m * pow_k(a[i], MOD-2, MOD)
  ans %= MOD
  
print(ans)

Solution (Python):
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))
n = ii()
a = li()
aco = a
aco = list(set(aco))
lis = [0]*(10**3)
rootn = 10**3
for i in range(len(aco)):
    for nm in range(2,rootn):
        if aco[i] % nm != 0:
            continue
        ima = 0
        while(aco[i]%nm == 0):
            ima += 1
            aco[i] = aco[i] //nm
        lis[nm] = max(lis[nm],ima)
aco = list(set(aco))
mod = 10**9 + 7
gcd = 1
for i in range(2,rootn):
    gcd *= (i ** lis[i]) % mod
for i in range(len(aco)):
    gcd *= aco[i] % mod

ans = 0
for i in range(n):
    ans += pow(a[i],mod-2,mod) * gcd % mod
print(ans% mod)

Solution (Python):
from collections import defaultdict
from functools import lru_cache
import math


def trial_division(n):
    factor = defaultdict(int)
    tmp = int(math.sqrt(n)) + 1
    for num in range(2, tmp):
        while n % num == 0:
            n //= num
            factor[num] += 1
    factor[n] += 1
    return factor


@lru_cache(maxsize=None)
def powmod(x, y, mod):
    if y == 0:
        return 1
    return (((powmod(x, y >> 1, mod) ** 2) % mod) * x ** (y & 1)) % mod


n = int(input())
a = list(map(int, input().split()))
mod = 10**9 + 7
numbers = defaultdict(int)
for a_i in a:
    for i, v in trial_division(a_i).items():
        numbers[i] = max(v, numbers[i])

l = 1
for i, v in numbers.items():
    l *= powmod(i, v, mod)
    l %= mod


ans = 0
for i in a:
    r = powmod(i, mod-2, mod)
    ans += l * r
    ans %= mod
print(int(ans))

Solution (Python):
from fractions import gcd
MOD=10**9+7
def lcm(x,y):return x*y//gcd(x,y)
def inv(x):return pow(x,MOD-2,MOD)
def main():
  n,*a=map(int,open(0).read().split())
  L=1
  for i in a:L=lcm(L,i)
  L=L%MOD
  ans=0
  for i in a:ans=(ans+L*inv(i))%MOD  
  print(ans)
main()

Solution (Python):
from fractions import gcd
def lcm(x,y):return x*y//gcd(x,y)
def inv(x):return pow(x,MOD-2,MOD)
MOD=10**9+7
def main():
  n,*a=map(int,open(0).read().split())
  L=1
  for i in a:L=lcm(L,i)
  L=L%MOD
  ans=0
  for i in a:ans=(ans+L*inv(i))%MOD  
  print(ans)
main()

Solution (Python):
n,*a=map(int,open(0).read().split())
MOD=10**9+7
from fractions import gcd

def lcm(x,y):return x*y//gcd(x,y)
def inv(x):return pow(x,MOD-2,MOD)

L=1
for i in a:L=lcm(L,i)
L=L%MOD
ans=0
for i in a:ans=(ans+L*inv(i))%MOD
  
print(ans)

Solution (Python):

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

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

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

def inv(x):
  return pow(x,MOD-2,MOD)

L=1
for i in a:
  L=lcm(L,i)

L=L%MOD
ans=0
for i in a:
  ans=(ans+L*inv(i))%MOD
  

print(ans)

Solution (Python):

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

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

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

def inv(x):
  return pow(x,MOD-2,MOD)

L=1
for i in a:
  L=lcm(L,i)

L=L%MOD
ans=0
for i in a:
  ans=(ans+L*inv(i))%MOD
  

print(ans)

Solution (Python):
import fractions
from functools import reduce
def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)
def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)
n=int(input())
a=list(map(int,input().split()))
b=0
l=lcm_list(a)
for i in range(n):
    b+=l//a[i]
print(b%(10**9+7))

Solution (Python):
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n = inp()
a = inpl()
def lcm(a,b):
    return a*b//fractions.gcd(a,b)
r = 1

for i in a:
    r = lcm(i,r)
r %= mod
res = 0
for i in a:
    res += r*pow(i,mod-2,mod)
    res %= mod
print(res)

Solution (Python):
def g(a, b):
    m = a * b
    if a < b:
        a, b = b, a
    while True:
        a, b = b, (a % b)
        if b == 0:
            return m // a    
        
N = int(input())
A = list(map(int,input().split()))
MOD = 10 ** 9 + 7
ans = 0
c = 1
for i in range(N):
    c = g(c, A[i])
for i in range(N):
    ans += c // A[i]
print(ans % MOD)

Solution (Python):
from fractions import gcd
import math
n = int(input())
a = list(map(int, input().split()))
MOD=10**9+7
lcm=1
for i in range(n):
    lcm*=a[i]//gcd(lcm,a[i])
res=0
for i in range(n):
    res+=lcm//a[i]
print(res%MOD)

Solution (Python):
import math
import fractions
import functools
def main():
    n = int(input())
    a = [int(t)for t in input().split()]

    M = 10**9+7
    culcm = functools.reduce(lcm,a)

    b = [culcm//a_i for a_i in a]

    print(sum(b)%M)

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

if __name__ == "__main__":
    main()

Solution (Python):
from collections import *
from itertools import *
from bisect import *
from heapq import *
import copy
import math
from fractions import gcd
def sosuu(n):
    arr = []
    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.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr


N=int(input())
A=list(map(int,input().split()))
mod=10**9+7
M=1
dic={}
for a in A:
    arr=sosuu(a)
    for b,c in arr:
        if b in dic:
            if c>dic[b]:
                M=M*pow(b,c-dic[b],mod)%mod
                dic[b]=c
        else:
            dic.update({b:c})
            M=M*pow(b,c,mod)%mod
M%=mod
print(sum([M*pow(a,mod-2,mod)%mod for a in A])%mod)

Solution (Python):
from collections import *
from itertools import *
from bisect import *
from heapq import *
import copy
import math
from fractions import gcd
def factorization(n):
    arr = []
    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.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

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

M=1

dic={}

for a in A:
    Z=1
    arr=factorization(a)
    for b,c in arr:
        if b in dic:
            if c>dic[b]:
                M=M*pow(b,c-dic[b],mod)%mod
                dic[b]=c
        else:
            dic.update({b:c})
            M=M*pow(b,c,mod)%mod
M%=mod

print(sum([M*pow(a,mod-2,mod)%mod for a in A])%mod)

Solution (Python):
from fractions import gcd
N=int(input())
A=list(map(int,input().split()))
mod=10**9+7
M=1
for a in A:
    M=((M * a) // gcd(M, a))
M%=mod

count=0

for a in A:
    count=(count+M*pow(a,mod-2,mod))%mod
print(count)

Solution (Python):
from fractions import gcd
N=int(input())
A=list(map(int,input().split()))
mod=10**9+7
M=1
for a in A:
    M=((M * a) // gcd(M, a))
M%=mod

print(sum([M*pow(a,mod-2,mod)%mod for a in A])%mod)

Solution (Python):
from collections import *
from itertools import *
from bisect import *
from heapq import *
import copy
import math
from fractions import gcd
N=int(input())
A=list(map(int,input().split()))
mod=10**9+7
M=1
for a in A:
    M=((M * a) // gcd(M, a))
M%=mod

print(sum([M*pow(a,mod-2,mod)%mod for a in A])%mod)

Solution (Python):
import fractions
MOD = 1000000007

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


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


x = A[0]
for a in A:
    x = get_lcm(a, x)


ret = 0
for a in A:
    ret += x // a

print(ret % MOD)

Solution (Python):
def kouyaku(a,b):
    aa = max(a,b)
    bb = min(a,b)
    if bb == 0:
        return aa
    else:
        return kouyaku(bb,aa%bb)

def power(a, b):
	if b == 0:
		return 1
	elif b == 1:
		return a % 1000000007
	elif b % 2 == 0:
		return (power(a, b//2) ** 2) % 1000000007
	else:
		return (power(a, b//2) ** 2 * a) % 1000000007
 
def divide(a, b):
	return (a * power(b, 1000000005)) % 1000000007

def prime(x):
    if x < 2: return []

    primes = [i for i in range(x)]
    primes[1] = 0 

    
    for prime in primes:
        if prime > x**(1/2): break
        if prime == 0: continue
        for non_prime in range(2 * prime, x, prime): primes[non_prime] = 0

    return [prime for prime in primes if prime != 0]

primes = prime(10**6)
pd = {}
for i in range(len(primes)):
	pd[primes[i]] = i
MOD = 10**9+7
N = int(input())
A = [int(i) for i in input().split()]
K = [0]*len(primes)
for i in range(N):
	a = A[i]
	for i in range(len(primes)):
		p = primes[i]
		if a == 1:
			break
		elif p > 1000:
			K[pd[a]] = 1
			break
		else:
			cou = 0
			while a%p==0:
				a = a//p
				cou += 1
			K[i] = max(cou, K[i])
kv = 1
for i in range(len(primes)):
	kv *= power(primes[i], K[i])
	kv %= MOD
ans = 0
for i in range(N):
	ans += divide(kv, A[i])
	ans %= MOD
print(ans)

Solution (Python):
from copy import deepcopy

N = int(input())
A = list(map(int, input().split()))
B = deepcopy(A)
mod = 10**9+7

"""
普通に最小公倍数を計算すると桁数が莫大になって
桁溢れor多倍長整数を使っても計算が一気に遅くなるのがこの問題のミソ

桁数の大きい数は素因数分解の形で保持すると高速にmod計算が可能なので、これを用いる。
まずは1000以下の素数テーブルを用意。
"""
prime = [i for i in range(2, 10**3)]
for p in prime:
    prime = [x for x in prime if (x == p or x % p != 0)]

def div(a, n):
    """
    自然数aがnで何回割れるかと、割り尽くした残りを返す
    """
    num = 0
    while a % n == 0:
        num += 1
        a = a // n
    return num, a

"""
素数pごとに、各A[i]がpで何回割れるかを求め、iでループを回した中での最大値をe_pとすると
A[0],...A[N-1]の最小公倍数はL = ¥Prod_p p^{e_p}になる。
これならmodで桁数削減が可能。

ただし素数テーブルは1000までしか用意してないので、それ以上の素数はリストAの中に吐き出させ、
あとでそれをLに組み込む。
"""
L = 1
for p in prime:
    e = 0
    for i in range(N):
        cand, A[i] = div(A[i], p)
        e = max(e, cand)
    L *= pow(p, e, mod)
    L %= mod
for a in set(A):
    L *= a
    L %= mod

"""
あとは答えを求めるのみ。
ただしLをmodで算出しているので、単純にL/A[i]を加算すると答えが狂う。
そこでA[i]^{-1}をmodで求めてLに乗算する。
"""
ans = 0
for i in range(N):
    inv = pow(B[i], mod - 2, mod)
    ans += L * inv
    ans %= mod
print(ans)

Solution (Python):
class PrimeOptimizer:
    def __init__(self, MAX_NUM=10**3):
        is_prime = [True] * MAX_NUM
        is_prime[0] = False
        is_prime[1] = False
        primes = []
        for i in range(MAX_NUM):
            if is_prime[i]:
                primes.append(i)
                for j in range(2*i, MAX_NUM, i):
                    is_prime[j] = False
        self.primes = primes

    def prime_factorization(self, x):
        res = {}
        for prime in self.primes:
            while x % prime == 0:
                if not prime in res:
                    res[prime] = 0
                res[prime] += 1
                x //= prime
        if x > 1:
            res[x] = 1
        return res

MOD = 10**9+7

def mod_pow(p, q):
    res = 1
    while q:
        if q & 1:
            res = (res * p) % MOD
        p = (p * p) % MOD
        q //= 2
    return res

def mod_inv(p):
    return mod_pow(p, MOD - 2)

def solve(n, a):
    primeOpt = PrimeOptimizer()
    D = {}
    for i in range(n):
        prime_num_mapping = primeOpt.prime_factorization(a[i])
        for prime, num in prime_num_mapping.items():
            if not prime in D:
                D[prime] = 0
            D[prime] = max(D[prime], num)
    L = 1
    for prime, num in D.items():
        L = (L * mod_pow(prime, num)) % MOD
    res = sum([L * mod_inv(x) % MOD for x in a])
    return res % MOD

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

Solution (Python):
import math
import fractions
def lcm(x, y):
  return (x * y) // fractions.gcd(x, y)
  
def main():
  mod = 10**9 +7
  n = int(input())
  ls = list(map(int,input().split()))
  
  t = ls[0]
  for a in ls:
    t = lcm(t,a)
  
  ans = 0
  for a in ls:
    ans += t//a
  print(ans%mod)
  
if __name__ == '__main__':
  main()

Solution (Python):
import math
import fractions
def lcm(x, y):
  return (x * y) // fractions.gcd(x, y)

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

MODp = 1000000007
K = 1
for i in range(N):
  K = lcm(K,l[i])

Ans = 0
for i in range(N):
  Ans += ((K // l[i]))

Ans = Ans % MODp
print(Ans)

Solution (Python):
import fractions
from functools import reduce


MAX = 10**6+1
mod = 1000000007
prime = [0 for i in range(MAX)] 
max_map = dict() 

def power(a, n):
	if n == 0: 
		return 1
	p = power(a, n // 2) % mod
	p = (p * p) % mod
	if n & 1: 
		p = (p * a) % mod
	return p 



def sieve(): 
	prime[0], prime[1] = 1, 1
	for i in range(2, MAX): 
		if prime[i] == 0: 
			for j in range(i * 2, MAX, i): 
				if prime[j] == 0: 
					prime[j] = i 
			prime[i] = i 


def lcmModuloM(arr, n): 
	for i in range(n): 
		num = arr[i] 
		temp = dict() 
		
		
		while num > 1:
			
			
			factor = prime[num]
			
			if factor in temp.keys():
				temp[factor] += 1
			else:
				temp[factor] = 1
			
			num = num // factor
		for i in temp:
			
			
			if i in max_map.keys():
				max_map[i] = max(max_map[i], temp[i])
			else: 
				max_map[i] = temp[i]
	ans = 1
	for i in max_map:
		ans = (ans * power(i, max_map[i])) % mod
	return ans

sieve()
X = int(input())
A = list(map(int,input().split()))
N = max(A)
value = lcmModuloM(A, X)
ans = 0
for i in range(X):
    ans += value*pow(A[i], mod-2, mod)%mod
print(ans%mod)

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

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

l = 1
for i in a:
    l = lcm(i,l)
    
ans = 0
for i in a:
    ans += l//i
    
print(ans%(10**9+7))

Solution (Python):
import sys
def input():
    return sys.stdin.readline()[:-1]
mod=10**9+7
N=int(input())
A=list(map(int,input().split()))
pr=[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 
71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 
313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 
787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997]
pl=[0]*168
l=[[] for i in range(N)]
for i in range(N):
    t=A[i]
    for j,p in enumerate(pr):
        c=0
        while 1:
            if t%p:
                break
            t//=p
            l[i].append(j)
            c+=1
        if c>pl[j]:
            pl[j]=c
    if t>1:
        pr.append(t)
        l[i].append(len(pl))
        pl.append(1)
lcm=1
for i,p in enumerate(pl):
    lcm=(lcm*pow(pr[i],p,mod))%mod
ipr=[]
for i in pr:
    ipr.append(pow(i,mod-2,mod))
a=0
for i in l:
    t=lcm
    for j in i:
        t=(t*ipr[j])%mod
    a=(a+t)%mod
print(a)

Solution (Python):
MOD = int(1e9+7)

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a%b)

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


N = int(input())
A = [int(i) for i in input().split()]

l = 1
for i in range(N):
    l = lcm(l, A[i])

ans = 0
for i in range(N):
    ans += l // A[i]

print(ans % MOD)

Solution (Python):
N = int(input())
A = [int(i) for i in input().split()]

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a%b)

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

l = 1
for i in range(N):
    l = lcm(l, A[i])

ans = 0
MOD = int(1e9+7)
for i in range(N):
    ans += l // A[i]

print(ans % MOD)

Solution (Python):
import fractions
n = int(input())
a = list(map(int, input().split()))
l = a[0]
for i in range(1, n): l = l // fractions.gcd(l, a[i]) * a[i]
s = 0
for i in range(n): s += l // a[i]
print(s % 1000000007)

Solution (Python):
input();a=list(map(int,input().split()))
import fractions as f
l,r=a[0],1
for i in range(1,len(a)):
  g=f.gcd(l,a[i])
  s,t=l//g,a[i]//g
  l,r=s*t*g,(r*t+s)%(10**9+7)
print(r)

Solution (Python):
M=10**9+7
n=int(input())
a=list(map(int,input().split()))
import fractions as f
l,r=a[0],1
for i in range(1,n):
  g=f.gcd(l,a[i])
  s,t=l//g,a[i]//g
  l,r=s*t*g,(r*t+s)%M
print(r)

Solution (Python):
M=10**9+7
n=int(input())
a=list(map(int, input().split()))
import fractions as f
l,r=a[0],1
for i in range(1,n):
  g=f.gcd(l,a[i])
  s,t=l//g,a[i]//g
  l,r=s*t*g,(r*t+s)%M
print(r)

Solution (Python):
M=10**9+7
n=int(input())
a=list(map(int, input().split()))
def f(x, y):
  while y: x,y=y,x%y
  return x
l,r=a[0],1
for i in range(1,n):
  g=f(l,a[i])
  s,t=l//g,a[i]//g
  l,r=s*t*g,(r*t+s)%M
print(r)

Solution (Python):
from functools import reduce
from fractions import gcd
n=int(input())
A=list(map(int,input().split()))
lc=reduce(lambda a,b: a*b//gcd(a,b),A)
b=[lc//i for i in A]
print(sum(b)%(1000*1000000+7))

Solution (Python):
import fractions

def main():
    mod = 10**9+7
    N = int(input())
    A = list(map(int,input().split()))
    lcm = 1
    for Ai in A:
        lcm = lcm*Ai//fractions.gcd(lcm,Ai)
    lcm %= mod
    ans = 0
    for Ai in A:
        ans += lcm*pow(Ai,mod-2,mod)%mod
        ans %= mod
    print(ans)
    
if __name__ == '__main__':
    main()

Solution (Python):
class PrimeOptimizer:
    def __init__(self, MAX_NUM=10**3):
        is_prime = [True] * MAX_NUM
        is_prime[0] = False
        is_prime[1] = False
        primes = []
        for i in range(MAX_NUM):
            if is_prime[i]:
                primes.append(i)
                for j in range(2*i, MAX_NUM, i):
                    is_prime[j] = False
        self.primes = primes

    def prime_factorization(self, x):
        res = {}
        for prime in self.primes:
            while x % prime == 0:
                if not prime in res:
                    res[prime] = 0
                res[prime] += 1
                x //= prime
        if x > 1:
            res[x] = 1
        return res

MOD = 10**9+7

def mod_pow(p, q):
    res = 1
    while q:
        if q & 1:
            res = (res * p) % MOD
        p = (p * p) % MOD
        q //= 2
    return res

def mod_inv(p):
    return mod_pow(p, MOD - 2)

def solve(n, a):
    primeOpt = PrimeOptimizer()
    D = {}
    for i in range(n):
        prime_num_mapping = primeOpt.prime_factorization(a[i])
        for prime, num in prime_num_mapping.items():
            if not prime in D:
                D[prime] = 0
            D[prime] = max(D[prime], num)
    L = 1
    for prime, num in D.items():
        L = (L * mod_pow(prime, num)) % MOD
    res = sum([L * mod_inv(x) % MOD for x in a])
    return res % MOD

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

Solution (Python):

max_A = 1000000

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

sieve = [0] * (max_A + 1)
sieve[0] = -1
sieve[1] = -1
for i in range(2, max_A + 1):
    if sieve[i] != 0:
        continue
    sieve[i] = i
    for j in range(i * i, max_A + 1, i):
        if sieve[j] == 0:
            sieve[j] = i

lcm_factors = {}
for i in range(N):
    t = []
    a = A[i]
    while a != 1:
        if len(t) != 0 and t[-1][0] == sieve[a]:
            t[-1][1] += 1
        else:
            t.append([sieve[a], 1])
        a //= sieve[a]
    for k, v in t:
        if k not in lcm_factors or lcm_factors[k] < v:
            lcm_factors[k] = v

lcm = 1
for k in lcm_factors:
    for i in range(lcm_factors[k]):
        lcm *= k
        lcm %= 1000000007

result = 0
for i in range(N):
    result += lcm * pow(A[i], 1000000007-2, 1000000007)
    result %= 1000000007
print(result)

Solution (Python):
import sys
input=sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))

from functools import reduce
import fractions
def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)
def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)
num=lcm_list(a)
ans=0
for tmp in a:
    ans+=num//tmp
print(ans%(10**9+7))

Solution (Python):






import math
from functools import lru_cache





MOD = 10**9 +7
INF = float('inf')





kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

def factorization(n):
    arr = []
    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.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])
    return arr





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

LCM = {}

for i in l:
  fact = factorization(i)
  for j in fact:
    if j[0] not in LCM:
      LCM[j[0]] = j[1]
    else:
      if LCM[j[0]] < j[1]:
         LCM[j[0]] = j[1]

lcm = 1
for i in LCM:
  lcm = lcm * pow(i,LCM[i],MOD) % MOD

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

print(ans)