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()))
c=[1]*(10**3+1)
p={}
q=[]
m=10**9+7
for i in range(2,10**3+1):
    if c[i]:
        p[i]=0
        q.append(i)
        for j in range(i*2,10**3+1,i):
            c[j]=0
for j in a:
    i=0
    while j!=1:
        if j%q[i]==0:
            d=0
            while j%q[i]==0:
                j//=q[i]
                d+=1
            p[q[i]]=max(p[q[i]],d)
        i+=1
        if i==168:
            break
    p[j]=1
e=1
for i in p.keys():
    e=(e*pow(i,p[i],m))%m
c=0
for i in a:
    c=(c+e*pow(i,m-2,m))%m
print(c)

Solution (Python):
import fractions

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

aset = set(a)

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

if n == 1:
    print(1)

elif 1 < n:
    g = lcm(a[0], a[1])

    if n != 2:
        for val in aset:
            g = lcm(g, val)

    ans = 0
    for val in a:
        ans += g//val

    print(ans % mod)

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)

lcm_a = 1

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

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

mod = int(1e9+7)

print(ans%mod)

Solution (Python):

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

def gcd(a, b):
    while b > 0:
        c = a % b
        a = b
        b = c
    return int(a)

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

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

ans = 0
MOD = int(1e9 + 7)
for a in A:
    ans += int(l // a)
    

print(ans % MOD)

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')


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():
    n = II()
    a = LI()
    lcm_ = lcm(a)
    ans = 0
    lcm_ %= mod
    for i in a:
        ans += lcm_ * pow(i, mod-2, mod)
        ans %= mod
    print(ans)
    return



if __name__ == '__main__':
    solve()

Solution (Python):
import fractions
from functools import reduce

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

def lcm_list(l):
    return reduce(lcm, l, 1)


ans = 0

dev = 10 ** 9 + 7

n = int(input())

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

z = lcm_list(a)



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

print(ans%dev)

Solution (Python):
N = int(input())
A = list(map(int,input().split()))
mod = 10**9 + 7
 
from fractions import gcd
 
def lcm(a,b):
    return a//gcd(a,b)*b

AA = 1
for i in range(N):
    AA = lcm(AA,A[i])
AA %= mod

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

Solution (Python):
import sys
input = sys.stdin.readline
LOCAL = len(sys.argv) > 1 and sys.argv[1] == 'LOCAL'


def dprint(*args):
  if LOCAL:
    print(*args)


MOD = 10**9 + 7

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



import math
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)


lcm = lcm_list(a)
dprint(lcm)

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

Solution (Python):
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N,num):
    if N<=0:
        return [[] for _ in range(num)]
    elif num==1:
        return [I() for _ in range(N)]
    else:
        read_all = [tuple(II()) for _ in range(N)]
        return map(list, zip(*read_all))



N = I()
A = III()


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,M=mod):
    if a==0:
        return 0
    x = extgcd(a,M)[0]
    return (M+x%M)%M

inv_list = [mod_inv(a) for a in range(max(A)+1)]

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)

x = lcm_list(A) % mod
y = [x*inv_list[a] for a in A]

ans = 0
for i in range(N):
    ans += y[i]
    ans %= mod

print(ans)

Solution (Python):
from fractions import gcd

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

def lcm(numbers):
    t = 1
    for n in numbers:
        t = lcm_base(t, n)
    return t

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

mod = 10**9+7
ans = 0
t = lcm(A)
t %= mod
for i in range(N):
    ans = (ans + t*pow(A[i],mod-2, mod))%mod

print(ans)

Solution (Python):

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

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



tmp = [0] * (10**6+1)
for i in range(n):
    t = factorization(a[i])
    for j in range(len(t)):
        tmp[t[j][0]] = max(tmp[t[j][0]], t[j][1])



lcm = 1
for i in range(1, 10**6+1):
    x = i 
    y = tmp[i] 
    for j in range(y):
        lcm *= x
        lcm %= mod



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

Solution (Python):
import sys

input = sys.stdin.readline

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


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


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


MOD = 10**9 + 7

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

x = ls[0]
for i in range(1, n):
    x = lcm(x, ls[i])
