Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

import sys
from collections import deque

n,m = map(int, input().split())
adj_list = [[] for i in range(n)]
for i in range(m):
    l, r, d = map(int, input().split())
    adj_list[l-1].append((r-1, d))
    adj_list[r-1].append((l-1, -d))
def search(start):
    q = deque([[start]])
    q_d = deque([0])
    dist_all = [None for i in range(n)]
    while(len(q) > 0):
        path = q.popleft()
        dist = q_d.popleft()
        w = path[len(path) - 1]
        for x in adj_list[w]:
            if x[0] not in path:
                new_path = path[:]
                new_path.append(x[0])
                if dist_all[x[0]] is None:
                    dist_all[x[0]] = dist + x[1]
                elif dist_all[x[0]] != dist + x[1]:
                    return False
                q.append(new_path)
                q_d.append(dist + x[1])
    return True
for i in range(n):
    if not search(i):
        print('No')
        exit(0)
print('Yes')


### FIXED CODE ###

import sys
from collections import deque

n,m = map(int, input().split())
adj_list = [[] for i in range(n)]
for i in range(m):
    l, r, d = map(int, input().split())
    adj_list[l-1].append((r-1, d))
    adj_list[r-1].append((l-1, -d))
def search(start, dist_all):
    q = deque([start])
    dist_all[i] = 0
    while(len(q) > 0):
        w = q.popleft()
        for x in adj_list[w]:
            if dist_all[x[0]] is None:
                dist_all[x[0]] = dist_all[w] + x[1]
                q.append(x[0])
            elif dist_all[x[0]] != dist_all[w] + x[1]:
                return False
    return True
dist_all = [None for i in range(n)]
for i in range(n):
    if dist_all[i] is None:
        if not search(i, dist_all):
            print('No')
            exit(0)
print('Yes')
### BUGGY CODE ###

n = int(input())
x = []
y = []
s = []
for i in range(n):
    X, Y = map(int, input().split())
    x.append(X)
    y.append(Y)
    s.append(abs(X)+abs(Y))

num = (x[0] + y[0]) % 2
flag = 0

for i in range(1, n):
    if (x[i] + y[i]) % 2 != num:
        flag = 1


if flag:
    print(-1)
else:
    m = max(s)
    print(m)

    d = [1 for i in range(m)]
    print(*d)

    for i in range(n):
        dist = m - s[i]
        ans = ""
        while dist > 0:
            ans += "LR"
            dist -= 2
        if x[i] > 0:
            for j in range(x[i]):
                ans += "R"
        if x[i] < 0:
            for j in range(abs(x[i])):
                ans += "L"
        if y[i] > 0:
            for j in range(y[i]):
                ans += "U"
        if y[i] < 0:
            for j in range(abs(y[i])):
                ans += "D"
        print(ans)

### FIXED CODE ###

n = int(input())
ps = [list(map(int, input().split())) for i in range(n)]

prev = None
for x, y in ps:
    mandist = abs(x) + abs(y)
    if prev is not None and mandist % 2 != prev:
        print(-1)
        exit()
    prev = mandist % 2

isodd = mandist % 2
ds = [2 ** i for i in range(31)]
ds = ds[::-1]
if isodd:
    m = 31
else:
    m = 32
    ds += [1]

print(m)
print(*ds)
for x, y in ps:
    px = py = 0
    ans = ""
    for d in ds:
        dx = x - px
        dy = y - py
        if abs(dx) >= abs(dy):
            if dx >= 0:
                ans += "R"
                px += d
            else:
                ans += "L"
                px -= d
        else:
            if dy >= 0:
                ans += "U"
                py += d
            else:
                ans += "D"
                py -= d
    print(ans)
### BUGGY CODE ###

# encoding: "utf-8"

from collections import defaultdict

# class Stdin:
#     @staticmethod
#     def read_line(converter=str):
#         return [converter(x) for x in input().split()]
    
#     @staticmethod
#     def read_lines(n, converter=str):
#         result = list()
#         for _ in range(n):
#             result.append(Stdin.read_line(converter))
#         return result
    
#     @staticmethod
#     def convert(data, converter):
#         assert(len(data) == len(converter))
#         return tuple(map(lambda x, f: f(x), data, converter))

#     @staticmethod
#     def convert_lines(datas, n, converter):
#         return [converter(data, n, converter) for data in datas]


