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):
N = int(input())
A = list(map(int, input().split()))
mod = int(1e+9 + 7)
L = A[0]
p = mod - 2
X = []
while p != 0:
  X = [p%2] + X[:]
  p //= 2

def inved(x):
  y = 1
  for i in range(len(X)):
    if X[i] == 1:
      y *= x
      y %= mod
    if i != len(X) - 1:
      y *= y
      y %= mod
  return y

for i in range(N-1):
  a, b = L, A[i+1]
  while b != 0:
    a, b = b, a % b
  b = A[i+1] // a
  L = b * L
S = 0
for i in range(N):
  S += (L * inved(A[i])) % mod
  S %= mod
print(S)

Solution (Python):
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
    
print(ans % mod)

Solution (Python):
from fractions import gcd

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

l = A[0]
for i in range(1, N):
    l = l * A[i] // gcd(l, A[i])

for a in A:
    res += l//a

print(res % 1000000007)

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

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

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

k = a[0]
for ai in a:
    k = lcm(ai, k)

res = 0
for ai in a:
    res += k//ai

print(res % 1000000007)

Solution (Python):
import fractions
from functools import reduce

mod = 10**9 + 7

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

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

n = int(input())
a = list(map(int, input().split()))
a_ = []
for i in range(n):
    a_.append(pow(a[i], mod - 2, mod))

num_lcm = lcm(*a) % mod
ans = 0
for i in range(n):
    ans = (ans + num_lcm * a_[i] % mod) % mod

print(ans)

Solution (Python):
n = int(input().strip())
A = [int(s) for s in input().strip().split()]
M = 10 ** 9 + 7

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

factors = [0] * 1001
large_factors = set()
for a in A:
    d = 0
    while a % 2 == 0:
        d += 1
        a //= 2
    factors[2] = max(factors[2], d)
    for i in range(3, int(a ** 0.5) + 1, 2):
        d = 0
        while a % i == 0:
            d += 1
            a //= i
        factors[i] = max(factors[i], d)
        if a == 1:
            break
    if a > 1000:
        large_factors.add(a)
    elif a > 1:
        factors[a] = max(factors[a], 1)

m = 1
for k, v in enumerate(factors):
    if v > 0:
        m = (m * pow(k, v, M)) % M
for k in large_factors:
    m = (m * k) % M

result = 0
for a in A:
    result = (result + m * modinv(a, M)) % M
print(result)

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

Solution (Python):


def gcd(a, b):
    """Calculate the Greatest Common Divisor of a and b.

    Unless b==0, the result will have the same sign as b (so that when
    b is divided by it, the result comes out positive).
    """
    while b:
        a, b = b, a%b
    return a


n = map(int, raw_input().split())
a = map(int, raw_input().split())

lcm = 1
cnt = 0
MOD = int(1e9 + 7)

for x in a:
    lcm = x*lcm/gcd(lcm, x)
    
for x in a:
    cnt += lcm/x 
    
print cnt % MOD

Solution (Python):
def main():
    from functools import reduce

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

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

    mod = 10 ** 9 + 7

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

    L = reduce(lcm, a)

    ret = 0
    for x in a:
        ret = (ret + pow(x, mod - 2, mod)) % mod
    ret = ret * L % mod
    print(ret)


if __name__ == '__main__':
    main()

