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, deque, Counter, OrderedDict
from bisect import bisect_left, bisect_right
from functools import reduce, lru_cache
from heapq import heappush, heappop, heapify

import itertools, bisect
import math, fractions
import sys, copy

def L(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline().rstrip())
def S(): return list(sys.stdin.readline().rstrip())
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
def LR(n): return [L() for _ in range(n)]

alphabets = "abcdefghijklmnopqrstuvwxyz"
ALPHABETS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"

sys.setrecursionlimit(1000000)
dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
MOD = 1000000007

class FactInv:
    def __init__(self, N, MOD=MOD):
        fact, inv = [1]*(N+1), [None]*(N+1)
        for i in range(1, N+1): fact[i] = fact[i - 1] * i % MOD
        inv[N] = pow(fact[N], MOD - 2, MOD)
        for i in range(N)[::-1]: inv[i] = inv[i + 1] * (i + 1) % MOD
        self.N, self.MOD, self.fact, self.inv = N, MOD, fact, inv

    def perm(self, a, b):
        if a > self.N or b > self.N: raise ValueError("\nPermutaion arguments are bigger than N\n N = {}, a = {}, b = {}".format(self.N, a, b))
        return self.fact[a] * self.inv[a-b] % self.MOD

    def comb(self, a, b):
        if a > self.N or b > self.N: raise ValueError("\nCombination arguments are bigger than N\n N = {}, a = {}, b = {}".format(self.N, a, b))
        return self.fact[a] * self.inv[b] * self.inv[a-b] % self.MOD

class Eratosthenes:
    
    def __init__(self, n):
        primes, lp = [], [0] * (n + 1)
        for i in range(2, n + 1):
            if lp[i] == 0:
                primes.append(i)
                lp[i] = i

            for pj in primes:
                if pj > lp[i] or i * pj > n: break
                lp[i * pj] = pj
        self.primes, self.lp = primes, lp

    def is_prime(self, x): return self.lp[x] == x

    def factors(self, x):
        ret = []
        while x > 1:
            ret.append(self.lp[x])
            x //= self.lp[x]
        return ret

def main():
    N = I()
    A = LI()

    era = Eratosthenes(max(A))
    factors = Counter()

    for ai in A:
        cai = Counter(era.factors(ai))
        for k in cai.keys():
            factors[k] = max(factors[k], cai[k])

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

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

    print(ans)





if __name__ == '__main__':
    main()

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


table_len = 1010
prime_list = [] 
isprime = [True] * (1010)
isprime[0] = isprime[1] = False
for i in range(table_len):
    if isprime[i]:
        for j in range(2*i, table_len, i):
            isprime[j] = False
        prime_list.append(i) 

N = int(input())
As = list(map(int, input().split()))
factor_counts = [0] * len(prime_list)
big_factors = set() 
for A in As:
    for i, p in enumerate(prime_list):
        count = 0
        while A % p == 0:
            A //= p
            count += 1
        factor_counts[i] = max(factor_counts[i], count)
        if A == 1:
            break
    else:
        big_factors.add(A)

A_lcm = 1
for p, count in zip(prime_list, factor_counts):
    A_lcm *= pow(p, count, MOD)
    A_lcm %= MOD

for p in big_factors:
    A_lcm *= p
    A_lcm %= MOD

ans = 0
for A in As:
    ans += A_lcm * pow(A, MOD - 2, MOD) % MOD
    ans %= MOD

print(ans)

Solution (Python):
def gcds(*numbers):
    from math import gcd
    from functools import reduce
    return reduce(gcd, numbers)

def lcms(*numbers):
    from math import gcd
    from functools import reduce
    def lcm_base(x, y):
        return x // gcd(x, y) * y
    return reduce(lcm_base, numbers)