def first_count_and_pop(xs):
    cnt = 0
    fst = xs[0]
    # cnt = xs.count(fst)
    for x in xs:
        if x != fst:
            break
        cnt += 1
    return (cnt, xs[cnt:])    
    

def main():
    _ = input()
    # xs = Stdin.read_line(converter=int)
    xs = [int(x) for x in input().split()]
    xs.sort()
    ys = defaultdict(int)
    # for key in xs:
    #     ys[key] += 1
    #     ys[key-1] += 1
    #     ys[key+1] += 1
    while xs:
        key = xs[0]
        cnt = 0
        for x in xs:
            if x != key:
                break
            cnt += 1
        cnt, xs = cnt, xs[cnt:]
        ys[key] += cnt
        ys[key-1] += cnt
        ys[key+1] += cnt

    print(max(ys.values()))

# def main_():
#     input()
#     xs = Stdin.read_line(converter=int)
#     xs.sort()
#     counts = list()
#     for i in range(100000):
#         if not xs:
#             counts.extend([0] * (100000 - len(counts)))
#             break     
#         elif i == xs[0]:
#             cnt, xs = first_count_and_pop(xs)
#             counts.append(cnt)
#         else:
#             counts.append(0)
#     m = 0
#     for i in range(0, 100000):
#         if i == 0:
#             temp = counts[i] + counts[i+1]
#         elif i == 100000 - 1:
#             temp = counts[i-1] + counts[i]
#         else:
#             temp = counts[i-1] + counts[i] + counts[i+1]
#         if m < temp:
#             m = temp
#     print(m)

if __name__ == "__main__":
    main()

### FIXED CODE ###

input()
a_list = [int(s) for s in input().split()]

count = [0]*100002

for a in a_list:
    count[a] += 1
    count[a+1] += 1
    count[a+2] += 1
    
print(max(count))
### BUGGY CODE ###

import itertools
import math
import fractions
import functools
import copy
from collections import deque
from functools import reduce
from decimal import Decimal


def main():
    n = int(input())
    a = list(map(int, input().split()))
    q = int(input())
    bc = []
    for _ in range(q):
        bc.append(list(map(int, input().split())))

    for element in bc:
        for i in range(len(a)):
            if a[i] == element[0]:
                a[i] = element[1]
        print(sum(a))


if __name__ == '__main__':
    main()


### FIXED CODE ###

import itertools
import math
import fractions
import functools
import copy
from collections import deque
from functools import reduce
from decimal import Decimal


def main():
    n = int(input())
    a = list(map(int, input().split()))
    q = int(input())
    bc = []
    for _ in range(q):
        bc.append(list(map(int, input().split())))

    a_i = [0]*(10**5 + 10)
    for num in a:
        a_i[num] += 1

    amount = 0
    for i, num in enumerate(a_i):
        amount += num * i

    for element in bc:
        amount = amount - a_i[element[0]] * \
            element[0] + a_i[element[0]] * element[1]
        a_i[element[1]] += a_i[element[0]]
        a_i[element[0]] = 0

        print(amount)


if __name__ == '__main__':
    main()
### BUGGY CODE ###

n = int(input())
A = [int(i) for i in input().split()]
# S = [sum(A[:i]) for i in range(n+1)]
S = [0]*(n+1)
for i in range(n):
    S[i+1] = S[i] + A[i]
out = 0
for i in set(S):
    num = S.count(i)
    out += num*(num-1)//2
print(out)

### FIXED CODE ###

from collections import Counter
n = int(input())
A = [int(i) for i in input().split()]
S = [0]*(n+1)
for i in range(n):
    S[i+1] = S[i] + A[i]
def hello(data):
    dt = Counter()
    for i in data:
        dt[str(i)] += 1
    return dt
