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):
import collections
import sys

input = sys.stdin.readline

ri = lambda: int(input())
rs = lambda: input().rstrip()
ril = lambda: list(map(int, input().split()))
rsl = lambda: input().rstrip().split()
ris = lambda n: [ri() for _ in range(n)]
rss = lambda n: [rs() for _ in range(n)]
rils = lambda n: [ril() for _ in range(n)]
rsls = lambda n: [rsl() for _ in range(n)]


def eratosthenes(n):
    sieve = [True for _ in range(n + 1)]
    sieve[0] = False
    sieve[1] = False

    def _update(p):
        if sieve[p]:
            for i in range(p * 2, n + 1, p):
                sieve[i] = False

    if n > 1:
        _update(2)
    p = 3
    while p * p <= n:
        _update(p)
        p += 2
    return sieve


def factorize(n, primes):
    import collections
    if n < 2:
        return dict()
    counter = collections.Counter()
    for p in primes:
        while n % p == 0:
            counter[p] += 1
            n //= p
        if n == 1:
            break
    if n > 1:
        counter[n] += 1
    return counter


MOD = 10**9 + 7

n = ri()
ls = ril()
if n == 1:
    print(1)
    exit()

sieve = eratosthenes(10**3)
primes = [x for x, b in enumerate(sieve) if b]

lcm = collections.Counter()
for x in ls:
    counter = factorize(x, primes)
    for p, k in counter.items():
        lcm[p] = max(lcm[p], k)
lcm_val = 1
for p, k in lcm.items():
    lcm_val *= pow(p, k, MOD)
    lcm_val %= MOD

res = 0
for x in ls:
    res += lcm_val * pow(x, MOD - 2, MOD)
    res %= MOD
print(res)

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

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

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

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

ans = 0
for i in range(n):
  ans += t//l[i]
ans %= 10**9+7

print(ans)

Solution (Python):
import collections
import sys

input = sys.stdin.readline

ri = lambda: int(input())
rs = lambda: input().rstrip()
ril = lambda: list(map(int, input().split()))
rsl = lambda: input().rstrip().split()
ris = lambda n: [ri() for _ in range(n)]
rss = lambda n: [rs() for _ in range(n)]
rils = lambda n: [ril() for _ in range(n)]
rsls = lambda n: [rsl() for _ in range(n)]


