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 sys,math,collections,itertools
input = sys.stdin.readline
m=10**9+7
"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""

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

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

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

    return arr

N=int(input())
A=list(map(int,input().split()))
d = collections.defaultdict(int)
for a in A:
    arr = factorization(a)
    for ar in arr:
        if d[ar[0]]<ar[1]:
            d[ar[0]]=ar[1]

gcd = 1
for key,val in d.items():
    gcd = gcd*pow(key,val)

ans = 0
for a in A:
    ans = ans+gcd//a
print(ans%m)

Solution (Python):
import sys
import math
import copy
from heapq import heappush, heappop, heapify
from functools import cmp_to_key
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque, Counter



input = sys.stdin.readline
getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = float("inf")
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)


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


def isPrimeMR(n):
    d = n - 1
    d = d // (d & -d)
    L = [2]
    for a in L:
        t = d
        y = pow(a, t, n)
        if y == 1: continue
        while y != n - 1:
            y = (y * y) % n
            if y == 1 or t == n - 1: return 0
            t <<= 1
    return 1


def findFactorRho(n):
    m = 1 << n.bit_length() // 8
    for c in range(1, 99):
        f = lambda x: (x * x + c) % n
        y, r, q, g = 2, 1, 1, 1
        while g == 1:
            x = y
            for i in range(r):
                y = f(y)
            k = 0
            while k < r and g == 1:
                ys = y
                for i in range(min(m, r - k)):
                    y = f(y)
                    q = q * abs(x - y) % n
                g = gcd(q, n)
                k += m
            r <<= 1
        if g == n:
            g = 1
            while g == 1:
                ys = f(ys)
                g = gcd(abs(x - ys), n)
        if g < n:
            if isPrimeMR(g):
                return g
            elif isPrimeMR(n // g):
                return n // g
            return findFactorRho(g)


def primeFactor(n):
    i = 2
    ret = {}
    rhoFlg = 0
    while i * i <= n:
        k = 0
        while n % i == 0:
            n //= i
            k += 1
        if k: ret[i] = k
        i += 1 + i % 2
        if i == 101 and n >= 2 ** 20:
            while n > 1:
                if isPrimeMR(n):
                    ret[n], n = 1, 1
                else:
                    rhoFlg = 1
                    j = findFactorRho(n)
                    k = 0
                    while n % j == 0:
                        n //= j
                        k += 1
                    ret[j] = k

    if n > 1: ret[n] = 1
    if rhoFlg: ret = {x: ret[x] for x in sorted(ret)}
    return ret

def solve():
    n = getN()
    nums = getList()
    d = dict()
    for num in nums:
        res = primeFactor(num)
        for k, v in res.items():
            if k not in d:
                d[k] = v
            elif d[k] < v:
                d[k] = v


    big = 1
    for k, v in d.items():
        big *= pow(k, v, MOD)
        big %= MOD
    ans = 0
    for num in nums:
        ans += big * divide(num)
        ans %= MOD

    print(ans)

def main():
    n = getN()
    for _ in range(n):
        solve()

    return
if __name__ == "__main__":
    
    solve()

Solution (Python):
from math import gcd
def inv(n, p):
    """
    mod p の逆元
    """
    return pow(n, p-2, p)
def lcm(a, b):
    return a*b//gcd(a,b)
def main():
    N = int(input())
    A = list(map(int, input().split()))
    mod = 10**9 + 7
    LCM = 1
    for a in A:
        LCM = lcm(LCM, a)
    ans = 0
    for a in A:
        ans += inv(a, mod)
    ans *= LCM % mod

    print(ans % mod)
main()

Solution (Python):
from math import gcd

def mod_prod(X,M):
    c=1
    for x in X:
        c*=x
        c%=M
    return c

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

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

P=mod_prod(E,Mod)

Q=0
for a in A:
    Q+=pow(a,Mod-2,Mod)
    Q%=Mod
print((P*Q)%Mod)

Solution (Python):
import math

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

mod = 10**9+7

primes = [0]*(10**6+1)

def prime_fac(n):
  temp = n
  Flag = True
  for i in range(2, int(math.sqrt(n)) + 1):
    if temp % i == 0:
      cnt = 0
      while temp % i == 0:
        cnt += 1
        temp //= i
      primes[i] = max(primes[i], cnt)
      Flag = False
  if temp != 1:
    primes[temp] = max(primes[temp], 1)
  if Flag:
    primes[n] = max(primes[n], 1)

for a in A:
  prime_fac(a)

LCM = 1
for p, i in enumerate(primes):
  if i:
    LCM *= pow(p, i, mod)
    LCM %= mod

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

print(ans)

Solution (Python):
import math

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

mod = 10**9+7

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

LCM = A[0]
for i in range(N-1):
  LCM = lcm(LCM, A[i+1])



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

print(ans)

Solution (Python):
import math

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

mod = 10**9+7

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

LCM = A[0]
for i in range(N-1):
  LCM = lcm(LCM, A[i+1])

LCM %= mod

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

print(ans)

Solution (Python):
import math
from functools import reduce


N = int(input())
A = list(map(int, input().split()))
P = int(1e9+7)

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


def lcm(iter):
    return reduce(lcm_base, iter, 1)


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

Solution (Python):
from collections import defaultdict
MOD = 10 ** 9 + 7

n = int(input())
alst = list(map(int, input().split()))
dd = defaultdict(int)
ans = 0
for a in alst:
    ans += pow(a, MOD - 2, MOD)
    ans %= MOD
    num = a
    for i in range(2, int(a ** 0.5) + 1):
        cnt = 0
        while num % i == 0:
            num //= i
            cnt += 1
        if cnt > 0:
            dd[i] = max(dd[i], cnt)
    if num != 1:
        dd[num] = max(dd[num], 1)
for key, value in dd.items():
    ans *= pow(key, value, MOD)
    ans %= MOD
print(ans)

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


def lcm(X,Y):
    x=X
    y=Y
    if y>x:
        x,y=y,x
    while x%y!=0:
        x,y=y,x%y
    return X*Y//y


a = 1
c = 0
s = 0
for i in range(n):
  q = lcm(a,A[i])
  s*=q//a
  a = q
  s+=q//A[i]
print(s%mod)

Solution (Python):

from collections import defaultdict

def factorize(n):
    """

    """
    tmp = n
    for i in range(2, int(n**0.5)+1):
        if tmp % i==0:
            cnt = 0
            while tmp % i == 0:
                cnt += 1
                tmp //= i
            if i in LCM:
                LCM[i] = max(LCM[i], cnt)
            else:
                LCM[i] = cnt
    if tmp != 1:
        if tmp in LCM:
            LCM[tmp] = max(LCM[tmp], 1)
        else:
            LCM[tmp] = 1
    if not LCM:
        if n in LCM:
            LCM[n] = max(LCM[n], 1)
        else:
            LCM[n] = 1
def inv(n, p):
    return pow(n, p-2, p)

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

for i in range(N):
    if A[i] != 1:
        factorize(A[i])

lcm = 1
for key, val in LCM.items():
    lcm *= pow(key, val, mod)
    lcm %= mod

inv_sum = 0
for i in range(N):
    inv_sum += inv(A[i], mod)
    inv_sum %= mod

print(lcm * inv_sum % mod)

Solution (Python):
from math import gcd

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

    print(ans % mod)
main()

Solution (Python):
def factorize(n):
    tmp = n

    for i in range(2, int(n**0.5)+1):
        if tmp % i == 0:
            cnt = 0
            while tmp % i == 0:
                cnt += 1
                tmp //= i
            if i in fact:
                fact[i] = max(fact[i],cnt)
            else:
                fact[i] = cnt
         
    if tmp != 1:
        if tmp in fact:
            fact[tmp] = max(fact[tmp],1)
        else:
            fact[tmp] = 1
    
    if len(fact) == 0:
        if N in fact:
            fact[N] = max(fact[N],1)
        else:
            fact[N] = 1

def inv(n, p):
    return pow(n, p-2, p)
    
N = int(input())
A = list(map(int, input().split()))
p = 10**9+7

fact = {}

for i in range(N):
    if A[i] != 1:
        factorize(A[i])

lcm = 1

for key, val in fact.items():
    lcm *= pow(key, val, p)
    lcm %= p

inv_sum = 0

for i in range(N):
    inv_sum += inv(A[i], p)
    inv_sum %= p

print(lcm * inv_sum % p)

Solution (Python):
n,*aa = map(int, open(0).read().split())
MOD = 10**9+7

from collections import defaultdict
from math import sqrt, ceil
def factors(x):
    d = defaultdict(int)
    while x % 2 == 0:
        d[2] += 1
        x //= 2
    for i in range(3, ceil(sqrt(x)) + 2, 2):
        while x % i == 0:
            d[i] += 1
            x //= i
    if x > 1:
        d[x] += 1
    return d

factors_of_aa = list(map(factors, aa))

factors_of_lcm = defaultdict(int)
for factors_of_a in factors_of_aa:
    for k in factors_of_a:
        factors_of_lcm[k] = max(factors_of_lcm[k], factors_of_a[k])
lcm = 1
for factor, cnt in factors_of_lcm.items():
    lcm *= pow(factor, cnt, MOD)

ans = 0
for factors_of_a in factors_of_aa:
    to_add = lcm
    for factor, cnt in factors_of_a.items():
        to_add *= pow(factor, -cnt, MOD)
        to_add %= MOD
    ans += to_add
    ans %= MOD

print(ans)

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

mod=1000000007
n=input();
arr = list(map(int, raw_input().split()))
l=arr[0];
for i in arr:
    x=gcd(l,i)
    l=(l*i)/x
    
ans=0

for i in arr:
    b=l/i
    ans+=b
ans=(ans%mod +mod)%mod
print ans

Solution (Python):
from math import gcd
mod=10**9+7
n=int(input())
a=list(map(int,input().split()))
c=a[0]
for i in a[1:]:
  c=c*i//gcd(c,i)
ans=0
c%=mod
for i in a:
  ans+=c*pow(i,mod-2,mod)
  ans%=mod
print(ans)

Solution (Python):
from collections import Counter




def fast_prime_factorization_many(lst):
    
    from subprocess import Popen, PIPE
    res = Popen(["factor"] + list(map(str, lst)), stdout=PIPE).communicate()[0].split(b"\n")[:-1]
    return [Counter(list(map(int, r.split()[1:]))) for r in res]


def main():
    import sys
    input = sys.stdin.readline
    N = int(input())
    A = list(map(int, input().split()))
    if N == 1:
        print(1)
        exit(0)

    mod = int(1e9+7)
    Factors = fast_prime_factorization_many(A)
    
    
    lcm = 1
    max_factor = [0] * (1000010)
    for f in Factors:
        for k, v in f.items():
            v_prev = max_factor[k]
            if v_prev < v:
                for i in range(v-v_prev):
                    lcm = lcm * k % mod
                max_factor[k] = v

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


main()

Solution (Python):
from itertools import groupby
from collections import Counter


def fast_prime_factorization_many(lst):
  
  from subprocess import Popen, PIPE
  res = Popen(["factor"] + list(map(str, lst)), stdout=PIPE).communicate()[0].split(b"\n")[:-1]
  return [Counter(list(map(int, r.split()[1:]))) for r in res]

def main():
  import sys
  input = sys.stdin.readline
  N = int(input())
  A = list(map(int, input().split()))
  if N == 1:
    print(1)
    exit(0)
  
  mod = int(1e9+7)
  Factors = fast_prime_factorization_many(A)
  
  
  lcm = 1
  max_factor = [0] * (1000010)
  for f in Factors:
    for k,v in f.items():
      v_prev = max_factor[k]
      if v_prev < v:
        for i in range(v-v_prev):
          lcm = lcm * k % mod
        max_factor[k] = v
        
  
  ans = 0
  for a in A:
    wk =  lcm * pow(a,mod-2,mod)
    
    ans += wk
    ans %= mod
  print(ans)
  exit(0)
  
main()

Solution (Python):
import math
from collections import defaultdict, Counter

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

N = int(input())
A = [int(i) for i in input().split()]
v_list = []
mod = 10 ** 9 + 7
LCM_dict = defaultdict(int)
for i in range(N):
    prime_cnt = Counter(prime_factorize(A[i]))
    for k, v in prime_cnt.items():
        LCM_dict[k] = max(LCM_dict[k], v)
    v_list.append(prime_cnt)
ans = 0
for i in range(N):
    prime_cnt = v_list[i]
    tmp_value = 1
    for k, v in LCM_dict.items():
        cnt = 0 if k not in prime_cnt.keys() else prime_cnt[k]
        tmp_value = pow(k, v - cnt) * tmp_value
        tmp_value = tmp_value % mod
    ans += tmp_value
    ans = ans % mod
print(ans)

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from operator import mul


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n = I()
A = LI()



D = defaultdict(int)
for i in range(n):
    a = A[i]
    Di = defaultdict(int)
    for j in range(2, int(a ** 0.5) + 1):
        while a % j == 0:
            a //= j
            Di[j] += 1
    if a:
        Di[a] += 1
    for k in Di:
        D[k] = max(D[k], Di[k])

ret = 1
for ki in D:
    ret = ret * pow(ki, D[ki], mod)
    ret %= mod

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

print(ans)

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from operator import mul


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n = I()
A = LI()



D = defaultdict(int)
for i in range(n):
    a = A[i]
    Di = defaultdict(int)
    for j in range(2, int(a ** 0.5) + 1):
        while a % j == 0:
            a //= j
            Di[j] += 1
        if a == 0:
            break
    if a:
        Di[a] += 1
    for k in Di:
        D[k] = max(D[k], Di[k])

ret = 1
for ki in D:
    ret = ret * pow(ki, D[ki], mod)
    ret %= mod

ans = 0
for a in A:
    ans += ret * pow(a, mod - 2, 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,mod):
    return a*b//gcd(a,b)
 
N = int(input())
A = list(map(int,input().split()))
mod = 10**9+7
b = 1
for i in range(N):
    a = A[i]
    b = lcm(a,b,mod)
ans = 0
for a in A:
    ans += b//a
print(ans%mod)

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

def gcd(x, y):
  while(x % y != 0 and y % x != 0):
    if(x > y):
      x = x % y
    else:
      y = y % x
  if(x > y):
    return y
  else:
    return x
      
def lcm(x, y, MOD):
  return x * y // gcd(x, y)

X = 1
ans = 0
for i in range(N):
  X = lcm(X, A[i], MOD)
for i in range(N):
  ans = (ans + X*pow(A[i], MOD-2, MOD))%MOD
print(ans)

Solution (Python):
def main():
    import copy
    n = int(input())
    a = list(map(int,input().split()))
    A = copy.deepcopy(a)
    mod = 10**9+7
    l = {}
    for i in range(n):
        for j in range(2,int(a[i]**0.5)+1):
            if a[i]%j==0:
                cnt = 0
                while a[i]%j==0:
                    cnt += 1
                    a[i] = a[i]//j
                if l.get(j)==None:
                    l[j] = cnt
                else:
                    l[j] = max(cnt,l[j])
        if a[i]!=1:
            if l.get(a[i])==None:
                l[a[i]] = 1
    L = 1
    for k in l.keys():
        L *= pow(k,l[k],mod)
    L = L%mod
    ans = 0
    for i in range(n):
        ans += L * pow(A[i],mod-2,mod) % mod
        ans = ans % mod
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
import sys, bisect, math, itertools, string, queue, copy
import numpy as np
import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
from fractions import gcd
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

n = inp()
A = inpl()

def lcm(A):
    from fractions import gcd
    x = A[0]
    for a in A:
        x = (x * a) // math.gcd(x, a)
    return x

l = lcm(A)

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

print(ans % mod)

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

def gcd(a, b):
    return b if a % b == 0 else gcd(b, a % b)
def lcm(a, b):
    return a * b // gcd(a, b)
hoge = 1
for p in l:
    hoge = lcm(hoge, p)
ans = 0
for p in l:
    ans += hoge // p
print(ans % int(1e9 + 7))

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

mod = 1000000007

def add(a, b):
    return (a + b) % mod

def mul(a, b):
    return (a * b) % mod

def pow(p, k):
    ret = 1
    b = p
    while k > 0:
        if k % 2 == 1:
            ret = mul(ret, b)
        b = mul(b, b)
        k //= 2
    return ret

def inv(p, k):
    return pow(p, mod - k - 1)

lcm = {}
ps = []
for i in range(n): 
    ai = a[i]
    p = 2
    ps.append({})
    while ai > 1:
        if ai % p == 0:
            ps[i][p] = 0
            while ai % p == 0:
                ps[i][p] += 1
                ai //= p
            lcm[p] = max(lcm.get(p, 0), ps[i][p])
        p = p + 1 if p * p < ai else ai

lcmv = 1
for p in lcm:
    lcmv = mul(lcmv, pow(p, lcm[p]))

ret = 0
for i in range(n):
    prod = lcmv
    for p in ps[i]:
        prod = mul(prod, inv(p, ps[i][p]))
    ret = add(ret, prod)

print(ret)

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

mod = 1000000007

lcm = {}
ps = []
for i in range(n): 
    ai = a[i]
    p = 2
    ps.append({})
    while p * p <= ai:
        if ai % p == 0:
            ps[i][p] = 0
            while ai % p == 0:
                ps[i][p] += 1
                ai //= p
            lcm[p] = max(lcm.get(p, 0), ps[i][p])
        p += 1
    if ai > 1:
        ps[i][ai] = 1
        lcm[ai] = max(lcm.get(ai, 0), ps[i][ai])

lcmv = 1
for p in lcm:
    lcmv = (lcmv * (p ** lcm[p])) % mod

def inv(p, k):
    k = mod - k - 1
    ret = 1
    b = p
    while k > 0:
        if k % 2 == 1:
            ret = (ret * b) % mod
        b = (b * b) % mod
        k //= 2
    return ret

ret = 0
for i in range(n):
    prod = lcmv
    for p in ps[i]:
        prod = (prod * inv(p, ps[i][p])) % mod
    ret = (ret + prod) % mod

print(ret)

Solution (Python):
import sys
from collections import defaultdict

mod = 10 ** 9 + 7


def factorization(n):
    """ n の素因数分解

    Args:
        n (int): [description]

    Returns:
        [type]: [description]
    """

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

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

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

    return arr


def main():

    N = int(sys.stdin.readline().rstrip())
    A = [int(x) for x in sys.stdin.readline().rstrip().split()]

    
    p = defaultdict(int)  
    for a in A:
        for x, y in factorization(a):
            p[x] = max(p[x], y)

    
    U = 1
    for x, y in p.items():
        U = (U * pow(x, y, mod)) % mod

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

    print(ans)


main()

Solution (Python):
n = int(input())
a = list(map(int, input().split()))
mod = 10**9+7
from math import gcd
cm = 1
for i in range(n):
    cm = cm*a[i]//gcd(cm, a[i])
ai = sum(pow(x, mod-2, mod) for x in a)
print(int(ai*cm%mod))

Solution (Python):
import sys
from io import StringIO
import unittest
import os
import copy


sys.setrecursionlimit(999999999)



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 resolve(test_def_name=""):
    n = int(input())
    a_s = list(map(int, input().split()))

    input_fact_s = []
    need_s = {}
    
    for a in a_s:
        aaa = factorization(a)
        input_fact_s.append(aaa)
        for fact in aaa:
            need_s[fact[0]] = max(fact[1], need_s.get(fact[0], 0))
    lcm = 1
    for val, cnt in need_s.items():
        lcm = (lcm * pow(val, cnt))

    ans = 0
    for a in a_s:
        ans += lcm // a

    print(ans % (pow(10, 9) + 7))

    


class TestClass(unittest.TestCase):
    def assertIO(self, assert_input, output):
        stdout, sat_in = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(assert_input)
        resolve(sys._getframe().f_back.f_code.co_name)
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, sat_in
        self.assertEqual(out, output)

    def test_input_1(self):
        test_input = """3
2 3 4"""
        output = """13"""
        self.assertIO(test_input, output)

    def test_input_2(self):
        test_input = """5
12 12 12 12 12"""
        output = """5"""
        self.assertIO(test_input, output)

    def test_input_3(self):
        test_input = """3
1000000 999999 999998"""
        output = """996989508"""
        self.assertIO(test_input, output)

    
    def tes_t_1original_1(self):
        test_input = """データ"""
        output = """データ"""
        self.assertIO(test_input, output)



if __name__ == "__main__":
    if os.environ.get("USERNAME") is None:
        
        resolve()

    else:
        
        unittest.main()

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

def gcd(a, b):
    return b if a % b == 0 else gcd(b, a % b)
def lcm(a, b):
    return a * b // gcd(a, b)
hoge = 1
for p in l:
    hoge = lcm(hoge, p)
ans = 0
for p in l:
    ans += hoge // p
print(ans % int(1e9 + 7))

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 

from decimal import *



N = INT()
A = LIST()


def factorization(n):
	arr = []
	tmp = n
	for i in range(2, int(-(-n**0.5//1))+1):
		if tmp%i == 0:
			cnt = 0
			while tmp%i == 0:
				cnt += 1
				tmp //= i
			arr.append([i, cnt])
	if tmp != 1:
		arr.append([tmp, 1])
	if arr == []:
		arr.append([n, 1])
	return arr
	
p = defaultdict(int)
for a in A:
	for x, y in factorization(a):
		p[x] = max(p[x], y)

U = 1
for x, y in p.items():
	U = (U*pow(x, y, mod))%mod
ans = 0
for a in A:
	ans = (ans+U*pow(a, mod-2, mod))%mod

print(ans)

Solution (Python):
from itertools import groupby

def fast_prime_factorization_many(lst):
    
    from subprocess import Popen, PIPE
    res = Popen(["factor"] + list(map(str, lst)), stdout=PIPE).communicate()[0].split(b"\n")[:-1]
    return [list(map(int, r.split()[1:])) for r in res]

def main():
    N = int(input())
    A = list(map(int, input().split()))
    mod = 10**9+7
    max_factor = [0] * (1010101)
    lcm = 1
    Factors = fast_prime_factorization_many(A)
    for factors in Factors:
        for prime, group in groupby(factors):
            n = len(list(group))
            n_old = max_factor[prime]
            if n_old < n:
                for i in range(n - n_old):
                    lcm = lcm * prime % mod
                max_factor[prime] = n
    ans = 0
    for a in A:
        ans += pow(a, mod-2, mod)
    ans = ans * lcm % mod
    print(ans)

main()

Solution (Python):
import math
 
mod = 1000000007
 
def lcm(x, y):
    return (x * y) // math.gcd(x, y)
 
n=int(input())
 
a = list(map(int,input().split()))
 
memo = a[0]
 
for i in range(1,n):
    memo = lcm(memo,a[i])
 
ans = 0
 
for i in range(n):
    ans += memo*pow(a[i], mod-2, mod)%mod
    ans %= mod
 
print(ans)

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

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

    def lcm(a, b): return a * b // math.gcd(a, b)
    l = reduce(lcm, A, 1) % MOD

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

    print(ans)





if __name__ == '__main__':
    main()

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

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

    def lcm(a, b): return a * b // math.gcd(a, b)
    l = reduce(lcm, A, 1)

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

    print(ans)





if __name__ == '__main__':
    main()