num = hello(S)
out = [i*(i-1)//2 for i in num.values() if i>1]
print(sum(out))
### BUGGY CODE ###

n = int(input())
s = list(map(int,input().split()))
ans = 0
mod = int(1e9+7)
def gcd(a,b):
  while b != 0:
    a, b = b, a % b
  return a
# 最小公倍数
def lcm(a,b):
    return (a*b) // gcd(a,b)

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


### FIXED CODE ###

n = int(input())
s = list(map(int,input().split()))
ans = 0
mod = int(1e9+7)
def gcd(a,b):
  while b != 0:
    a, b = b, a % b
  return a
def lcm(a,b):
    return a // gcd(a,b) * b

g = 1
for i in range(n):
    g = lcm(g, s[i])
for i in range(n):
    ans += g // s[i]
print(ans%mod)
### BUGGY CODE ###



n,k = map(int,input().split())
a=[0 for i in range(n)]
for i in range(n):
    a[i] = int(input())
rank=[0 for i in range(n)]

rank[0]=1
for i in range(1,n):
    ap = a[i]
    r=0
    for j in range(i):
        if abs(a[j]-ap)<=k:
            r=max(r,rank[j])
    rank[i]=r+1
print(max(rank))

### FIXED CODE ###



n,k = map(int,input().split())
a=[0 for i in range(n)]
for i in range(n):
    a[i] = int(input())
rank=[[] for i in range(n)]

ans = 1
for i in range(n):
    for r in range(ans,-1,-1):
        frag = 0
        for j in rank[r]:
            if abs(j-a[i])<=k:
                rank[r+1].append(a[i])
                ans = max(ans,r+2)
                frag =1
                break
        rank[0].append(a[i])
        if frag ==1:
            break


print(ans-1)
### BUGGY CODE ###

n = int(input())
s = input()
q = int(input())
ks = list(map(int, input().split()))

a = []
for k in ks:
    t = 0
    for i in range(n):
        if s[i] == 'C':
            p = s[max(0, i - k + 1):i]
            d = p.count('D')
            m = p.count('M')
            for j in range(len(p)):
                if p[j] == 'M': m -= 1
                if p[j] == 'D': t += m
    a.append(t)

print(*a, sep='\n')

### FIXED CODE ###

def solve():
    n = int(input())
    s = input()
    q = int(input())
    ks = list(map(int, input().split()))

    for k in ks:
        ans = 0
        cnt = 0
        d = 0
        m = 0
        for i in range(n):
            if s[i] == 'D':
                d += 1
            elif s[i] == 'M':
                m += 1
                cnt += d
            elif s[i] == 'C':
                ans += cnt

            if i >= k - 1:
                if s[i - k + 1] == 'D':
                    cnt -= m
                    d -= 1
                elif s[i - k + 1] == 'M':
                    m -= 1

        print(ans)


if __name__ == '__main__':
    solve()
### BUGGY CODE ###

import sys

s = sys.stdin.readline().strip()
t = sys.stdin.readline().strip()

s_len = len(s)
t_len = len(t)
dp = [['' for x in range(t_len)] for y in range(s_len)]

for i in range(t_len):
    if s[0] == t[i]:
        dp[0][i] = s[0]
    else:
        dp[0][i] = dp[0][i-1] if i != 0 else ''


for i in range(s_len):
    if s[i] == t[0]:
        dp[i][0] = t[0]
    else:
        dp[i][0] = dp[i-1][0] if i != 0 else ''

for i in range(1, s_len):
    for j in range(1, t_len):
        if t[j] == s[i]:
            dp[i][j] = dp[i-1][j-1] + t[j]
        else:
            dp[i][j] = dp[i-1][j] if len(dp[i-1][j]) > len(dp[i][j-1]) else dp[i][j-1]

print(dp[s_len-1][t_len-1])


### FIXED CODE ###

import sys

s = sys.stdin.readline().strip()
t = sys.stdin.readline().strip()

s_len = len(s)
t_len = len(t)
dp = [[0 for x in range(t_len + 1)] for y in range(s_len + 1)]


for i in range(1, s_len+1):
    for j in range(1, t_len+1):
        if t[j-1] == s[i-1]:
            dp[i][j] = dp[i-1][j-1] + 1
        else:
            dp[i][j] = max(dp[i-1][j], dp[i][j-1])

ans = ''
i = s_len
j = t_len

while i > 0 and j > 0:
    if dp[i][j] == dp[i - 1][j]:
        i -= 1
    elif dp[i][j] == dp[i][j - 1]:
        j -= 1
    else:
        ans += s[i - 1]
        i -= 1
        j -= 1

print(ans[::-1])
### BUGGY CODE ###

x = int(input())

def gen_divisor(x):
    for i in range(1, x + 1):
        if x % i == 0:
            yield i

def gen_candidates(limit, divisor):
    for a in range(limit):
        yield (a, a - divisor)


for divisor in gen_divisor(x):
    for a, b in gen_candidates(x + 1, divisor):
        if a**5 - b**5 == x:
            print(a, b)
            break
    else:
        continue
    break


### FIXED CODE ###

X = int(input())

for a in range(-119,119):
    for b in range(-119,119):
        if a**5 - b**5 == X:
            print(a,b)
            break
    else:
        continue
    break
### BUGGY CODE ###

from statistics import mean
import math

N = int(input())
A = list(map(int, input().split()))
A = [A[idx]-(idx+1) for idx in range(N)]

b = round(mean(A))

ans1 = 0
ans2 = 0
for i in range(N):
    ans1 += abs(math.floor(mean(A))-A[i])
    ans2 += abs(math.ceil(mean(A)) - A[i])
    
print(min(ans1,ans2))

### FIXED CODE ###

from statistics import median
import math

N = int(input())
A = list(map(int, input().split()))
A = [A[idx]-(idx+1) for idx in range(N)]

ans1 = 0
ans2 = 0
median_A = median(A)
median_floor_A = math.floor(median_A)
median_ceil_A = math.ceil(median(A))

for i in range(N):
    ans1 += abs(median_floor_A - A[i])
    ans2 += abs(median_ceil_A - A[i])
    
print(min(ans1,ans2))
### BUGGY CODE ###

def cmb(n, r):
  if n - r < r: r = n - r
  if r == 0: return 1
  if r == 1: return n

  numerator = [n - r + k + 1 for k in range(r)]
  denominator = [k + 1 for k in range(r)]

  for p in range(2,r+1):
    pivot = denominator[p - 1]
    if pivot > 1:
      offset = (n - r) % p
      for k in range(p-1,r,p):
        numerator[k - offset] /= pivot
        denominator[k] /= pivot

  result = 1
  for k in range(r):
    if numerator[k] > 1:
      result *= int(numerator[k])

  return result

N=int(input())
A=list(map(int, input().split()))
R=[0]*(N+1)
for i in range(N):
  R[i+1]=R[i]+A[i]
  
#m=len(set(R[1:]))
#print((N-m)*m)
#print(R[:10],)
#print(R.count(4))

ans=0
for a in list(set(R[1:])):
  b=R.count(a)
  if b>=2:
    ans+=cmb(b,2)
print(ans)

### FIXED CODE ###

def cmbn2(n):
  #n>=2
  return int(n*(n-1)/2)

N=int(input())
A=list(map(int, input().split()))
R=[0]*(N+1)
D={0:1}
for i in range(N):
  R[i+1]=R[i]+A[i]
  if R[i+1] not in D.keys():
    D[R[i+1]]=1
  else:
    D[R[i+1]]+=1
  
#m=len(set(R[1:]))
#print((N-m)*m)
#print(R[1:10],)
#print(R.count(4))

ans=0
for b in D.values():
  
  if b>=2:
    ans+=cmbn2(b)
print(ans)
#print(D.values())
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys


MOD = 10 ** 9 + 7

input = sys.stdin.readline
N = int(input())
S = input()
if S[0] == 'W' or S[-1] == 'W':
    print(0)
    exit(0)

Dc = 1
LRsub = 1
Pattern = 1
for i in range(1,2*N):
    Dc = Dc if S[i] != S[i-1] else -Dc
    if Dc < 0:
        Pattern *= LRsub
    LRsub += Dc

if LRsub == 0:
    for i in range(2,N+1):
        Pattern *= i
        Pattern = Pattern % MOD
    print(Pattern)
else:
    print(0)


### FIXED CODE ###

# -*- coding: utf-8 -*-

MOD = 10 ** 9 + 7

N = int(input())
S = list(map(lambda x: int(x == "W"),input()))
if S[0] or S[-1]:
    print(0)
    exit(0)

Dc = 1
LRsub = 1
Pattern = 1
Sp = S[0]

for i in range(1,N*2):
    Sc = S[i]
    Dc = Dc if Sc != Sp else -Dc
    Sp = Sc
    if Dc < 0:
        Pattern = (Pattern * LRsub) % MOD
    LRsub += Dc

if LRsub == 0:
    for i in range(2,N+1):
        Pattern = (Pattern * i) % MOD
    print(Pattern)
else:
    print(0)
### BUGGY CODE ###

s = input()
q = int(input())

inv = False
mae = ''
usiro = ''

for _ in range(q):
    tmp = list(input().split())
    if tmp == ['1']:
        inv = not inv

    elif tmp[1] == '1' and not inv:
        mae += tmp[2]
    elif tmp[1] == '2' and not inv:
        usiro += tmp[2]
    elif tmp[1] == '1' and inv:
        usiro += tmp[2]
    elif tmp[1] == '2' and inv:
        mae += tmp[2]

    # print(mae,s,usiro)

ans = mae[::-1] + s + usiro

if inv:
    ans = ans[::-1]

print(ans)

### FIXED CODE ###

s = input()
q = int(input())

inv = False
mae = ''
usiro = ''

for _ in range(q):
    tmp = input()
    if tmp[0] == '1':
        inv = not inv

    else:
        _,f,c = tmp.split()

        if f == '1' and not inv:
            mae += c
        elif f == '2' and not inv:
            usiro += c
        elif f == '1' and inv:
            usiro += c
        elif f == '2' and inv:
            mae += c

    # print(mae,s,usiro)

ans = mae[::-1] + s + usiro

if inv:
    ans = ans[::-1]

print(ans)
### BUGGY CODE ###

N = int(input())
S = list(input())

import itertools
import copy

counter = 0
flag_list = [i for i in range(2*N)]
flag = itertools.combinations(flag_list, N)


for f in flag:
    red = ""
    s = copy.copy(S)
    for i in f:
        red += s[i]
        s[i] = "0"
    blue = "".join(s)[::-1].replace("0", "")
    if red == blue:
        counter += 1


print(counter)


### FIXED CODE ###

N = int(input())
S = input()

S1, S2 = S[:N], S[N:][::-1]

dic = {}
keys = []
Ans = 0

for i in range(2 ** N):
    red, blue, red2, blue2 = "", "", "", ""
    # 半分ずつbit全探索
    bits = bin(2 ** N + i)[3:]
    for j in range(N):
        if bits[j] == "0":
            red += S1[j]
            red2 += S2[j]
        else:
            blue += S1[j]
            blue2 += S2[j]
    # あとで数える際に使うので記録しておく
    keys.append(red2 + "-" + blue2)
    # 半分全列挙
    key = red + "-" + blue
    if key not in dic.keys():
        dic[key] = 1
    else:
        dic[key] += 1

for key in keys:
    Ans += dic.get(key, 0)

print(Ans)
### BUGGY CODE ###

import queue
H, W = map(int, input().split())
S = [list(input()) for h in range(H)]
 
Search = [(-1, 0), (0, -1), (1, 0), (0, 1)]
Total = 0
BlackVis = [[False for w in range(W)] for h in range(H)]
for h in range(H):
    for w in range(W):
        if S[h][w] == "#":
            if not BlackVis[h][w]:
                Visited = [[False for w in range(W)] for h in range(H)]
                Visited[h][w] = True
                Q = queue.Queue()
                Q.put((h,w))
                Mult = 1
                Count = 0
                while not Q.empty():
                    now = Q.get()
                    for s in Search:
                        nh, nw = now[0] + s[0], now[1]+s[1]
                        if 0 <= nh < H and 0 <= nw < W:
                            if S[now[0]][now[1]] != S[nh][nw] and not Visited[nh][nw]:
                                Visited[nh][nw] = True
                                Q.put((nh, nw))
                                if S[nh][nw] == ".":
                                    Count += 1
                                else:
                                    BlackVis[nh][nw] = True
                                    Mult += 1
                Total += Count * Mult 
print(Total)

### FIXED CODE ###

import queue
H, W = map(int, input().split())
S = [list(map(int, input().replace(".", "0").replace("#","1"))) for h in range(H)]

Search = [(-1, 0), (0, -1), (1, 0), (0, 1)]
Total = 0
Visited = [[False for w in range(W)] for h in range(H)]
for h in range(H):
    for w in range(W):
        if not Visited[h][w]:
            Visited[h][w] = True
            Color = ([1, 0] if S[h][w] == 0 else [0, 1])
            Q = queue.Queue()
            Q.put((h, w, S[h][w]))
            while not Q.empty():
                nh, nw, nc = Q.get()
                for s in Search:
                    nexth, nextw = nh + s[0], nw + s[1]
                    if 0 <= nexth < H and 0 <= nextw < W:
                        if not Visited[nexth][nextw] and S[nexth][nextw] != nc:
                            nextc = S[nexth][nextw]
                            Visited[nexth][nextw] = True
                            Q.put((nexth, nextw, nextc))
                            Color[nextc] += 1
            Total += Color[0] * Color[1]

print(Total)
### BUGGY CODE ###

def mv(nodes,mvinfo):
    dists=set()
    for node in nodes:
        dists=dists | set(mvinfo[node-1])
    return list(dists)


N,M=[int(e) for e in input().split(' ')]

# 1step
mv1=[[] for n in range(N)]

for i in range(M):
    u,v=[int(e) for e in input().split(' ')]
    mv1[u-1].append(v)
S,T=[int(e) for e in input().split(' ')]

# 1step to 3steps
mv3=[]
for i in range(N):
    mv3.append(mv(mv(mv1[i],mv1),mv1))

# search
reached=set()
for i in range(1,1+N):
    if i==1:
        dists=mv3[S-1]
    else:
        dists=mv(dists,mv3)

    if T in dists:
        break
    
    dists=list(set(dists)-reached)
    reached=reached | set(dists)
else:
    i=-1
print(i)



### FIXED CODE ###

#import queue
from collections import deque
INF=-1

N,M=[int(e) for e in input().split(' ')]

to=[[] for _ in range(N)]

for i in range(M):
    u,v=[int(e) for e in input().split(' ')]
    to[u-1].append(v-1)
S,T=[int(e)-1 for e in input().split(' ')]

dist=[[INF for i in range(3)] for j in range(N)]

q=deque([])
q.append([S,0])

dist[S][0]=0

while(q):
    v,l=q.popleft()
    for v_to in to[v]:
        nl=(l+1)%3
        if dist[v_to][nl] != INF:
            continue
        dist[v_to][nl]=dist[v][l]+1
        q.append([v_to,nl])
ans=dist[T][0]
if ans == INF:
    ans = -1
else:
    ans=ans//3

print(ans)
### BUGGY CODE ###

import unittest
import functools


class TestE(unittest.TestCase):
    def test_1(self):
        self.assertEqual(think([2, 3, 4]), 13)

    def test_2(self):
        self.assertEqual(think([12, 12, 12, 12, 12]), 5)

    def test_3(self):
        self.assertEqual(think([1000000, 999999, 999998]), 996989508)

    def test_4(self):
        self.assertEqual(gcd(3, 2), 1)


def solve():
    a = read()
    result = think(a)
    write(result)


def read():
    n = read_int(1)[0]
    return read_int(n)


def read_int(n):
    return read_type(int, n, sep=' ')


def read_float(n):
    return read_type(float, n, sep=' ')


def read_type(t, n, sep):
    return list(map(lambda x: t(x), read_line().split(sep)))[:n]


def read_line(n=0):
    if n == 0:
        return input().rstrip()
    else:
        return input().rstrip()[:n]


def think(a):
    mode = 10 ** 9 + 7
    lcm_of_all_a = functools.reduce(lambda x, y: lcm(x, y), a, 1)
    b = map(lambda x: (lcm_of_all_a * inverse(x, mode)) % mode, a)
    return sum(b) % mode


def write(result):
    print(result)


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


def gcd(a, b):
    if a < b:
        return gcd(b, a)

    while True:
        if a % b == 0:
            return b
        a, b = b, a % b


def inverse(x, mode):
    return pow(x, mode - 2, mode)


if __name__ == '__main__':
    # unittest.main()
    solve()

### FIXED CODE ###

import unittest
import functools


class TestE(unittest.TestCase):
    def test_1(self):
        self.assertEqual(think([2, 3, 4]), 13)

    def test_2(self):
        self.assertEqual(think([12, 12, 12, 12, 12]), 5)

    def test_3(self):
        self.assertEqual(think([1000000, 999999, 999998]), 996989508)

    def test_4(self):
        self.assertEqual(gcd(3, 2), 1)


def solve():
    a = read()
    result = think(a)
    write(result)


def read():
    n = read_int(1)[0]
    return read_int(n)


def read_int(n):
    return read_type(int, n, sep=' ')


def read_float(n):
    return read_type(float, n, sep=' ')


def read_type(t, n, sep):
    return list(map(lambda x: t(x), read_line().split(sep)))[:n]


def read_line(n=0):
    if n == 0:
        return input().rstrip()
    else:
        return input().rstrip()[:n]


def think(a):
    mode = 10 ** 9 + 7

    lcm_of_all_a = 1
    for e in a:
        lcm_of_all_a = lcm(lcm_of_all_a, e)

    lcm_of_all_a %= mode
    result = 0
    for e in a:
        result += lcm_of_all_a * inverse(e, mode) % mode
        result %= mode
    return result


def write(result):
    print(result)


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


def gcd(a, b):
    if a < b:
        return gcd(b, a)

    while True:
        if a % b == 0:
            return b
        a, b = b, a % b


def inverse(x, mode):
    return pow(x, mode - 2, mode)


if __name__ == '__main__':
    # unittest.main()
    solve()