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



Sample input:
3
2 3 4


Sample output:
13

Submission status: Runtime Error

Solution code:
def lcm(p,q):
	p, q = abs(p), abs(q)
	m = p * q
	if not m: return 0
	while True:
		p %= q
		if not p: return m // q
		q %= p
		if not q: return m // p

def find_loop():
    N = int(input())
    nums = [int(x) for x in input().split(" ")]
    current_lcm = nums[0]
    for i in range(1, N):
        current_lcm = lcm(current_lcm, nums[i])
    ret = 0
    for i in range(N):
        ret = (ret+int(current_lcm/nums[i])) % 1000000007
    print(ret)

find_loop()

Submission status: Runtime Error

Solution code:
def gcd(m, n):
    return m if n == 0 else gcd(n, m%n)

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

def find_loop():
    N = int(input())
    nums = [int(x) for x in input().split(" ")]
    current_lcm = nums[0]
    for i in range(1, N):
        current_lcm = lcm(current_lcm, nums[i])
    ret = 0
    for i in range(N):
        ret = (ret+int(current_lcm/nums[i])) % 1000000007
    print(ret)

find_loop()

Submission status: Runtime Error

Solution code:
def gcd(m, n):
    return m if n == 0 else gcd(n, m%n)

def lcm(m, n):
    g = gcd(m, n)
    return m*n if g == 0 else m*n/g

def find_loop():
    N = int(input())
    nums = [int(x) for x in input().split(" ")]
    current_lcm = nums[0]
    for i in range(1, N):
        current_lcm = lcm(current_lcm, nums[i])
    ret = 0
    for i in range(N):
        ret = (ret+current_lcm/nums[i]) % 1000000007
    print(int(ret))


find_loop()

Submission status: Runtime Error

Solution code:
import sys
from fractions import gcd
input = sys.stdin.readline
def lcm(a, b):
    return a*b//gcd(a, b)

n = input()
arr = list(map(int, input().split()))
tmp = arr[0]
for i in range(len(arr)-1):
    tmp = lcm(tmp,arr[i+1])
ans = sum(tmp/a for a in arr)
ans = ans % (1e+9+7)
print(int(ans))

Submission status: Runtime Error

Solution code:
import sys
from fractions import gcd
input = sys.stdin.readline
def lcm(a, b):
    return a*b//gcd(a, b)

n = input()
arr = map(int, input().split())
tmp = arr[0]
for i in range(len(arr)-1):
    tmp = lcm(tmp,arr[i+1])
ans = sum(tmp/a for a in arr)
ans = ans % (1e+9+7)
print(int(ans))

Submission status: Runtime Error

Solution code:
import java.io.*;
import java.util.*;
import java.math.BigInteger;

public class Main {
    static int N = (int)1e9 + 7;
    public static void main(String[] args){
        MyReader mr = new MyReader();
        PrintWriter pr = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));

        int n = mr.nextInt();
        int[] arr = mr.nextIntArray(n);

        BigInteger l = BigInteger.valueOf(arr[0]);

        for(int i = 1;i<n;i++){
            l = lcm(l,BigInteger.valueOf(arr[i]));
        }

        BigInteger sum = BigInteger.valueOf(0);
        for(int num : arr){
            BigInteger tmp = l.divide(BigInteger.valueOf(num));
            sum = sum.add(tmp);

        }



        System.out.println(sum.mod(BigInteger.valueOf(N)).toString());







    }

    static BigInteger lcm(BigInteger a, BigInteger b){
        BigInteger gcd = a.gcd(b);
        BigInteger mul = a.multiply(b);
        BigInteger res = mul.divide(gcd);
        return res;
    }



    static class MyReader {
        BufferedReader br;
        StringTokenizer st;

        MyReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (Exception e) {
                    e.printStackTrace();
                }
            }

            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String res = "";
            try {
                res = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }

            return res;
        }

        int[] nextIntArray(int n){
            try{
                st = new StringTokenizer(br.readLine());
            }
            catch (Exception e){
                e.printStackTrace();
            }
            int[] arr = new int[n];
            for(int i=0;i<n;i++){
                arr[i] = Integer.parseInt(st.nextToken());
            }

            return arr;
        }

        long[] nextLongArray(int n){
            try{
                st = new StringTokenizer(br.readLine());
            }
            catch (Exception e){
                e.printStackTrace();
            }
            long[] arr = new long[n];
            for(int i=0;i<n;i++){
                arr[i] = Integer.parseInt(st.nextToken());
            }

            return arr;
        }

        String[] nextStringArray(int n){
            String res = "";
            try{
                res = br.readLine();
            }
            catch (Exception e){
                e.printStackTrace();
            }

            String[] arr = res.split(" ");
            return arr;
        }
    }

    static class Pair {
        int x, y;

        public Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

}