Solution (Python):
'''
条件に合うものを絞り込む
data = [1, 2, 3]
s = [x for x in data if x % 3 == 0]
'''
'''
文字配列を数値に
l_si = ['-10', '0', '100']

l_si_i = [int(s) for s in l_si]
'''
'''
a = [2, 4, 6, 8]
b = [3, 6, 9]

print(list(set(a) | set(b)))  
print(list(set(a) & set(b)))  
'''
'''
N = int(stdin.readline().rstrip())
A = [int(x) for x in stdin.readline().rstrip().split()]
count = 0
while len([x for x in A if x % 2 == 0]) == N:
    A = list(map(lambda y: y / 2, A))
    count += 1
print(count)
'''
'''
.append(要素)
.extend(要素)
.insert(場所,要素)
del 配列名[場所]
-1で末尾で末尾から一つ前
'''
'''
間に空白追加
' '.join(lis)
'''
'''
copy.copy(配列名)
'''
'''
sort()
sorted(reverse=true)
'''
'''
2分探索
bisect.bisect_left(リスト, 要素)
'''
'''
リスト同士の演算
list(map(lambda x, y: x+y, el2, el3))
'''
'''
配列の初期化
配列名=[a]*n+[b]*m
'''
'''
重複
list(set())
２次元配列
list(map(list, set(map(tuple, addition))))
'''
'''
順列
for el in itertools.permutations(配列のパターン):
'''
'''
Decimal()
'''






from sys import stdin
from itertools import accumulate, dropwhile, takewhile, groupby
import bisect
import copy
import math
import itertools
from functools import reduce
from operator import mul
def gcd(*numbers):
    return reduce(math.gcd, numbers)


def gcd_list(numbers):
    return reduce(math.gcd, numbers)


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


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


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


def get_unique_list(seq):
    seen = []
    return [x for x in seq if x not in seen and not seen.append(x)]


N = int(stdin.readline().rstrip())
A = [int(s) for s in stdin.readline().rstrip().split()]
res = lcm(A)
part = 0
for k in range(len(A)):
    part += res//A[k]
print(part % (10**9+7))

Solution (Python):
import fractions

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

if n == 1:
    print(1)