def build_inv(N=10**5, P=10**9+7):
    inv = [0, 1]
    for i in range(2, N + 1):
        inv.append((-inv[P % i] * (P // i)) % P)
    return inv

def resolve():
    N = int(input())
    A = list(map(int, input().split()))
    MOD = 10**9+7
    invs = build_inv(10**6, MOD)
    target = lcms(*A)
    print(target*sum(map(lambda x: invs[x], A))%MOD)

    
if __name__ == "__main__":
    resolve()

Solution (Python):
import sys
from functools import reduce
from collections import defaultdict
def input(): return sys.stdin.readline().rstrip()


mod = 10**9+7


def prime(x):
    pf = defaultdict(int)
    for i in range(2, int(x**0.5)+1):
        while x % i == 0:
            pf[i] += 1
            x //= i
    if x > 1:
        pf[x] = 1
    return pf


def lcm(x, y):
    xx=x.copy()
    yy=y.copy()
    for k, v in yy.items():
        xx[k] = max(xx[k], v)
    return xx


def main():
    n = int(input())
    a = list(map(int, input().split()))
    a2 = list(map(prime, a))
    lcms = reduce(lcm, a2)
    lcmss = 1
    for k, v in lcms.items():
        lcmss = (lcmss*(k**v)) % mod
    ans = 0
    for aa in a:
        ans += lcmss*pow(aa,-1,mod)
    print(ans % mod)


if __name__ == '__main__':
    main()

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

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

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

b = []
for i in range(n):
    b.append(lcm // a[i])

print(sum(b) % MOD)

Solution (Python):
'''
研究室PCでの解答
'''
import math

import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit


ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7
dir = [(-1,0),(1,0),(0,-1),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"

def rev(n,mod=(10**9+7)):
    ni = n
    nm = 1
    m2 = mod-2
    while m2 > 0:
        if m2&1:
            nm = (nm*ni)%mod
        m2 >>= 1
        ni = (ni**2)%mod
    return nm


def factorization(n):
    d = dict()
    ni = n
    pn = 2
    t = 0
    while pn**2 <= n and ni > 1:
        if ni%pn == 0:
            t += 1
            ni //= pn
        else:
            if not t == 0:
                d[pn] = t
                t = 0
            if pn == 2:
                pn = 3
            else:
                pn += 2
    if t > 0:
        d[pn] = t
    if ni > 1:
        d[ni] = 1
    return d

def main():
    n = int(ipt())
    ans = 0
    a = [int(i) for i in ipt().split()]
    d = defaultdict(int)
    for i in a:
        ans += rev(i)
        di = factorization(i)
        for ki,vi in di.items():
            d[ki] = max(d[ki],vi)
        ans %= mod

    for ki,vi in d.items():
        ans *= pow(ki,vi,mod)
        ans %= mod

    print(ans)

    return None

if __name__ == '__main__':
    main()

Solution (Python):
'''
研究室PCでの解答
'''
import math

import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit


ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7
dir = [(-1,0),(1,0),(0,-1),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"

def rev(n,mod=(10**9+7)):
    ni = n
    nm = 1
    m2 = mod-2
    while m2 > 0:
        if m2&1:
            nm = (nm*ni)%mod
        m2 >>= 1
        ni = (ni**2)%mod
    return nm


def factorization(n):
    d = dict()
    ni = n
    pn = 2
    t = 0
    while pn**2 <= n and ni > 1:
        if ni%pn == 0:
            t += 1
            ni //= pn
        else:
            if not t == 0:
                d[pn] = t
                t = 0
            if pn == 2:
                pn = 3
            else:
                pn += 2
    if t > 0:
        d[pn] = t
    if ni > 1:
        d[ni] = 1
    return d

def main():
    n = int(ipt())
    ans = 0
    a = [int(i) for i in ipt().split()]
    d = defaultdict(int)
    for i in a:
        ans += rev(i)
        di = factorization(i)
        for ki,vi in di.items():
            d[ki] = max(d[ki],vi)
        ans %= mod

    for ki,vi in d.items():
        ans *= pow(ki,vi,mod)
        ans %= mod

    print(ans)

    return None

if __name__ == '__main__':
    main()

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
mod = 10**9 + 7
a = max(A)
prime_num = [2]
sgn = [0 for _ in range(max(int(a**0.5)+1, 4))]
sgn[2] = 1
for k in range(3, len(sgn), 2):
  if sgn[k] == 0:
    prime_num.append(k)
    for j in range(k, a+1, k**2):
      sgn[k] = 1
baisu = []
count = [0 for _ in range(a+1)]
for k in range(N):
  b = 0 + A[k]
  for p in prime_num:
    if p**2 <= b:
      if b%p == 0:
        if count[p] == 0:
          baisu.append(p)
        c = 0
        while b % p == 0:
          b //= p 
          c += 1 
        if c > count[p]:
          count[p] = c
    else:
      break
  if b != 1:
    if count[b] == 0:
      count[b] = 1
      baisu.append(b)

product = 1
for item in baisu:
  product *= pow(item, count[item], mod)
  product %= mod

b = mod-2
blis = []
c = 0
while b >0:
  if b & 1 == 1:
    blis.append(c)
  c += 1
  b >>= 1

def modinv(a):
  if a == 1:
    return 1
  else:
    res = 1
    li = []
    for _ in range(c):
      li.append(a%mod)
      a = a*a%mod
    for item in blis:
      res = res *li[item] %mod
    return res

ans = 0
for k in range(N):
  ans += product*modinv(A[k])
  ans %= mod

print(ans)

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
mod = 10**9 + 7
a = max(A)
prime_num = [2]
sgn = [0 for _ in range(max(int(a**0.5)+1, 4))]
sgn[2] = 1
for k in range(3, len(sgn), 2):
  if sgn[k] == 0:
    prime_num.append(k)
    for j in range(k, a+1, k**2):
      sgn[k] = 1
baisu = []
count = [0 for _ in range(a+1)]
for k in range(N):
  b = 0 + A[k]
  for p in prime_num:
    if p**2 <= b:
      if b%p == 0:
        if count[p] == 0:
          baisu.append(p)
        c = 0
        while b % p == 0:
          b //= p 
          c += 1 
        if c > count[p]:
          count[p] = c
    else:
      break
  if b != 1:
    if count[b] == 0:
      count[b] = 1
      baisu.append(b)

product = 1
for item in baisu:
  product *= pow(item, count[item], mod)
  product %= mod

b = mod-2
blis = []
c = 0
while b >0:
  if b & 1 == 1:
    blis.append(c)
  c += 1
  b >>= 1

def modinv(a):
  if a == 1:
    return 1
  else:
    res = 1
    li = []
    for _ in range(c):
      li.append(a%mod)
      a = a*a%mod
    for item in blis:
      res = res *li[item] %mod
    return res

ans = 0
for k in range(N):
  ans += product*modinv(A[k])
  ans %= mod

print(ans)

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
mod = 10**9 + 7
a = max(A)
prime_num = [2]
sgn = [0 for _ in range(max(int(a**0.5)+1, 4))]
sgn[2] = 1
for k in range(3, len(sgn), 2):
  if sgn[k] == 0:
    prime_num.append(k)
    for j in range(k, a+1, k**2):
      sgn[k] = 1
baisu = []
count = [0 for _ in range(a+1)]
for k in range(N):
  b = 0 + A[k]
  for p in prime_num:
    if p**2 <= b:
      if b%p == 0:
        if count[p] == 0:
          baisu.append(p)
        c = 0
        while b % p == 0:
          b //= p 
          c += 1 
        if c > count[p]:
          count[p] = c
    else:
      break
  if b != 1:
    if count[b] == 0:
      count[b] = 1
      baisu.append(b)

product = 1
for item in baisu:
  product *= pow(item, count[item], mod)
  product %= mod

b = mod-2
blis = []
c = 0
while b >0:
  if b & 1 == 1:
    blis.append(c)
  c += 1
  b >>= 1

def modinv(a):
  if a == 1:
    return 1
  else:
    res = 1
    li = []
    for _ in range(c):
      li.append(a%mod)
      a = a*a%mod
    for item in blis:
      res = res *li[item] %mod
    return res

ans = 0
for k in range(N):
  ans += product*modinv(A[k])
  ans %= mod

print(ans)

Solution (Python):
N = int(input())
A = list(map(int, input().split()))
mod = 10**9 + 7
a = max(A)
prime_num = [2]
sgn = [0 for _ in range(max(int(a**0.5)+1, 4))]
sgn[2] = 1
for k in range(3, len(sgn), 2):
  if sgn[k] == 0:
    prime_num.append(k)
    for j in range(k, a+1, 2*k):
      sgn[k] = 1
baisu = []
count = [0 for _ in range(a+1)]
for k in range(N):
  b = 0 + A[k]
  for p in prime_num:
    if p**2 <= b:
      if b%p == 0:
        if count[p] == 0:
          baisu.append(p)
        c = 0
        while b % p == 0:
          b //= p 
          c += 1 
        if c > count[p]:
          count[p] = c
    else:
      break
  if b != 1:
    if count[b] == 0:
      count[b] = 1
      baisu.append(b)

product = 1
for item in baisu:
  product *= pow(item, count[item], mod)
  product %= mod

b = mod-2
blis = []
c = 0
while b >0:
  if b & 1 == 1:
    blis.append(c)
  c += 1
  b >>= 1

def modinv(a):
  if a == 1:
    return 1
  else:
    res = 1
    li = []
    for _ in range(c):
      li.append(a%mod)
      a = a*a%mod
    for item in blis:
      res = res *li[item] %mod
    return res

ans = 0
for k in range(N):
  ans += product*modinv(A[k])
  ans %= mod

print(ans)

Solution (Python):

from math import gcd
from functools import reduce


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


N = int(input())
X = list(map(int, input().split()))
total = reduce(lcm, X)
MOD = 10 ** 9 + 7

ans = 0
for v in X:
    ans += total * pow(v, MOD - 2, MOD) % MOD
    ans %= MOD

print(ans)

Solution (Python):
from collections import defaultdict


def prime_factor(n):
    d = defaultdict(int)
    for i in range(2, n + 1):
        if i * i > n:
            break

        while n % i == 0:
            d[i] += 1
            n //= i

    if n != 1:
        d[n] += 1

    return d


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

ctr = defaultdict(int)
buf = []
for n in X:
    d = prime_factor(n)
    buf.append(d)
    for key in d:
        ctr[key] = max(ctr[key], d[key])

total = 1
for key, val in ctr.items():
    total *= pow(key, val, MOD)
    total %= MOD

ans = 0
for i, n in enumerate(X):
    cur = total
    for key, val in buf[i].items():
        cur = cur * pow(pow(key, val, MOD), MOD - 2, MOD) % MOD

    ans += cur
    ans %= MOD

print(ans)

Solution (Python):
n=int(input())
a=[int(x) for x in input().rstrip().split()]

now=1
mod=10**9+7
def lcm(a,b):
    ori_a=a
    ori_b=b
    while b!=0:
        a,b=b,a%b
    return (ori_a*ori_b)//a
  
for i in a:
  now=lcm(i,now)

print(sum([now//i for i in a])%mod)

Solution (Python):
def make_prime_table(n):
    sieve = list(range(n + 1))
    sieve[0] = -1
    sieve[1] = -1
    for i in range(4, n + 1, 2):
        sieve[i] = 2
    for i in range(3, int(n ** 0.5) + 1, 2):
        if sieve[i] != i:
            continue
        for j in range(i * i, n + 1, i * 2):
            if sieve[j] == j:
                sieve[j] = i
    return sieve


def prime_factorize(n):
    result = []
    while n != 1:
        p = prime_table[n]
        e = 0
        while n % p == 0:
            n //= p
            e += 1
        result.append((p, e))
    return result


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

m = 1000000007

prime_table = make_prime_table(10 ** 6)

lcm_factors = {}
for a in A:
    for p, e in prime_factorize(a):
        if p not in lcm_factors or lcm_factors[p] < e:
            lcm_factors[p] = e

lcm = 1
for p in lcm_factors:
    lcm *= pow(p, lcm_factors[p], m)
    lcm %= m

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

Solution (Python):


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7
def main():
    n=I()
    lis=LI()
    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
    lists=[Counter(prime_factorize(lis[i])) for i in range(n)]
    C=Counter([])
    for i in range(n):
        x=lists[i]
        for j in x.keys():
            C[j]=max(C[j],x[j])
    
    
    ans=1
    '''for i in range(n):
        x=lists[i]
        y=1
        for j in C.keys():
            y=(y*pow(j,C[j]-x[j],mod))%mod
        
        ans=(ans+y)%mod
    print(ans%mod)'''
    invmod=0
    for i in range(n):
        invmod=(invmod+pow(lis[i]%mod,mod-2,mod))%mod
    for x in C.keys():
        ans=(ans*pow(x,C[x],mod))%mod
    print(ans*invmod%mod)
        
if __name__=="__main__":
    main()

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


def primeFactor(n):
    res = defaultdict(lambda: 0)
    for i in range(2, int(n**0.5)+1):
        while n % i == 0:
            res[i] += 1
            n = n // i
    if n != 1:
        res[n] += 1
    return res

    

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

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

MOD = 10**9+7
GCD = gcd(*A)

P = defaultdict(lambda: 0)

for i in range(N):
    factors = primeFactor(A[i])
    for k, v in factors.items():
        if v > P[k]:
            P[k] = v


P_mod = 1
for k in P.keys():
    P_mod = P_mod*(k**P[k])%MOD

ans = 0
for i in range(N):
    b = A[i]
    mod_inv = pow(b, MOD-2, MOD)
    ans = (ans + P_mod * mod_inv) % MOD

print(ans)

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

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

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

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

print(ans % 1000000007)

Solution (Python):
n = int(input())
a = list(map(int,input().split()))
so_list = [0 for i in range(10**6)]
mod = 10**9+7

def fac(n):
    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
            if so_list[i]<cnt:
              so_list[i]= cnt
    if temp!=1:
    
      if so_list[temp]==0:
        so_list[temp]=1
for i in range(n):
  a1 = a[i]
  fac(a1)
l = 1
for i in range(len(so_list)):
  if so_list[i]!=0:
    l *= pow(i,so_list[i],mod)
    l %= mod
ans = 0

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

Solution (Python):


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

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

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





n=I()
lis=LI()
promod=1
LCM=1
for i in range(n):
    LCM=lcm(lis[i],LCM)


for i in range(n):
    promod=(promod*(lis[i]%mod))%mod
smmod=0
for i in range(n):
    smmod=(smmod+promod*pow(lis[i],mod-2,mod))%mod

x=(promod*pow(LCM%mod,mod-2,mod))%mod
ans=(smmod*pow(x,mod-2,mod))%mod
print(ans)

Solution (Python):


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

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

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





n=I()
lis=LI()
promod=1
LCM=1
for i in range(n):
    LCM=lcm(lis[i],LCM)

for i in range(n):
    promod=(promod*(lis[i]%mod))%mod
smmod=0
for i in range(n):
    smmod=(smmod+promod*pow(lis[i],mod-2,mod))%mod

x=(promod*pow(LCM,mod-2,mod))%mod
ans=(smmod*pow(x,mod-2,mod))%mod
print(ans)

Solution (Python):
import math
from functools import reduce

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

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

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

l = lcm(*a)

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

Solution (Python):
import math
from functools import reduce

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

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

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

l = lcm(*a)

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

Solution (Python):
N = int(input())
*A, = map(int, input().split())

mod = 10**9 + 7
MAX = 1_000_000


def gen_primes(n):
    n = int(n**0.5) + 2
    is_prime = [True]*n
    is_prime[0] = is_prime[1] = False
    for i in range(2, n):
        if is_prime[i]:
            for j in range(2*i, n, i):
                is_prime[j] = False
    return [i for i, flag in enumerate(is_prime) if flag]


C = [0]*(MAX+1)
primes = gen_primes(MAX)


def prime_fact(n):
    cnt = 0
    for p in primes:
        if n % p:
            continue
        while n % p == 0:
            cnt += 1
            n //= p
        C[p] = max(C[p], cnt)
        cnt = 0
    if n != 1:
        C[n] = 1


for a in A:
    prime_fact(a)

lcm = 1
for i, c in enumerate(C):
    if c:
        lcm = lcm * pow(i, c, mod) % mod

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

Solution (Python):
import numpy as np

class SieveOfEratosthenes:
    def __init__(self, V):
        self.is_prime = np.ones(V + 1, dtype=bool)
        self.is_prime[4::2] = False
        self.is_prime[9::3] = False
        self.is_prime[25::5] = False
        self.primes = [2, 3, 5]
        for i in range(7, V + 1, 2):
            if self.is_prime[i]:
                self.primes.append(i)
                self.is_prime[i * i::i] = False
    
    def factorize(self, x):
        assert x >= 1
        if x == 1:
            return [(1, 1)]
        result = []
        for p in self.primes:
            exp = 0
            while x % p == 0:
                exp += 1
                x = x // p
            if exp > 0:
                result.append((p, exp))
            if p * p > x:
                break
        if x > 1:
            result.append((x, 1))
        return result


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

sieve = SieveOfEratosthenes(10**3)
F = [dict(sieve.factorize(a)) for a in A]

lcm = F[0]
for i in range(1, len(F)):
    for p, e in F[i].items():
        if p in lcm:
            lcm[p] = max(lcm[p], e)
        else:
            lcm[p] = e

val = 1
for p, e in lcm.items():
    val = val * pow(p, e, M) % M


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

Solution (Python):
import numpy as np

class SieveOfEratosthenes:
    def __init__(self, V):
        self.is_prime = np.ones(V + 1, dtype=bool)
        self.is_prime[4::2] = False
        self.is_prime[9::3] = False
        self.is_prime[25::5] = False
        self.primes = [2, 3, 5]
        for i in range(7, V + 1, 2):
            if self.is_prime[i]:
                self.primes.append(i)
                if i * i < V + 1:
                    self.is_prime[i * i::i] = False
    
    def factorize(self, x):
        assert x >= 1
        if x == 1:
            return [(1, 1)]
        result = []
        for p in self.primes:
            exp = 0
            while x % p == 0:
                exp += 1
                x = x // p
            if exp > 0:
                result.append((p, exp))
            if p * p > x:
                break
        if x > 1:
            result.append((x, 1))
        return result


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

sieve = SieveOfEratosthenes(10**3)
F = [dict(sieve.factorize(a)) for a in A]

lcm = F[0]
for i in range(1, len(F)):
    for p, e in F[i].items():
        if p in lcm:
            lcm[p] = max(lcm[p], e)
        else:
            lcm[p] = e

val = 1
for p, e in lcm.items():
    val = val * pow(p, e, M) % M


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

Solution (Python):
import numpy as np

class SieveOfEratosthenes:
    def __init__(self, V):
        self.is_prime = np.ones(V + 1, dtype=bool)
        self.is_prime[2::2] = False
        self.is_prime[3::3] = False
        self.is_prime[5::5] = False
        self.primes = [2, 3, 5]
        for i in range(7, V + 1, 2):
            if self.is_prime[i]:
                self.primes.append(i)
                if i * i < V + 1:
                    self.is_prime[i * i::i] = False
    
    def factorize(self, x, return_dict=False):
        if x == 1:
            return {1:1} if return_dict else [(1, 1)]
        result = []
        for p in self.primes:
            exp = 0
            while x % p == 0:
                exp += 1
                x = x // p
            if exp > 0:
                result.append((p, exp))
            if p * p > x:
                break
        if x > 1:
            result.append((x, 1))
        if return_dict:
            result = {p: e for p, e in result}
        return result


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

sieve = SieveOfEratosthenes(10**3)
F = [sieve.factorize(a, return_dict=True) for a in A]

lcm = F[0]
for i in range(1, len(F)):
    for p, e in F[i].items():
        if p in lcm:
            lcm[p] = max(lcm[p], e)
        else:
            lcm[p] = e

val = 1
for p, e in lcm.items():
    val = val * pow(p, e, M) % M

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

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


class PrimeFactor():

    def __init__(self, n):                  
        self.n = n
        self.table = list(range(n+1))       
        self.table[2::2] = [2]*(n//2)
        for p in range(3, int(n**0.5) + 2, 2):
            if self.table[p] == p:
                for q in range(p * p, n + 1, 2 * p):
                    if self.table[q] == q:
                        self.table[q] = p

    def is_prime(self, x):  
        if x < 2:
            return False
        return self.table[x] == x

    def prime_factors(self, x):             
        res = []
        if x < 2:
            return res
        while self.table[x] != 1:
            res.append(self.table[x])
            x //= self.table[x]
        return res

    def prime_counter(self, x):             
        res = defaultdict(int)
        if x < 2:
            return res
        while self.table[x] != 1:
            res[self.table[x]] += 1
            x //= self.table[x]
        return res

    def prime_gcd(self, X, mod=None):        
        exponents = self.prime_counter(X[0])
        for x in X[1:]:
            Y = self.prime_counter(x)
            for prime, exp in exponents.items():
                if Y[prime] < exp:
                    exponents[prime] = Y[prime]
        res = 1
        for prime, exp in exponents.items():
            res *= pow(prime, exp, mod)
        if mod == None:
            return res
        else:
            return res % mod

    def prime_lcm(self, X, mod=None):       
        exponents = defaultdict(int)
        for x in X:
            for prime, exp in self.prime_counter(x).items():
                if exp > exponents[prime]:
                    exponents[prime] = exp
        res = 1
        for prime, exp in exponents.items():
            res *= pow(prime, exp, mod)
        if mod == None:
            return res
        else:
            return res % mod





int(input())
N = 10**6 + 1
table = PrimeFactor(N)
A = list(map(int, input().split()))
MOD = 10**9+7
temp = table.prime_lcm(A,MOD)
res = 0
for a in A:
    res += temp*pow(a,MOD-2,MOD)
print(res%MOD)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

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

import collections
lcm_pf = collections.defaultdict(int)
for i, v in enumerate(a):
    j = 2
    pf = {}
    while j ** 2 <= v:
        ext = 0
        while v % j == 0:
            ext += 1
            v //= j
        if ext:
            pf[j] = ext
            lcm_pf[j] = max(lcm_pf[j], ext)
        j += 1
    if v != 1:
        pf[v] = 1
        lcm_pf[v] = max(lcm_pf[v], 1)
for p in lcm_pf:
    lcm = lcm * (p ** lcm_pf[p])




ans = 0
for v in a:
    ans = ans + (lcm // v)
    
print(ans % MOD)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

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




















import math
for v in a:
    lcm = (lcm // math.gcd(lcm, v)) * v

ans = 0
for v in a:
    ans = ans + (lcm // v)
    
print(ans % MOD)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

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

import collections

lcm_pf = collections.defaultdict(int)
for i, v in enumerate(a):
    j = 2
    pf = {}
    while j ** 2 <= v:
        ext = 0
        while v % j == 0:
            ext += 1
            v //= j
        if ext:
            pf[j] = ext
            lcm_pf[j] = max(lcm_pf[j], ext)
        j += 1
    if v != 1:
        pf[v] = 1
        lcm_pf[v] = max(lcm_pf[v], 1)

lcm = 1
for p in lcm_pf:
    lcm = lcm * (p ** lcm_pf[p])

ans = 0
for v in a:
    ans = ans + (lcm // v)
print(ans % MOD)