def factorize_all(n):
    factorizations = [None] * (n + 1)
    factorizations[0] = dict()
    factorizations[1] = dict()
    for p in range(2, n + 1):
        if factorizations[p] is None:
            for k in range(1, n // p + 1):
                if factorizations[k] is None:
                    continue
                fs = factorizations[k].copy()
                if p in fs:
                    fs[p] += 1
                else:
                    fs[p] = 1
                factorizations[k * p] = fs
    return factorizations


MOD = 10**9 + 7

n = ri()
ls = ril()
if n == 1:
    print(1)
    exit()

factorizations = factorize_all(max(ls))

lcm = collections.Counter()
for x in ls:
    counter = factorizations[x]
    for p, k in counter.items():
        lcm[p] = max(lcm[p], k)
lcm_val = 1
for p, k in lcm.items():
    lcm_val *= pow(p, k, MOD)
    lcm_val %= MOD

res = 0
for x in ls:
    res += lcm_val * pow(x, MOD - 2, MOD)
    res %= MOD
print(res)

Solution (Python):
import collections
import sys

input = sys.stdin.readline

ri = lambda: int(input())
rs = lambda: input().rstrip()
ril = lambda: list(map(int, input().split()))
rsl = lambda: input().rstrip().split()
ris = lambda n: [ri() for _ in range(n)]
rss = lambda n: [rs() for _ in range(n)]
rils = lambda n: [ril() for _ in range(n)]
rsls = lambda n: [rsl() for _ in range(n)]


def factorize_all(n):
    factorizations = [None] * (n + 1)
    factorizations[0] = dict()
    factorizations[1] = dict()
    for p in range(2, n + 1):
        if factorizations[p] is None:
            for k in range(1, n // p + 1):
                if factorizations[k] is None:
                    continue
                fs = factorizations[k].copy()
                if p in fs:
                    fs[p] += 1
                else:
                    fs[p] = 1
                factorizations[k * p] = fs
    return factorizations


MOD = 10**9 + 7

n = ri()
ls = ril()
if n == 1:
    print(1)
    exit()

factorizations = factorize_all(max(ls))

lcm = collections.Counter()
for x in ls:
    counter = factorizations[x]
    for p, k in counter.items():
        lcm[p] = max(lcm[p], k)
lcm_val = 1
for p, k in lcm.items():
    lcm_val *= pow(p, k, MOD)
    lcm_val %= MOD

res = 0
for x in ls:
    res += lcm_val * pow(x, MOD - 2, MOD)
    res %= MOD
print(res)

Solution (Python):
import collections
import sys

input = sys.stdin.readline

ri = lambda: int(input())
rs = lambda: input().rstrip()
ril = lambda: list(map(int, input().split()))
rsl = lambda: input().rstrip().split()
ris = lambda n: [ri() for _ in range(n)]
rss = lambda n: [rs() for _ in range(n)]
rils = lambda n: [ril() for _ in range(n)]
rsls = lambda n: [rsl() for _ in range(n)]


def factorize_all(n):
    factorizations = [None] * (n + 1)
    factorizations[0] = dict()
    factorizations[1] = dict()
    for p in range(2, n + 1):
        if factorizations[p] is None:
            for k in range(1, n // p + 1):
                if factorizations[k] is None:
                    continue
                fs = factorizations[k].copy()
                if p in fs:
                    fs[p] += 1
                else:
                    fs[p] = 1
                factorizations[k * p] = fs
    return factorizations


MOD = 10**9 + 7

n = ri()
ls = ril()
if n == 1:
    print(1)
    exit()

factorizations = factorize_all(max(ls))

lcm = collections.Counter()
for x in ls:
    counter = factorizations[x]
    for p, k in counter.items():
        lcm[p] = max(lcm[p], k)
lcm_val = 1
for p, k in lcm.items():
    lcm_val *= pow(p, k, MOD)
    lcm_val %= MOD

pinvs = {p: pow(p, MOD - 2, MOD) for p in lcm}
res = 0
for x in ls:
    counter = factorizations[x]
    s = 1
    for p, k in counter.items():
        s *= pow(pinvs[p], k, MOD)
    res += lcm_val * s % MOD
    res %= MOD
print(res)

Solution (Python):
n = int(input())
l = list(map(int, input().split()))
mod = 10**9 + 7
def gcd(a,b):
  while b: a,b = b,a%b
  return a
lcm = lambda a,b: a*b//gcd(a,b)
t = 1
for x in l: t = lcm(t,x)
print(sum(t//x for x in l)%mod)

Solution (Python):
n = int(input())
l = list(map(int, input().split()))
t = 1; mod = 10**9 + 7
def gcd(a,b):
  while b: a,b = b,a%b
  return a
lcm = lambda a,b: a*b//gcd(a,b)
for x in l: t = lcm(t,x)
print(sum(t//x for x in l)%mod)

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())
l = list(map(int, input().split(" ")))

p = lcm_list(l)
c = 0
z = 10 ** 9 + 7
for i in l:
  c += p // i
print(c % z)

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 7)

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

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

def lcm(a):    
    x = a[0]
    for i in range(1, len(a)):
        x = (x * a[i]) // gcd(x, a[i])
    return x

N = ir()
A = lr()
A.sort()
if N == 1:
    print(1)
    exit()
MOD = 10 ** 9 + 7
l = []
first = A[0]
l = [x//gcd(x, first) for x in A[1:]]
x = lcm(l) 
answer = x%MOD

for i in range(1, N):
    answer += first * x // A[i]

print(answer%MOD)

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 7)

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

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

def lcm(a):    
    x = a[0]
    for i in range(1, len(a)):
        x = (x * a[i]) // gcd(x, a[i])
    return x

N = ir()
A = lr()
A.sort()
if N == 1:
    print(1)
    exit()
MOD = 10 ** 9 + 7
l = []
first = A[0]
l = [x//gcd(x, first) for x in A[1:]]
x = lcm(l) 
answer = x%MOD

for i in range(1, N):
    answer += first * x // A[i]
    if i % 100 == 0:
        answer %= MOD

print(answer%MOD)

Solution (Python):
import fractions

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

for i in range(n):
    lcm = lcm * a[i] // fractions.gcd(lcm, a[i]) if i > 0 else a[i]
    ainv_sum += pow(a[i], m-2, m)
    ainv_sum %= m

print((ainv_sum * lcm) % m)

Solution (Python):
def mpow(x, n):
    result = 1
    while n != 0:
        if n & 1 == 1:
            result *= x
            result %= 1000000007
        x *= x
        x %= 1000000007
        n >>= 1
    return result


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 * mpow(A[i], 1000000007-2)
    result %= 1000000007
print(result)

Solution (Python):
import fractions
N = int(input())
T = list(map(int, input().split()))
lcm = T[0]
ans = 0
MOD = 1000000007
for i in range(1, N):
  lcm = lcm * T[i] // fractions.gcd(lcm, T[i])
for x in T:
  ans += lcm // x
print(ans % MOD)

Solution (Python):
from fractions import gcd
MOD = 10 ** 9 + 7

def main():
    _ = int(input())
    l = list(map(int,input().split()))

    lcm = 1
    for i in l:
        lcm = lcm * i // gcd(lcm,i)

    ans = 0
    for i in l:
        ans += lcm // i
    ans %= MOD

    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
from fractions import gcd

def lcm(a):
    x = a[0]
    for i in range(1, len(a)):
        x = (x*a[i])//gcd(x, a[i])
    return x


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

A = lcm(a);
ans = 0

for i in a:
    ans+=A//i

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

Solution (Python):
import sys

def compute_gcd(x, y):
   while(y):
       x, y = y, x % y
   return x
 
def compute_lcm(x, y):
   lcm = (x*y)//compute_gcd(x,y)
   return lcm

def lcm(a):
	x = a[0]
	for i in range(1, len(a)):
		x = compute_lcm(x, a[i])
	return x

n = int(input())

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

MOD = 10 ** 9 + 7

ans = lcm(a)
cur = 0

for i in a:
	cur += ans // i

print(cur % MOD)

Solution (Python):



def calc_gcd(a, b):
  if a > b:
    a, b = b, a
  while True:
    a, b = b%a, a
    if a == 0:
      return b

def calc_lcm(a, b):
  gcd = calc_gcd(a, b)
  return int(a * b // gcd)

def main():
  n = int(input())
  As = list(map(int, input().strip().split()))
  lcm = As[0]
  total = 0
  for a in As[1:]:
    lcm = calc_lcm(lcm, a)
  for a in As:
    total += lcm // a
  print(total % (10**9+7))


if __name__=='__main__':
  main()

Solution (Python):
from fractions import gcd

def lcm(a):
    x = a[0]
    for i in range(1, len(a)):
        x = (x * a[i]) // gcd(x, a[i])
    return x

n=int(input())
a=list(map(int, input().split()))
A=lcm(a)
ans=0

for i in a:
    ans+=A//i

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

Solution (Python):
from fractions import gcd

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

for i in a:
    l=l*i//gcd(l,i)

for i in a:
    ans+=l//i

print(ans%mod)

Solution (Python):
def mpow(x, n):
    result = 1
    while n != 0:
        if n & 1 == 1:
            result *= x
            result %= 1000000007
        x *= x
        x %= 1000000007
        n >>= 1
    return result


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:
            t.append([sieve[a], 1])
        elif 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 * mpow(A[i], 1000000007-2)
    result %= 1000000007
print(result)

Solution (Python):
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations,groupby
import sys
import bisect
import string
import math
import time
import random
def S_():
    return input()
def LS():
    return [i for i in input().split()]
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def NI(n):
    return [int(input()) for i in range(n)]
def NI_(n):
    return [int(input())-1 for i in range(n)]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def LtoS(ls):
    return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)]
        rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
sys.setrecursionlimit(10**5)
input=lambda: sys.stdin.readline().rstrip()

def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a



def primeFactor(N):
    i,n=2,N
    ret={}
    d,sq=2,99
    while i<=sq:
        k=0
        while n%i==0:
            n,k,ret[i]=n//i,k+1,k+1
        if k>0 or i==97:
            sq=int(n**(1/2)+0.5)
        if i<4:
            i=i*2-1
        else:
            i,d=i+d,d^6
    if n>1:
        ret[n]=1
    return ret




def PrimeNumSet(N):
    Max = int(N**0.5)
    seachList = [i for i in range(2,N+1)]
    primeNum = []
    while seachList:
        if seachList[0] <= Max:
            break
        primeNum.append(seachList[0])
        tmp = seachList[0]
        seachList = [i for i in seachList if i % tmp != 0]
    primeNum.extend(seachList)
    return primeNum



def LCM(b,mo=10**9+7):
    prs=PrimeNumSet(max(b))
    M=dict(zip(prs,[0]*len(prs)))
    for i in b:
        dc=primeFactor(i)
        for j,k in dc.items():
            M[j]=max(M[j],k)
    
    r=1
    for j,k in M.items():
        if k!=0:
            r*=pow(j,k,mo)
            r%=mo
    return r

show_flg=False
show_flg=True


ans=0

n=I()
a=LI()

m=LCM(a)

x=0
for i in a:
    x+=m*pow(i,mo-2,mo)
    x%=mo

print(x)

Solution (Python):

MAX = 1000005
MOD = 10**9+7
factrial = [0]*MAX
inverse = [0]*MAX
factrial_inverse = [0]*MAX



def COMinit():
    global factrial, inverse, factrial_inverse
    factrial[0] = 1
    factrial[1] = 1
    inverse[1] = 1
    factrial_inverse[0] = 1
    factrial_inverse[1] = 1
    for i in range(2, MAX):
        factrial[i] = factrial[i-1] * i % MOD
        inverse[i] = MOD - inverse[MOD % i] * (MOD//i) % MOD
        factrial_inverse[i] = factrial_inverse[i-1] * inverse[i] % MOD



def COM(n, k):
    global factrial, inverse, factrial_inverse
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return factrial[n] * (factrial_inverse[k] * factrial_inverse[n-k] % MOD) % MOD



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

primes = {}

for val in A:
    p = 2
    while val >= p * p:
        if val % p == 0:
            
            cnt = 0
            while val % p == 0:
                cnt += 1
                val //= p
            if p not in primes:
                primes[p] = cnt
            else:
                primes[p] = max(cnt, primes[p])
        p += 1
    if val != 1:
        if val not in primes:
            primes[val] = 1

lcm = 1
for p, cnt in primes.items():
    lcm *= p ** cnt
    lcm %= MOD

ans = 0
for val in A:
    ans += lcm * inverse[val]
    ans %= MOD
print(ans)

Solution (Python):
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations,groupby
import sys
import bisect
import string
import math
import time
import random
def S_():
    return input()
def LS():
    return [i for i in input().split()]
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def NI(n):
    return [int(input()) for i in range(n)]
def NI_(n):
    return [int(input())-1 for i in range(n)]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def LtoS(ls):
    return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)]
        rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
sys.setrecursionlimit(10**5)
input=lambda: sys.stdin.readline().rstrip()

def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

def primeFactor(N):  
    i,n=2,N
    ret={}
    d,sq=2,99
    while i<=sq:
        k=0
        while n%i==0:
            n,k,ret[i]=n//i,k+1,k+1
        if k>0 or i==97:
            sq=int(n**(1/2)+0.5)
        if i<4:
            i=i*2-1
        else:
            i,d=i+d,d^6
    if n>1:
        ret[n]=1
    return ret

def PrimeNumSet(N):  
    Max = int(N**0.5)
    seachList = [i for i in range(2,N+1)]
    primeNum = []
    while seachList:
        if seachList[0] <= Max:
            break
        primeNum.append(seachList[0])
        tmp = seachList[0]
        seachList = [i for i in seachList if i % tmp != 0]
    primeNum.extend(seachList)
    return primeNum

def LCM(b,mo=10**9+7):  
    prs=PrimeNumSet(max(b))
    M=dict(zip(prs,[0]*len(prs)))
    for i in b:
        dc=primeFactor(i)
        for j,k in dc.items():
            M[j]=max(M[j],k)
    
    r=1
    for j,k in M.items():
        if k!=0:
            r*=pow(j,k,mo)
            r%=mo
    return r

show_flg=False
show_flg=True


ans=0

n=I()
a=LI()

m=LCM(a)

x=0
for i in a:
    x+=m*pow(i,mo-2,mo)
    x%=mo

print(x)

Solution (Python):
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations,groupby
import sys
import bisect
import string
import math
import time
import random
def S_():
    return input()
def LS():
    return [i for i in input().split()]
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def NI(n):
    return [int(input()) for i in range(n)]
def NI_(n):
    return [int(input())-1 for i in range(n)]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def LtoS(ls):
    return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)]
        rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
sys.setrecursionlimit(10**5)
input=lambda: sys.stdin.readline().rstrip()

def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

def primeFactor(N):  
    i,n=2,N
    ret={}
    d,sq=2,99
    while i<=sq:
        k=0
        while n%i==0:
            n,k,ret[i]=n//i,k+1,k+1
        if k>0 or i==97:
            sq=int(n**(1/2)+0.5)
        if i<4:
            i=i*2-1
        else:
            i,d=i+d,d^6
    if n>1:
        ret[n]=1
    return ret

def PrimeNumSet(N):  
    Max = int(N**0.5)
    seachList = [i for i in range(2,N+1)]
    primeNum = []
    while seachList and seachList[0] <= Max:
        primeNum.append(seachList[0])
        tmp = seachList[0]
        seachList = [i for i in seachList if i % tmp != 0]
    primeNum.extend(seachList)
    return primeNum

def LCM(b,mo=10**9+7):  
    prs=PrimeNumSet(max(b))
    M=dict(zip(prs,[0]*len(prs)))
    for i in b:
        dc=primeFactor(i)
        for j,k in dc.items():
            M[j]=max(M[j],k)
    
    r=1
    for j,k in M.items():
        if k!=0:
            r*=pow(j,k,mo)
            r%=mo
    return r

show_flg=False
show_flg=True


ans=0

n=I()
a=LI()

m=LCM(a)

x=0
for i in a:
    x+=m*pow(i,mo-2,mo)
    x%=mo

print(x)

Solution (Python):


import sys
from collections import Counter

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def fermat(x, y, MOD): return x * pow(y, MOD-2, MOD) % MOD

def factorize(num: int) -> dict:
    """ 素因数分解 """
    from math import sqrt
    from collections import Counter

    d = Counter()
    
    for i in range(2, int(sqrt(num))+1):
        
        while num % i == 0:
            num //= i
            d[i] += 1
        
        if num == 1:
            break
    
    if num != 1:
        d[num] += 1
    return d

def mul(C1, C2):
    return C1 + C2

def div(C1, C2):
    return C1 - C2

def gcd(C1, C2):
    for k, v in C2.items():
        C1[k] = min(C1[k], v)
    return C1
    

def lcm(C1, C2):
    for k, v in C2.items():
        C1[k] = max(C1[k], v)
    return C1
    
    

N = INT()
A = LIST()


A2 = [factorize(a) for a in A]
l2 = Counter()
for a in A2:
    l2 = lcm(l2, a)


l = 1
for k, v in l2.items():
    l *= pow(k, v, MOD)
    l %= MOD

ans = 0
for a in A:
    ans += fermat(l, a, MOD)
    ans %= MOD
print(ans)

Solution (Python):
def gcd(a, b):
    while b!= 0:
        a,b = b, a%b
    return a
def lcm(a,b):
    return a*b //(gcd(a, b))

N = int(input())
A = list(map(int, input().split()))
a_lcm = A[0]

mod = 10 ** 9 + 7

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

ans = 0
for i in range(N):
    ans += a_lcm*pow(A[i], mod-2, mod)
print(ans%mod)

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


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

primes = {}

for val in A:
    p = 2
    while val >= p * p:
        if val % p == 0:
            
            cnt = 0
            while val % p == 0:
                cnt += 1
                val //= p
            if p not in primes:
                primes[p] = cnt
            else:
                primes[p] = max(cnt, primes[p])
        p += 1
    if val != 1:
        if val not in primes:
            primes[val] = 1

lcm = 1
for p in primes:
    lcm *= p ** primes[p]
    lcm %= MOD

ans = 0

for val in A:
    ans += lcm * inv(val)
    ans %= MOD
print(ans)

Solution (Python):
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations,groupby
import sys
import bisect
import string
import math
import time
import random
def S_():
    return input()
def LS():
    return [i for i in input().split()]
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def NI(n):
    return [int(input()) for i in range(n)]
def NI_(n):
    return [int(input())-1 for i in range(n)]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def LtoS(ls):
    return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)]
        rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