Submission status: Runtime Error

Solution code:
from math import *
n,*a=map(int,open(0).read().split())
b=1
for i in a:b*=i//gcd(b,i)
print(sum(b//i for i in a)%(10**9+7))

Submission status: Runtime Error

Solution code:
import math as m
n=int(input())
a=input().split()
b=1
for i in a:
    i=int(i)
    b*=i//m.gcd(b,i)
    
print(sum(b//int(i) for i in a)%(10**9+7))

Submission status: Runtime Error

Solution code:
import math as m
n=int(input())
a=input().split()
b=1
for i in a:
    i=int(i)
    b*=i//m.gcd(b,i)
    
print(sum(b//int(i) for i in a)%(10**9+7))

Submission status: Runtime Error

Solution code:
from fractions import gcd

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

def lcm(x, y):
    return (x * y) // gcd(x, y)
l = a[0]
for i in range(n):
    if i == 0:
        continue
    l = lcm(l, a[i])
sum = 0
for i in range(n):
    sum += l / a[i]
    sum %= 1000000007
print(sum)

Submission status: Runtime Error

Solution code:
from fractions import gcd
def lcm(a, b):
    return a*b//gcd(a, b)
n = input()
arr = input().split(' ')
arr = [int(a) for a in arr]
tmp = arr[0]
for i in range(len(arr)-1):
    tmp = lcm(tmp,arr[i+1])
ans = sum([tmp/a for a in arr])
ans = int(ans % (1e+9+7))
print(ans)

Submission status: Runtime Error

Solution code:
from math import gcd
def lcm(a, b):
    return a*b//gcd(a, b)
n = input()
arr = input().split(' ')
arr = [int(a) for a in arr]
tmp = arr[0]
for i in range(len(arr)-1):
    tmp = lcm(tmp,arr[i+1])
ans = sum([tmp/a for a in arr])
ans = int(ans % (1e+9+7))
print(ans)

Submission status: Runtime Error

Solution code:
import math

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

def lcm(x, y):
    return (x * y) // math.gcd(x, y)
l = a[0]
for i in range(n):
    if i == 0:
        continue
    l = lcm(l, a[i])
sum = 0
for i in range(n):
    sum += l / a[i]
    sum %= 1000000007
print(sum)

Submission status: Runtime Error

Solution code:
from functools import reduce

def gcd(x, y):
    y, x = sorted([x, y])
    while True:
        r = x % y
        if r == 0:
            print(x, y, r)
            return r
        else:
            print(x, y, r)
            x, y = y, r

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

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

N = int(input())
l = list(map(int, input().split(" ")))

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

Submission status: Runtime Error

Solution code:
n = input()
arr = input().split(' ')
arr = [int(a) for a in arr]
# arr = [12, 1, 12, 12, 12]
def gcd(a, b):
    while b is not 0:
        a, b = b, a % b
    return a
def lcm(a, b):
    return a *b//gcd(a, b)
tmp = arr[0]
for i in range(len(arr)-1):
    tmp = lcm(tmp,arr[i+1])
ans = sum([tmp/a for a in arr])
ans = int(ans % (1e+9+7))
print(ans)

Submission status: Runtime Error

Solution code:
n = input()
arr = input().split(' ')
arr = [int(a) for a in arr]
arr = [a for a in arr if a!=0]
def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a
def lcm(a, b):
    return a *b//gcd(a, b)
tmp = arr[0]
for i in range(len(arr)-1):
    tmp = lcm(tmp,arr[i+1])
ans = sum([int(tmp/a) for a in arr])
ans = int(ans % (1e+9+7))
print(ans)

Submission status: Runtime Error

Solution code:
n = input()
arr = input().split(' ')
arr = [int(a) for a in arr]
def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a
def lcm(a, b):
    return a *b//gcd(a, b)
tmp = arr[0]
for i in range(len(arr)-1):
    tmp = lcm(tmp,arr[i+1])
ans = sum([int(tmp/a) for a in arr])
ans = int(ans % (1e+9+7))
print(ans)

Submission status: Runtime Error

Solution code:
def gcd(x, y):
    while y > 0:
        tmp = x % y
        x = y
        y = tmp
    return x

def lcm(x, y):
    if x == 0 or y == 0:
        return 0
    else:
        return x / gcd(x, y) * y

def main():
    mod = int(1e9 + 7)
    n = int(input())
    a = list(map(int, input().split()))
    l = 1
    for i in range(n):
        l = lcm(l, a[i])

    ans = 0

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

    ans %= mod

    print(int(ans))

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import fractions

#互いに素なa,bについて、a*x+b*y=1の一つの解
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
    #[x,y]
    return [w[0],w[1]]

# aの逆元(mod m)を求める。(aとmは互いに素であることが前提)
def mod_inv(a,m):
    x = extgcd(a,m)[0]
    return (m+x%m)%m

n = int(input())
a = list(map(int, input().split()))
ans = a[0]
for i in range(1, n):
    ans = int(ans * a[i] % md*mod_inv(fractions.gcd(ans, a[i]),md)%md)
b= 0
md = 10**9+7
for i in range(n):
    b = int(b + ans/a[i]) % md
print(b)

Submission status: Runtime Error

Solution code:
import time, math

def f(a):
    M=10**9+7
    ans, z = 0, 1
    for x in a:
        z = (z * x) // math.gcd(z, x)
    #print(z)
    z %= M
    for x in a:
        ans += z * pow(x, M-2, M)
        ans %= M
    return ans

n = input()
a = list(map(int, input().split()))
#a = []
#for i in range(1000):
#    a.append(1000000-i)
print(f(a))

Submission status: Runtime Error

Solution code:
from fractions import gcd

d = int(input())
nums = list(map(int, input().split(' ')))

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

if d == 1:
  print(1)
else:
  lcm_num = nums[0]
  for i in range(len(nums)-1):
    lcm_num = lcm_base(lcm_num, nums[i+1])

  min_nums = []
  for n in nums:
    min_nums.append(int(lcm_num / n))
  ans = sum(min_nums)
  print(ans % (10**9 + 7))

Submission status: Runtime Error

Solution code:
from fractions import gcd

d = int(input())
nums = list(map(int, input().split(' ')))

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

if d == 1:
  print(1)
else:
  lcm_num = nums[0]
  for i in range(len(nums)-1):
    lcm_num = lcm_base(lcm_num, nums[i+1])

min_nums = []
for n in nums:
  min_nums.append(int(lcm_num / n))
ans = sum(min_nums)
print(ans % (10**9 + 7))

Submission status: Runtime Error

Solution code:
import fractions
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])
b= 0
md = 10**9+7
for i in range(n):
    b = int(b + ans/a[i]) % md
print(b)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
class sieve:
  def __init__(self, n):
    self.n = n
    self.sv = [1] * (n + 1)
    self.sv[0] = 0
    self.sv[1] = 0
    for i in range(2, n + 1):
      if self.sv[i]:
        for j in range(i * 2, n + 1, i):
          self.sv[j] = 0
  def isprime(self, x):
    if x > self.n:
      return False
    return self.sv[x] == 1
  def factorize(self, x):
    res = []
    for i in range(2, self.n + 1):
      if self.sv[i]:
        while x % i == 0:
          x //= i
          res.append(i)
    if x != 1:
      res.append(x)
    return res
  def modgcd(self, a, mod):
    res = [float("inf")] * (self.n + 1)
    vis = set()
    f = self.factorize(a[0])
    for j in f:
      res[j] = f.count(j)
      vis.add(j)
    for i in range(1, len(a)):
      f = self.factorize(a[i])
      for j in vis:
        res[j] = min(f.count(j), res[j])
        vis.add(j)
    rres = 1
    for i in range(self.n + 1):
      if res[i] != float("inf"):
        rres *= pow(i, res[i], mod)
        rres %= mod
    return rres
  def modlcm(self, a, mod):
    res = [0] * (self.n + 1)
    for i in range(len(a)):
      f = self.factorize(a[i])
      for j in f:
        res[j] = max(f.count(j), res[j])
    rres = 1
    for i in range(self.n + 1):
      if res[i] != 0:
        rres *= pow(i, res[i], mod)
        rres %= mod
    return rres
sv = sieve(10 ** 3)
lcm = sv.modlcm(a, 10 ** 9 + 7)
res = 0
for x in a:
  res += lcm * pow(x, 10 ** 9 + 5, 10 ** 9 + 7)
  res %= 10 ** 9 + 7
print(res)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
from collections import Counter
import numpy as np
sys.setrecursionlimit(10**8)
MOD = 1000000007  # type: int


def eratosthenes_sieve(n):
    table = [0] * (n + 1)
    prime_list = []

    for i in range(2, n + 1):
        if table[i] == 0:
            prime_list.append(i)
            for j in range(i + i, n + 1, i):
                table[j] = 1

    return prime_list


def solve(N: int, A: "List[int]"):

    primes = eratosthenes_sieve(10**3)

    def factorial(n):
        # 試し割りによる素因数分解
        prime_count = Counter()
        for i in primes:
            while n % i == 0:
                n /= i
                prime_count[i] += 1
        if n > 1:
            prime_count[int(n)] += 1
        return prime_count

    C = [factorial(a) for a in A]

    K = Counter()
    for c in C:
        for k in c:
            K[k] = max(K[k], c[k])
    # print(K)

    B = [0]*N
    for i in range(N):
        b = Counter()
        for k in K:
            b[k] = K[k] - C[i][k]
        a = 1
        for k in b:
            if b[k] != 0:
                a *= k**b[k]
                a %= MOD
        B[i] = a
    # print(B)
    print(sum(B) % MOD)

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(100000000)
import math

M = 10**9 + 7
n = int(input())
a = list(map(int, input().split()))
p = a[0]
ans = 0
for i in range(1, n):
    p = p * a[i] // math.gcd(p, a[i])

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

Submission status: Runtime Error

Solution code:
import sys
n = int(input())
a = list(map(int,sys.stdin.read().strip().split()))

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

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

L = 1
for _a in a:
    L = lcm(L , _a)

answer = 0;
for _a in a:
    answer += L / _a

mod = int(1e9 + 7)
answer %= mod

print(int(answer))

Submission status: Runtime Error

Solution code:
import sys
n = int(input())
a = list(map(int,sys.stdin.read().strip().split()))

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

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

L = 1
for _a in a:
    L = lcm(L , _a)

answer = 0;
for _a in a:
    answer += L / _a

mod = int(1e9 + 7)
answer %= mod

print(answer)

Submission status: Runtime Error

Solution code:
import sys
n = int(input())
a = list(map(int,sys.stdin.read().strip().split()))

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

L = 1
for _a in a:
    L = lcm(L , _a)
    
answer = 0;
for _a in a:
    answer += L / _a
    
mod = int(1e9 + 7)
answer %= mod

print(answer)

Submission status: Runtime Error

Solution code:
import sys
 
def compute_gcd(x, y):
   while(y):
       x, y = y, x % y
   return x
 
def compute_lcm(x, y):
   lcm = (x*y)//compute_gcd(x,y)
   return lcm
   
n = int(input())

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

MOD = 10 ** 9 + 7

ans = 1
d = 1
cur = 0

for i in a:
	ans = compute_lcm(ans, i)

for i in a:
	cur += ans / i

print(cur % MOD)

Submission status: Runtime Error

Solution code:
#!/usr/bin/python3
# -*- coding:utf-8 -*-

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

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

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


if __name__=='__main__':
  main()

Submission status: Runtime Error

Solution code:
from fractions import gcd

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

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

for i in a:
    ans+=A/i

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

Submission status: Runtime Error

Solution code:
from fractions import gcd

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

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

for i in a:
    ans+=l/i

print(int(ans%mod))

Submission status: Runtime Error

Solution code:
#!/usr/bin/python3
# -*- coding:utf-8 -*-

def calc_gcd(a, b):
  if a > b:
    a, b = b, a
  a, b = b%a, a
  if a != 0:
    return calc_gcd(a, b)
  else:
    return b

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

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


if __name__=='__main__':
  main()

Submission status: Runtime Error

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

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

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

def PrimeNumSet(N):  # return the list of prime numbers in [2,N], using eratosthenes sieve
    Max = int(N**0.5)
    seachList = [i for i in range(2,N+1)]
    primeNum = []
    while seachList[0] <= Max:
        primeNum.append(seachList[0])
        tmp = seachList[0]
        seachList = [i for i in seachList if i % tmp != 0]
    primeNum.extend(seachList)
    return primeNum

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

show_flg=False
show_flg=True


ans=0

n=I()
a=LI()

m=LCM(a)

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

print(x)

Submission status: Runtime Error

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

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

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

def PrimeNumSet(N):  # return the list of prime numbers in [2,N], using eratosthenes sieve
    max = int(N**0.5+1)
    seachList = [i for i in range(2,N+1)]
    primeNum = []
    while seachList[0] <= max:
        primeNum.append(seachList[0])
        tmp = seachList[0]
        seachList = [i for i in seachList if i % tmp != 0]
    primeNum.extend(seachList)
    return primeNum

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

show_flg=False
show_flg=True


ans=0

n=I()
a=LI()

m=LCM(a)

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

print(x)

Submission status: Runtime Error

Solution code:
import math
import collections


def modinv(n, p):
    """
    逆元のmod pを求める
    """
    if n >= p:
        raise ValueError('p must be larger than n')
    return pow(n, p-2, p)


def prime_sieve(n):
    """
    n以下の素数を昇順に列挙する
    エラトステネスの篩 計算量O(Nlog(log(N)))
    """
    is_prime = [True for i in range(n+1)]
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, n+1):
        if is_prime[i]:
            for j in range(i+i, n+1, i):
                is_prime[j] = False
    return [i for i in range(2, n+1) if is_prime[i]]


def prime_factorization(it):
    """
    数値の素因数分解をリストで返すイテレータ
    エラトステネスの篩を応用する 計算量O(A+Nlog(log(N)))
    """
    n = max(it)
    factor = [1 for i in range(n+1)]
    factor[0] = 0
    factor[1] = 1
    for i in range(2, n+1):
        if factor[i] == 1:
            for j in range(i, n+1, i):
                factor[j] = i
    for a in it:
        prime_factors = list()
        while a != factor[a]:
            prime_factors.append(factor[a])
            a //= factor[a]
        prime_factors.append(factor[a])
        yield list(sorted(prime_factors))


def lcm(x, p=-1):
    """
    配列xに対する最小公倍数 LCM(x_1, x_2, ..., x_n) を求める
    p > 0のときはLCM mod pを返す
    """
    max_prime_counts = dict()
    for prime in prime_sieve(max(x)):
        max_prime_counts[prime] = 0
    pfs = prime_factorization(x)
    for pf in pfs:
        prime_count = collections.Counter(pf)
        for prime in prime_count.keys():
            max_prime_counts[prime] = max(max_prime_counts[prime], prime_count[prime])
    lcm_value = 1
    for prime, factor in max_prime_counts.items():
        if p > 0:
            lcm_value *= pow(prime, factor, p)
            lcm_value %= p
        else:
            lcm_value *= pow(prime, factor)
    return lcm_value


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


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


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

Submission status: Runtime Error

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

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

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

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

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

show_flg=False
show_flg=True
import fractions
ans=0

n=I()
a=LI()

m=LCM(a)

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

print(x)