else:
    lcm = 1
    sum_b = 0
    for i in range(n):
        gcd = fractions.gcd(a[i], lcm)
        sum_b *= (a[i] // gcd)
        sum_b %= mod
        lcm = lcm * a[i] // gcd
        sum_b += (lcm // a[i])
        sum_b %= mod
    print(sum_b)

Solution (Python):

from fractions import gcd
from functools import reduce

N = int(input())

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

MOD = 10**9+7

L = reduce((lambda x, y: x // gcd(x, y) * y), A) % MOD

res = 0

def modulo(x, y):
  tmp = x % y
  if tmp < 0: tmp += y
  return tmp

def extgcd(x, y):
  if x < y:
    a, b = extgcd(y, x)
    return b, a
  if y == 0 or x % y == 0: return 0, 1
  a, b = extgcd(y, modulo(x , y))
  return (b, -(x // y) * b + a)

def inv(x):
  a, _ = extgcd(x,MOD)
  return modulo(a, MOD)

for a in A:
  res = (res + L* inv(a) % MOD) % MOD

print(res)

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 = [int(x) for x in input().split()]

t_lcm = lcm(A)
count = 0
for i in A:
    count += t_lcm//i
    
print(count%(10**9+7))

Solution (Python):
from collections import Counter

def solve():
    MOD = 10**9 + 7
    maxA = 10**6

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

    isPrimes = [False]*2 + [True]*(maxA-1)
    minFs = [1] * (maxA+1)
    for i in range(2, int(maxA**0.5) + 1):
        if isPrimes[i]:
            for x in range(i*i, maxA+1, i):
                isPrimes[x] = False
                minFs[x] = i

    def getPrimeFactors(x):
        anss = []
        while minFs[x] > 1:
            anss.append(minFs[x])
            x //= minFs[x]
        if x != 1:
            anss.append(x)
        return anss

    PFss = []
    Primes = set()
    for A in As:
        PFs = getPrimeFactors(A)
        cnt = Counter(PFs)
        PFss.append(cnt)
        Primes |= cnt.keys()

    cntP = Counter()
    for PFs in PFss:
        for key, num in PFs.items():
            cntP[key] = max(cntP[key], num)

    lcmA = 1
    for key, num in cntP.items():
        lcmA *= pow(key, num, MOD)
        lcmA %= MOD

    def getInvs(n, MOD):
        invs = [1] * (n+1)
        for x in range(2, n+1):
            invs[x] = (-(MOD//x) * invs[MOD%x]) % MOD
        return invs

    invs = getInvs(10**6, MOD)

    ans = 0
    for A in As:
        ans += lcmA * invs[A]
        ans %= MOD

    print(ans)

solve()

Solution (Python):
import fractions

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

l = a[0]
for i in range(1, n):
    l = l * a[i] // fractions.gcd(l, a[i])

count = 0


for i in a:
  count += l//i
count %= (10**9+7)

print(count)

Solution (Python):
from collections import defaultdict

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

mod = 10 ** 9 + 7

def prime_factor(x) :
  ret = dict()
  if x % 2 == 0 :
    ret[2] = 0
    while x % 2 == 0 :
      x //= 2
      ret[2] += 1
          
  i = 3
  while i * i <= x :
    if x % i == 0 :
      ret[i] = 0
      
      while x % i == 0 :
        x //= i
        ret[i] += 1
    i += 2
      
  if x != 1 :
    ret[x] = 1
  
  return ret

pr = defaultdict(int)
for i in range(N) :
  for k, v in prime_factor(A[i]).items() :
    pr[k] = max(pr[k], v)
    
a = 1
for k, v in pr.items() :
  a *= pow(k, v, mod)
  a %= mod

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

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()))

saikou = lcm_list(a)
ans = 0

for i in a:
  b = saikou // i
  ans += b
  
print(int(ans) % 1000000007)

Solution (Python):
N = int(input())
A = 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)


if len(A) < 2:
    print(1)
    exit()

if A[0] < A[1]:
    temp = lcm(A[1], A[0])
else:
    temp = lcm(A[0], A[1])

for i in range(2, N):
    if temp < A[i]:
        temp = lcm(A[i], temp)
    else:
        temp = lcm(temp, A[i])

if temp == A[0]:
    print(N)
    exit()

ans = 0
for a in A:
    ans += temp // a

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

Solution (Python):
import functools
MOD = 10**9 + 7
N = int(input())
A = list(map(int,input().split()))

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

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

def list_lcm(l):
    return functools.reduce(lcm,l)

g = list_lcm(A)

B = [g //a for a in A]
print(sum(B) % MOD)

Solution (Python):


import fractions
def min_kou(a):
  ans = a[0]
  for i in range(1, len(a)):
    ans = ans * a[i] // fractions.gcd(ans, a[i])
  return ans

def main():
  N = int(input())
  A = list(map(int, input().split()))
  min_res = min_kou(A)
  ans = 0
  for i in A:
    ans += min_res // i
  print(ans % 1000000007)
  
if __name__ == '__main__':
  main()

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

def solve(arr):
    ab = lcm(arr)
    sum = 0
    for a in arr:
        sum += ab // a
    return sum % (10**9+7)

n = int(input())
arr = list(map(int, input().split()))
print(solve(arr))

Solution (Python):
from fractions import gcd
import sys 
input = sys.stdin.readline

def pow_mod(x,n):
    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 K*x

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

if N==1:
    print(1)
    exit()

Gcd = gcd(A[0],A[1])
ans = (A[0]//Gcd+A[1]//Gcd)%mod
temp = A[0]//Gcd

for i in range(1,N-1):
    
    Gcd = gcd(A[i],A[i+1])
    
    temp2 = A[i+1]//Gcd
    
    Gcd2 = gcd(temp,temp2)

    
    a = temp2//Gcd2
    
    b = temp//Gcd2

    temp = A[i]//Gcd*b

    a %= mod
    b %= mod
    ans *= a
    ans %= mod


    Gcd %= mod 
    c = A[i]
    c %= mod
    d = c*pow_mod(Gcd,mod-2)
    
    d %= mod


    e = b*d%mod
    ans += e
    
    ans %= mod


print(ans)

Solution (Python):
from operator import itemgetter
from math import log,ceil
from fractions import gcd
mod = 10**9 + 7


def euclid(a:int,b:int)->(int,int):
    
    
    if b == 0:
        return 1,0
    x,y = euclid(b,a%b)
    return y,x - y*(a // b)

def inverse(a:int,mod:int)->int:
    
    if mod > a:
        n,x = euclid(mod,a)
    else:
        x,n = euclid(a,mod)
    return x

def devide_mod(a:int,b:int,mod:int)->int:
    
    x = inverse(b,mod)
    return  (a*x)%mod



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

def main():
    N = int(input())
    A  =list(map(int,input().split()))
    neko = 1
    for a in A:
        neko = lcm(neko,a)
    sm = 0
    neko = neko%mod
    for a in A:
        sm = (sm + devide_mod(neko , a,mod))%mod
    print(sm)

    return


if __name__ == "__main__":
    main()

Solution (Python):


import fractions
from functools import reduce

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


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


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


min_AB = lcm(*A)

ans = 0
for a in A:
    ans += min_AB // a

print(ans % mod)

Solution (Python):
from functools import reduce
import fractions


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())
a = list(map(int, input().split()))
l = lcm_list(a)
ans = sum([l // x for x in a]) % int(1e9+7)
print(ans)

Solution (Python):

from fractions import gcd


n=int(input())
a=list(map(int,input().split()))
mod=10**9+7
x = a[0]
for i in range(1, len(a)):
    x = (x * a[i]) // gcd(x, a[i])
gcd=x
res = 0
for i in a:
    res += gcd//i
    
print(res%mod)

Solution (Python):
import sys
from fractions import gcd
input = sys.stdin.readline


def mod_inverse(n, mod=10**9+7):
    return pow(n, mod-2, mod)

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


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

ans = 0
inv_sum = 0
l = A[0]
for a in A:
    l = lcm(l, a)
    inv_sum = (inv_sum + mod_inverse(a)) % mod
print(l * inv_sum % mod)

Solution (Python):

import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

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


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

P = 10**9 + 7
N = 1000010
inv_t = [0]+[1]
for i in range(2,N):
  inv_t += [inv_t[P % i] * (P - int(P / i)) % P]

for ai in A:
    pro=lcm(pro,ai)
for ai in A:
    ans+=inv_t[ai]
    ans%=mod
print((pro*ans)%mod)

Solution (Python):
import functools

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

def gcd(m, n):
    r = m % n
    return gcd(n, r) if r else n

def lcm(m, n):
    return m//gcd(m, n)*n

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

lcm_a = lcm_list(a)

b = [lcm_a//a[i] for i in range(n)]

print(sum(b) % ((10**9)+7))

Solution (Python):
import collections
import sys

readline = sys.stdin.buffer.readline


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


def main():
    N = int(readline())
    A = list(map(int, readline().split()))
    C = 10**9 + 7

    d = collections.defaultdict(list)

    for a in A:
        B = factorization(a)
        for b in B:
            d[b[0]].append(b[1])
    e = 1
    for k, v in d.items():
        e *= k**max(v)

    ans = 0
    for a in A:
        ans += (e // a)
    print(ans % C)


main()

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

MOD = 10 ** 9 + 7

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

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

l = lcm(a)
total = 0

for a_ in a:
    total += l // a_

print(total % MOD)

Solution (Python):


MOD = 10**9 + 7

def getPrimes(n):
    if (n < 2):
        return []

    flags = [False]*(n+1)
    primes = [2]

    for p in range(3, n+1, 2):
        if not flags[p]:
            primes.append(p)
            for k in range(p**2, n+1, p):
                flags[k] = True

    return primes


def modPow(a, b, mod):
    x = 1
    
    while b > 0:
        if b & 1:
            x = (x*a)%mod

        a = (a**2)%mod
        b //= 2

    return x


def getModInv(a, b):
    return 1 if (a == 1) else int((1-b*getModInv(b%a, a))/a%b)


def getFactors(x):
    factors = {}
    for p in P:
        if x < 2:
            break

        n = 0
        while x%p == 0:
            x //= p
            n += 1

        if n > 0:
            factors[p] = n

    if x > 1:
        factors[x] = 1

    return factors


P = getPrimes(1000)

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

maxFacts = {}

for a in A:
    facts = getFactors(a)
    for p in facts:
        if not p in maxFacts or maxFacts[p] < facts[p]:
            maxFacts[p] = facts[p]

lcd = 1
for p in maxFacts:
    lcd = lcd * modPow(p, maxFacts[p], MOD)%MOD

lcd %= MOD

s = 0
for a in A:
    s += lcd*getModInv(a, MOD)%MOD

print(s%MOD)

Solution (Python):
import sys
from fractions import gcd
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input(): return sys.stdin.readline().rstrip()

def main():
    def modinv(a, mod):
        b,u,v = mod,1,0
        while b:
            t=a//b
            a-=t*b
            a,b=b,a
            u-=t*v
            u,v=v,u
        u%=mod
        if u < 0:
            u+=mod
        return u
    
    
    N=int(input())
    A=list(map(int,input().split()))
    l=A[0]
    for x in A[1:]:
        l=l*x//gcd(l,x)
    l%=MOD
    ans=0
    for x in A:
        ans+=l*modinv(x,MOD)
        ans%=MOD
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
import fractions
from functools import reduce
def main():
  _=input()
  a=tuple(map(int,input().split()))
  fgcd=fractions.gcd
  def lcm_base(x, y):
    return (x * y) // fgcd(x, y)
  def lcm(numbers):
    return reduce(lcm_base, numbers, 1)
  q=lcm(a)
  x=[q//i for i in a]
  print(sum(x)%(10**9+7))
  
if __name__ == '__main__':
    main()

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

def extgcd(a,b): 
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    
    return [w[0],w[1]]

def mod_inv(a,mod): 
    x = extgcd(a,mod)[0]
    return (mod+x%mod)%mod










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

lcm_ = a[0]
for i in range(1, n):
    lcm_ = lcm_ * a[i] // fractions.gcd(lcm_, a[i])


ans = 0
for i in range(0,n):
    
    
    
    

    ans += lcm_%MOD * mod_inv(a[i], MOD)%MOD

print(ans%MOD)

Solution (Python):
def gcd(x, y): 
      
    while(y): 
        x, y = y, x % y 
      
    return x 
 
n=int(input())
a=list(map(int,input().split()))
x=1
ans=0
for i in a:
    x=(x*i)//gcd(x,i)
for i in a:
    ans+=(x//i)
ans=ans%(1000000007)
print(ans)

Solution (Python):
from fractions import gcd
lim=10**9+7
def lcm(a):
    x = a[0]
    for i in range(1, len(a)):
        x = (x * a[i]) // gcd(x, a[i])
    return int(x)


n=int(input())
A=[int(i) for i in input().split()]
A_inv = [pow(a,lim-2,lim) for a in A]

Z = A[0]
k=1
for i in range(1, n):
    Z = Z // gcd(Z, A[i]) * A[i]
ans=0

Z=Z % lim
for i in range(n):
    ans = ( ans + Z*A_inv[i] ) % lim
print(ans)

Solution (Python):
MAX = 1000001

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


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




def flt(a, mod):
    return rep_sqr(a, mod-2, mod)


sieve()


MOD = 10**9 + 7

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

lcm_ = lcmModuloM(a, n)

b = list(map(lambda x: lcm_ * flt(x, mod), a))
ans = 0
for i in range(len(b)):
    ans += b[i]
    ans %= MOD
print(ans)

Solution (Python):

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


def modinv(a, m):
    b = m
    u = 1
    v = 0
    while b:
        t = 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 gcd(a,b):
    while b!=0:
        a,b = b,a%b
    return a

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

def lcmlist(l):
    res = l[0]
    for x in l[1:]:
        res = lcm(res, x)
    return res

l = lcmlist(al)%MOD
res = 0
for a in al:
    res += l*modinv(a,MOD)
    res %= MOD

print(res)

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

Solution (Python):
MOD = 1000000007


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


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


def LCM(a, b):
    return (a // GCD(a, b)) * b


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

l = 1
for i in range(n):
    l = LCM(l, a[i])
ans = 0
l %= MOD
for i in range(n):
    ans += l * modinv(a[i]) % MOD
    ans %= MOD
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
from collections import defaultdict

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

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

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

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



L = 1
d = defaultdict(int)

for Ai in A:
    f = factorize(Ai)
    
    for n, c in f:
        d[n] = max(d[n], c)

for v, c in d.items():
    L *= v**c
    L %= MOD
    
ans = 0

for Ai in A:
    ans += L*inv(Ai)
    ans %= MOD

print(ans)

Solution (Python):
from fractions import gcd
from functools import reduce
def lcm(x, y):
  return (x * y) // gcd(x, y)
def ll(numbers):
  return reduce(lcm, numbers, 1)
def modinv(a):
    return pow(a,m-2,m)
n=int(input())
a=list(map(int,input().split()))
l=ll(a)
x=0
m=10**9+7
lm=l%m
for i in range(n):
  x+=(lm*modinv(a[i]))%m
  x=x%m
print(x)

Solution (Python):
from functools import reduce
import fractions
N = int(input())
* A, = map(int, input().split())
mod = 10**9+7


def gcd(a, b):
    return int(fractions.gcd(a, b))


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


LCM = reduce(lcm, A)

ans = 0
for a in A:
    ans += LCM * pow(a, mod - 2, mod) % mod
print(ans % mod)

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

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

num = int(input())
A = [int(s) for s in input().split()]
ans = A[0]
for i in range(1,num):
    ans = lcm(ans,A[i])
B = [ans//A[s] for s in range(num)]
print(sum(B)%(10**(9)+7))

Solution (Python):
import fractions
N = int(input())
A = list(map(int,input().split()))
mod = 10 ** 9 + 7
def mul(a, b):
    return ((a % mod) * (b % mod)) % mod
def div(a, b):
    return mul(a, pow(b,mod-2,mod))
if N == 1:
    ans = 1
else:
    lcm = A[0] * A[1] // fractions.gcd(A[0],A[1])
    for i in range(2,N):
        
        lcm = lcm * A[i] // fractions.gcd(lcm,A[i])
    ans = 0
    for i in range(N):
        b = div(lcm,A[i])
        ans += b 
        ans %= 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(*numbers):
    return reduce(lcm_base, numbers, 1)

n = int(input())
a = [int(i) for i in input().split()]
mod = 10 ** 9 + 7
ans = 0
b = lcm(*a)

for i in range(n):
    ans += b // a[i]
print(ans%mod)

Solution (Python):
def gcd(a,b):
    if a>b: a,b=b,a
    while b:
        a, b = b, a%b
    return a

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

n = int(input())
a = list(map(int, input().split()))
g = 0
for i in range(n): g=lcm(g, a[i])

sm = 0
for i in a: sm += g//i
print(sm%1000000007)

Solution (Python):
import fractions
mod=10**9+7
N=int(input())
a = list(map(int, input().split()))
ans = a[0]
for i in range(1, N):
    ans = ans * a[i] // fractions.gcd(ans, a[i])

count=0
for i in a:
    count+=ans//i
print(count%mod)

Solution (Python):
mod = 10**9+7
n = int(input())
l = list(map(int, input().split()))

from functools import reduce

def gcd(x, y):
  while y:
    x , y = y, x % y
  return x

lcm = l[0]
ans = 1

for i in range(1, n):
  g = gcd(lcm, l[i])
  s = lcm // g
  t = l[i] // g
  lcm = s * t * g
  ans = (ans * t + s) % mod
print(ans)

Solution (Python):
n=int(input())
a=list(map(int,input().split()))
import fractions
mod=10**9+7
ans=0
l=a[0]
for i in range(1,n):
    l=l*a[i]//fractions.gcd(l,a[i])
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()))
c=1
a=0
w=10**9+7
for A_ in A:
    c=c*A_//fractions.gcd(c,A_)
for A_ in A:
    a+=c//A_
print(int(a%w))

Solution (Python):
mod = 10**9+7
n = int(input())
num = [ int(v) for v in input().split() ]

def gcd(a,b):
    if a < b:
        a, b = b, a
    while b >= 1:
        a, b = b, a % b
    return a
def lcm(a,b):
	return a * b // gcd(a,b)

def shave(n):
    if n < 2:
        return []
    else:
        n_root = int(n**0.5)
        candidate = [i for i in range(3, n+1, 2)]
        for i in range(3, n_root+2, 2):
            candidate = [j for j in candidate if j == i or j % i != 0]
        candidate = [2] + candidate
        return candidate

d = {}
prime_list = shave(10**3)
for i in prime_list:
    d[i] = 0

def prime_factorization(x):

    for i in prime_list:
        if x == 1:
            break
        elif x % i == 0:
            q = 0
            while x % i == 0:
                x //= i
                q += 1
            d[i] = max(d[i], q)
    if x != 1:
        d[x] = 1
    return 

for i in num:
    prime_factorization(i)

l = 1
for i in d:
    l *= pow(i, d[i], mod)
    l %= mod

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

Solution (Python):
n = int(input())
a = list(map(int,input().split()))
P = 10 ** 9 + 7
p = 10 ** 9 + 7
mo = P
inv_t = [0]+[1]
for i in range(2,1000009):
    inv_t += [inv_t[P % i] * (P - int(P / i)) % P]



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

M = a[0]
for i in range(1, n):
    M = M * a[i] // gcd(M, a[i])

M = M%p
ans = 0
for i in range(n):
    ans += M*inv_t[a[i]]
    ans = ans %p

print(ans)

Solution (Python):
import fractions


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


N = int(input())
A = list(map(int, input().split()))
l = A[0]
mod = 10**9+7
ans = 0
for i in range(1, N):
    l = lcm(l, A[i])
for i in range(N):
    ans += l // A[i]
print(ans % mod)

Solution (Python):
import fractions
import sys
input = sys.stdin.readline


P = 10**9 + 7
N = (10**6)+1
inv_t = [0]+[1]
for i in range(2, N):
    inv_t += [inv_t[P % i] * (P - int(P / i)) % P]

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

mod = 10**9+7
lcm = 1
B = [0]*N

for i in range(N):
    lcm = (lcm // fractions.gcd(lcm, A[i])) * A[i]

ans = 0

lcm %= mod
for i in range(N):
    ans += (lcm * inv_t[A[i]]) % mod
    ans %= mod

print(ans)

Solution (Python):
import fractions

def modinv(a, MOD=1000000007):
    b = MOD
    u = 1
    v = 0
    while b > 0:
        t = a // b
        a -= (t * b)
        tmp = a
        a = b
        b = tmp
        u -= (t * v)
        tmp = u
        u = v
        v = tmp
    u %= MOD
    if u < 0:
        u += MOD
    return u
            

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

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

def read():
    N = int(input().strip())
    A = list(map(int, input().strip().split()))
    return N, A

def solve(N, A, MOD=1000000007):
    lcmv = lcm_array(A)
    bsum = 0
    for i in range(N):
        bsum += (lcmv * modinv(A[i]) % MOD)
        bsum %= MOD
    return bsum

if __name__ == '__main__':
    inputs = read()
    print("%s" % solve(*inputs))