ds = [x // y for y in ls]
print(sum(ds) % MOD)

Solution (Python):
import fractions
from functools import reduce


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

def MinB_list(numbers):
    return reduce(MinB, numbers, 1)

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

tmp = MinB_list(AList)
result = 0
for i in range(0, N):
    result += tmp // AList[i]
    
print(result % (10 ** 9 + 7))

Solution (Python):
import fractions
def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0

def modinv(a, m):
    g, x, y = xgcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m
def main():
    N = int(input())
    A = list(map(int, input().split()))
    g = A[0]
    l = A[0]
    for i in A[1:]:
        g = fractions.gcd(g, i)
        l = l * i // fractions.gcd(l, i)
    r = 0
    mod = 10 ** 9 + 7
    n = (l // g) % mod
    for i in A:
        r += n * modinv(i//g, mod)
    print(r % mod)
main()

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

Solution (Python):
n = int(input())
a = list(map(int,input().split()))
mod = 10 ** 9 + 7
lcm = a[0]
for i in range(1,n):
  big,sml = lcm,a[i]
  while sml != 0:
    big,sml = sml,big%sml
  lcm *= a[i] // big
ans = 0
def inv(x):
  y = 1
  while x != 1:
    y *= mod // x + 1
    y %= mod
    x -= mod % x
  return y

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

ans *= lcm
ans %= mod
print(ans)

Solution (Python):
import fractions
from functools import reduce
m = 0
sum = 0

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

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)

m = lcm_list(List)

for i in List:
  sum += m // i
print(sum % (10**9 + 7))

Solution (Python):
def gcd(x, y): 

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

n = int(input())
a = list(map(int, input().split(' ')))
nok = a[0]
mod = int(1e9 + 7)
for i in range(1, n):
    nok = nok * a[i] // gcd(nok, a[i])
ans = 0
for i in range(0, n):
    ans += nok // a[i]
print (ans % mod)

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

from fractions import gcd
from functools import reduce

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7





def get_factors(n):
    """
    素因数分解
    :param int n:
    :rtype: list of int
    """
    if n <= 1:
        return []

    ret = []
    while n > 2 and n % 2 == 0:
        ret.append(2)
        n //= 2
    i = 3
    while i <= math.sqrt(n):
        if n % i == 0:
            ret.append(i)
            n //= i
        else:
            i += 2
    ret.append(n)
    return ret


def mod_invs(max, mod):
    """
    逆元 0, 1/1, 1/2, 1/3, ..., 1/max
    :param int max:
    :param int mod:
    """
    invs = [1] * (max + 1)
    invs[0] = 0
    for x in range(2, max + 1):
        invs[x] = (-(mod // x) * invs[mod % x]) % mod
    return invs


N = int(sys.stdin.buffer.readline())
A = list(map(int, sys.stdin.buffer.readline().split()))


max_counts = defaultdict(int)
for a in A:
    counts = Counter(get_factors(a))
    for k, cnt in counts.items():
        max_counts[k] = max(max_counts[k], cnt)

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

invs = mod_invs(max(A), MOD)
ans = 0
for a in A:
    ans += lcm * invs[a]
    ans %= MOD
print(ans)

Solution (Python):

import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
from fractions import gcd
MOD = 10**9 + 7

n = int(input())
a = [int(item) for item in input().split()]


lcm = 1
for item in a:
    lcm = lcm * item // gcd(lcm, item)
lcm %= MOD

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

print(ans)

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

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

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

Solution (Python):
def main():
    from collections import Counter as ct
    n = int(input())
    a = list(map(int, input().split()))
    mod = 10**9+7

    def soinsuu(a):
        yy, j = [], 2
        y = yy.append
        while(a > 1):
            for i in range(j, int(a**0.5)+1):
                if a % i == 0:
                    y(i)
                    a, j = a//i, i
                    break
            else:
                y(a)
                break
        return ct(yy)

    soinsuu_dict = dict()

    for i in a:
        j = soinsuu(i)
        
        for x, y in j.items():
            if x not in soinsuu_dict.keys():
                soinsuu_dict[x] = y
            else:
                soinsuu_dict[x] = max(soinsuu_dict[x], y)
    
    l = 1
    for i, j in soinsuu_dict.items():
        l = l*pow(i, j, mod) % mod
    
    ans = 0
    for i in a:
        ans = (ans+l*pow(i, mod-2, mod)) % mod
    print(ans)


main()

Solution (Python):
from sys import stdin
def gcd(x, y):
	while(y):x, y = y, x % y 
	return x
n = int(stdin.readline())
a = list(map(int,stdin.readline().split()))
lcm = a[0]
for i in range(1,n):lcm = (lcm*a[i])//gcd(lcm,a[i])
b = [lcm // i for i in a]
print(sum(b)%1000000007)

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









def pow(x, y, mod):  
    ans = 1
    while y > 0:
        if y % 2 == 1:
            ans = (ans * x) % mod
        x = (x**2) % mod
        y //= 2
    return ans

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














from fractions import gcd


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


def lcm_list(A):
    ans = A[0] % mod
    for i in range(1, len(A)):
        ans = lcm(ans, A[i]) 
    return ans % mod

lc = lcm_list(A)

ans = 0
for i in range(n):
    ans = (ans + (lc * inv(A[i], mod))% mod) % mod
print(ans%mod)

Solution (Python):
import fractions

n = int(input())
a = list(map(int, input().split()))
tmp = a[0]
ans = 0

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

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

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

Solution (Python):
n = int(input())
a_list = list(map(int, input().split()))
MOD = 1000000007
gid = 1
for i in a_list:
    gid_temp = gid
    i_temp = i
    while i_temp > 0:
        gid_temp, i_temp = i_temp, gid_temp % i_temp
    gid = gid * i // gid_temp

sum = 0
for i in a_list:
    sum += gid // i
print(sum % MOD)

Solution (Python):
import fractions
from functools import reduce

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

def lcm_ls(num):
    return reduce(lcm, num, 1)


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

m = lcm_ls(ls)

ans = 0

for i in range(n):
    ans += m // ls[i]

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

Solution (Python):
from collections import Counter as C
N = 10 ** 6
X = [-1] * (N+1)
L = [[] for _ in range(N+1)]
k = 2
while k <= N:
    X[k] = 1
    L[k].append(k)
    for i in range(k*2, N+1, k):
        X[i] = 0
        L[i].append(k)
    d = 2
    while k**d <= N:
        for i in range(k**d, N+1, k**d):
            L[i].append(k)
        d += 1
    while k <= N and X[k] >= 0:
        k += 1
P = [i for i in range(N+1) if X[i] == 1]
D = {p: 0 for p in P}


P = 10**9+7
N = int(input())
A = [int(a) for a in input().split()]
s = sum([pow(a, P-2, P) for a in A]) % P
for a in A:
    c = C(L[a])
    for f in c:
        D[f] = max(D[f], c[f])

l = 1
for f in D:
    l = l * pow(f, D[f], P) % P

print(s * l % P)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

N = int(readline())
A = np.array(read().split(),np.int64)

MOD = 10 ** 9 + 7

U = 10 ** 6 + 10
is_prime = np.zeros(U, np.bool)
is_prime[2] = 1
is_prime[3::2] = 1
for p in range(3,U,2):
    if p*p > U:
        break
    if is_prime[p]:
        is_prime[p*p::p+p] = 0

M = 10 ** 3
small_primes = np.where(is_prime[:M])[0].tolist()

B = A.copy()
lcm = 1
for p in small_primes:
    e = 0
    while np.any(A % p == 0):
        e += 1
        A[A % p ==0] //= p
    lcm *= p**e
    lcm %= MOD

for x in set(A.tolist()):
    lcm *= x
    lcm %= MOD

answer = sum(pow(x, MOD-2, MOD) for x in B.tolist()) % MOD
answer *= lcm
answer %= MOD
print(answer)

Solution (Python):

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

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

for i in range(N):
    if i == 0:
        LCM = A[0]
    else:
        LCM = lcm(LCM,A[i])

for j in range(N):
    S = S + (LCM // A[j])

S = S % (10**9 + 7)
print(S)

Solution (Python):



def rint():
    return int(input())


def rints():
    return list(map(int, input().split()))


from fractions import gcd
from functools import reduce
m = 10**9 + 7
def inv(a):
    return pow(a, m - 2, m)
def mod_lcm(a, b):
    return a * b // gcd(a, b)
n = rint()
a = rints()
l = reduce(mod_lcm, a) % m
print(sum(l * inv(ai) % m for ai in a) % m)

Solution (Python):
import functools

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

def multiple(a, b):
    return a*b // euclid(a, b)

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

N = int(input())
A = list(map(int, input().split()))
NumLCM = lcm(A)
ans = 0
for i in range(len(A)):
    ans += NumLCM // A[i]

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

Solution (Python):
def Eratosthenes(N): 
    
    N+=1
    is_prime_list = [True]*N


    m = int(N**0.5)+1
    for i in range(3,m,2):
        if is_prime_list[i]:
            is_prime_list[i*i::2*i]=[False]*((N-i*i-1)//(2*i)+1)
    return [2] + [i for i in range(3,N,2) if is_prime_list[i]]





import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
read = sys.stdin.read



MOD = 10**9+7

n = int(input())
a = [int(i) for i in readline().split()]




from fractions import gcd
m = a[0]
for i in a:
    m = m//gcd(m,i)*i

ans = 0
M = m%MOD
for i in a:
    ans += M*pow(i,MOD-2,MOD)%MOD

print(ans%MOD)

Solution (Python):
from fractions import gcd

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

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

Solution (Python):
from fractions import gcd

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

n=int(input())
a=[int(i) for i in input().split()]
l=1
mod=10**9+7
for i in range(n):
    l=lcm(l,a[i])
ans=0

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

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


k = 10 ** 9 + 7
n = int(input())
a = list(map(int, input().split()))
z = lcm(a)
answer = 0
for j in range(n):
    answer += z // a[j]
print(answer % k)

Solution (Python):
import fractions as math
from functools import reduce
def lcm_base(x, y):
    return (x * y) // math.gcd(x, y)
def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)
a = input()
b = list(map(int,input().split()))
c = lcm_list(b)
ans = 0
for d in b:
  ans += c//d
print(ans%1000000007)

Solution (Python):

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


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

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

from functools import reduce
def lcm_multi(num_list):
    return reduce(lcm, num_list, 1)

div_num = 10 ** 9 + 7
lcm_num = lcm_multi(tuple(A_list))
ans = 0
for i in range(N):
    ans += (lcm_num // A_list[i])
print(ans % div_num)

Solution (Python):
def gcd(x,y):
    while y != 0:
        x, y = y, x%y

    return(x)

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

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

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

Solution (Python):
n = int(input())
a = [int(i) for i in input().split()]
p = 10 ** 9 + 7

def pr(x):
    a=[]
    i=2
    while True:
        if x % i == 0:
            j=0
            while x % i == 0:
                x //= i
                j += 1
            a.append((i, j))
        if i * i > x:
            break
        i += 1
    if x != 1:
        a.append((x,1))
    return a
c = {}
for i in a:
    d = pr(i)
    for j in d:
        if j[0] in c:
            c[j[0]] = max(c[j[0]], j[1])
        else:
            c[j[0]] = j[1]

b = 1
for i in c:
    b *= pow(i, c[i], p)
    b %= p
ans = 0
for i in a:
    ans += b * pow(i, p - 2, p)
    ans %= p
print(ans)

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

mod=10**9+7

from collections import Counter

F=Counter()

import math

for x in A:
    L=int(math.sqrt(x))

    FACT=dict()

    for i in range(2,L+2):
        while x%i==0:
            FACT[i]=FACT.get(i,0)+1
            x=x//i

    if x!=1:
        FACT[x]=FACT.get(x,0)+1

    for f in FACT:
        F[f]=max(F[f],FACT[f])



LCM=1
for f in F:
    LCM=LCM*pow(f,F[f],mod)%mod

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

print(ANS)

Solution (Python):
MAX = 10**6+3

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

n = int(input())
a = list(map(int, input().split()))
sieve()
LCM = lcmModuloM(a, n)
ans = 0
for ai in a:
    ans += pow(ai, mod-2, mod)
ans *= LCM
ans %= mod
print(ans)

Solution (Python):
def GCD(a, b):
    return GCD(b, a % b) if b else a
    
def LCM(a, b):
    return a // GCD(a, b) * b

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

al = 1
for i in range(n):
    al = LCM(al, a[i])

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

print(ans%1000000007)

Solution (Python):
def gcd(a: int, b: int) -> int:
    """a, bの最大公約数(greatest common divisor:GCD)を求める
    計算量: O(log(min(a, b)))
    """
    if b == 0:
        return a
    return gcd(b, a%b)


def lcm(a, b):
    """a, bの最小公倍数(least common multiple:LCM)を求める
    計算量: O(log(min(a, b)))"""
    return (a * b) // gcd(a, b)


def multi_gcd(array: list) -> int:
    """arrayのGCDを求める
    計算量: O(Nlog)
    """
    n = len(array)
    ans = array[0]
    for i in range(1, n):
        ans = gcd(ans, array[i])
    return ans


def multi_lcm(array):
    """arrayのLCMを求める"""
    ans = array[0]
    for i in range(1, len(array)):
        ans = (ans * array[i]) // gcd(ans, array[i])
    return ans


n = int(input())
MOD = 10**9 + 7
a = list(map(int, input().split()))
lcm_ = multi_lcm(a)
ans = 0
for i in range(n):
    ans += lcm_ * pow(a[i], MOD - 2, MOD)
print(ans % MOD)

Solution (Python):
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  

n = ni()
a = na()

isp = [True] * 1001
isp[0] = isp[1] = False
for p in range(2, 1001):
    if isp[p]:
        for j in range(p*2, 1001, p):
            isp[j] = False

maxe = [0] * 1000001
for v in a:
    for p in range(2, 1001):
        e = 0
        while v % p == 0:
            v //= p
            e += 1
        maxe[p] = max(maxe[p], e)
    if v > 1:
        maxe[v] = max(maxe[v], 1)

def inv(a, mod):
    b = mod
    p, q = 1, 0
    while b > 0:
        c = a//b
        d = a; a = b; b = d % b
        d = p; p = q; q = d-c*q
    return p+mod if p < 0 else p


ans = 1
mod = 1000000007
for i in range(2, 1000001):
    for j in range(maxe[i]):
        ans = ans * i % mod

xx = 0
for v in a:
    xx += inv(v, mod)

print(ans*xx%mod)

Solution (Python):
def PrimeFact(N):
    PF = dict()
    M = N
    k = 2
    while (k*k<=N):
        od = 0
        if M % k == 0:
            while (True):
                if M % k == 0:
                    od += 1
                    M = M // k
                else:
                    break
            PF[k]=od
        else:
            k += 1
        if M == 1:
            break
    if M>1:
        PF[M]=1
    return PF

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



mod=10**9+7
def inv(x):
    return pow(x,mod-2,mod)
D=dict()
for i in range(N):
    T=PrimeFact(A[i])
    for p in T:
        if not(p in D):
            D[p]=0
        D[p]=max(D[p],T[p])
ans=1
for p in D:
    ans=ans*pow(p,D[p],mod)
    ans%=mod
tmp=0
for i in range(N):
    tmp+=inv(A[i])
    tmp%=mod
ans=ans*tmp
ans%=mod
print(ans)

Solution (Python):
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())


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

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


N = inp()
aa = inpl()
tmp = 1

for a in aa:
    tmp = lcm(a,tmp)

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

print(ans)

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

n=int((input()))
a=input().split()
t=1
for x in a:
    t=(t*int(x))//(gcdlol(t,int(x)))
ans=0
for x in a:
    ans+=(t//int(x))
print(ans%1000000007)

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
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)]

sys.setrecursionlimit(1000000)
mod = 1000000007

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

    n = I()
    a = LI()
    g = a[0]
    l = a[0]
    for i in a[1:]:
        g = gcd(l,i)
        l = l*i//g
    ans = 0
    for i in a:
        ans += pow(i,mod-2,mod)
        ans %= mod
    print(ans*l%mod)
    return


if __name__ == "__main__":
    solve()

Solution (Python):
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)
l=a[0]
for i in range(1,n):
  l=lcm(l,a[i])
ans=0
l%=mod
for i in range(n):
  ans+=l*pow(a[i],mod-2,mod)
  ans%=mod
print(ans)

Solution (Python):
N = int(input())
A = list(map(int,input().split()))
mod = 10**9+7
def power(a,b):
    if b == 0:
        return 1
    if b % 2 == 0:
        d = power(a,b//2)
        return d*d%mod
    elif b % 2 == 1:
        return a*power(a,b-1)%mod
import fractions
l = A[0]
g = A[0]
for i in range(1,N):
    x = A[i]
    g = fractions.gcd(l,x)
    l = l*x//g
l = l % mod
ans = 0
for i in range(N):
    ans += l*power(A[i],mod-2) % mod
ans = ans%mod
print(ans)

Solution (Python):
def gcd(n,m):
  if n>m:
    return gcd(m,n);
  if n==0:
    return m;
  return gcd(m-n*(m//n),n)

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