sys.setrecursionlimit(10**5)
input=lambda: sys.stdin.readline().rstrip()

def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

def primeFactor(N):
    i,n=2,N
    ret={}
    d,sq=2,99
    while i<=sq:
        k=0
        while n%i==0:
            n,k,ret[i]=n//i,k+1,k+1
        if k>0 or i==97:
            sq=int(n**(1/2)+0.5)
        if i<4:
            i=i*2-1
        else:
            i,d=i+d,d^6
    if n>1:
        ret[n]=1
    return ret

def primes(n):
    rt=[]
    for i in range(2,10**5):
        if sum(primeFactor(i).values())==1:
            rt.append(i)
    return rt

def seachPrimeNum(N):
    max = int(N**0.5+1)
    seachList = [i for i in range(2,N+1)]
    primeNum = []
    while seachList[0] <= max:
        primeNum.append(seachList[0])
        tmp = seachList[0]
        seachList = [i for i in seachList if i % tmp != 0]
    primeNum.extend(seachList)
    return primeNum
    
def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError("n is int-type.")
    if n < 2:
        raise ValueError("n is more than 2")
    data = [i for i in range(2, n + 1)]
    for d in data:
        data = [x for x in data if (x == d or x % d != 0)]
    return data

def LCM(b):
    prs=seachPrimeNum(10**6)
    M=dict(zip(prs,[-1]*len(prs)))
    for i in b:
        dc=primeFactor(i)
        for j,k in dc.items():
            M[j]=max(M[j],k)
    
    r=1
    for j,k in M.items():
        if k!=-1:
            r*=pow(j,k,mo)
            r%=mo
    return r

show_flg=False
show_flg=True


ans=0

n=I()
a=LI()



m=LCM(a)

x=0
for i in a:
    x+=m*pow(i,mo-2,mo)
    x%=mo

print(x)