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

N, K = [int(x) for x in input().split()]
S = input()
lst = []
if (S[0] == '0'): lst.append(0)
cnt = 1
for i in range(N-1):
    if (S[i] == S[i+1]):
        cnt += 1
    else:
        lst.append(cnt)
        cnt = 1 
lst.append(cnt)
if (S[-1] == '0'): lst.append(0)
tmp = []
ans = 0 if (len(lst) != 1) else lst[0] 
for i in range(0, len(lst)-1, 2):
    s = sum(lst[i:(i+1+2*K)])
    if (ans < s):
        ans = s
print(ans)


### FIXED CODE ###

N, K = [int(x) for x in input().split()]
S = input()
lst = []
if (S[0] == '0'): lst.append(0)
cnt = 1
for i in range(N-1):
    if (S[i] == S[i+1]):
        cnt += 1
    else:
        lst.append(cnt)
        cnt = 1 
lst.append(cnt)
if (S[-1] == '0'): lst.append(0)
tmp = [0] + lst[:]
ans = 0 if (len(lst) != 1) else lst[0] 
for i in range(len(lst)):
    tmp[i+1] += tmp[i]
if (((len(lst)+1)//2-K) < 1):
    ans = tmp[-1]
else:
    for i in range(0, (len(lst)+1)//2-K):
        l = 2*i
        r = l + 1 + 2*K
        s = tmp[r] - tmp[l]
        if (ans < s):
            ans = s
print(ans)
### BUGGY CODE ###

n, kk = map(int, input().split())
AA = [list(map(int, input().split())) for _ in range(n)]
mod = 10 ** 9 + 7

# nxnの行列積


def matrix_product(A, B):
    res = [[0] * n for _ in range(n)]
    for i in range(n):
        for k in range(n):
            for j in range(n):
                res[i][j] += A[i][k] * B[k][j]
                res[i][j] %= mod
    return res


def matrix_exponents(A, t):
    res = [[0] * n for _ in range(n)]
    for i in range(n):
        res[i][i] = 1

    while t:
        if t & 1 == 1:
            res = matrix_product(res, A)
        A = matrix_product(A, A)
        t //= 2
    return res


temp = matrix_exponents(AA, kk)


ans = 0
for i in range(n):
    for j in range(n):
        ans += temp[i][j]
        ans %= mod
print(ans)


### FIXED CODE ###

n, kk = map(int, input().split())
AA = [list(map(int, input().split())) for _ in range(n)]
mod = 10 ** 9 + 7

# nxnの行列積


def matrix_product(A, B):
    res = [[0] * n for _ in range(n)]
    for i in range(n):
        for k in range(n):
            for j in range(n):
                res[i][j] += A[i][k] * B[k][j]
                res[i][j] %= mod
    return res


def matrix_exponents(A, t):
    res = [[0] * n for _ in range(n)]
    for i in range(n):
        res[i][i] = 1

    while t:
        if t & 1 == 1:
            res = matrix_product(res, A)
        A = matrix_product(A, A)
        t //= 2
    return res


temp = matrix_exponents(AA, kk)


ans = 0
for i in range(n):
    for j in range(n):
        ans += temp[i][j]
        ans %= mod
print(ans)
### BUGGY CODE ###

# TODO D - Cake 123
# https://atcoder.jp/contests/abc123/tasks/abc123_d

X, Y, Z, K = map(int, raw_input().split())

A = [int(x) for x in raw_input().split()]
B = [int(y) for y in raw_input().split()]
C = [int(z) for z in raw_input().split()]

AB = list()

for x in range(X):
    for y in range(Y):
        AB.append(A[x] + B[y])

AB.sort(reverse=True)

N = min(X*Y, K)

ABC = list()
for ab in range(N):
    for z in range(Z):
        ABC.append(AB[ab] + C[z])
ABC.sort(reverse=True)

for i in range(K):
    print '{}'.format(ABC[i])


### FIXED CODE ###

#abc123d
 
x,y,z,k=map(int,raw_input().split())
a=sorted(map(int,raw_input().split()),reverse=True)
b=sorted(map(int,raw_input().split()),reverse=True)
c=sorted(map(int,raw_input().split()),reverse=True)
 
ab=sorted([i+j for i in a for j in b],reverse=True)
res=sorted([ij+l for ij in ab[:k] for l in c],reverse=True)
for i in res[:k]:
	print i
### BUGGY CODE ###

from itertools import takewhile

# 入力
H, W = map(int, input().split())
S = [input() for _ in range(H)]

# 各マスについて、横方向に照らすマスの数と縦方向に照らすマスの数を求める
x = [[0 for _ in range(W)] for _ in range(H)]
y = [[0 for _ in range(W)] for _ in range(H)]

for i in range(H):
    for j in range(W):
        if x[i][j] == 0:
            w = len(list(takewhile(lambda k: S[i][k] == '.', range(j, W))))
            for k in range(j, j + w):
                x[i][k] = w
        if y[i][j] == 0:
            h = len(list(takewhile(lambda k: S[k][j] == '.', range(i, H))))
            for l in range(i, i + h):
                y[l][j] = h

ans = max(
    x[i][j] + y[i][j] - 1
    for i in range(H)
    for j in range(W)
)
# 出力
print(ans)


### FIXED CODE ###

H, W = map(int, input().split())
S = [input() for _ in range(H)]

dp1 = [[0 for _ in range(W)] for _ in range(H)]
dp2 = [[0 for _ in range(W)] for _ in range(H)]

for i in range(H):
    for j in range(W):
        if dp1[i][j] == 0 and S[i][j] == '.':
            c = 0
            for k in range(i, H):
                if S[k][j] == '.':
                    c += 1
                else:
                    break
            for k in range(i, H):
                if S[k][j] == '.':
                    dp1[k][j] = c
                else:
                    break
for i in range(H):
    for j in range(W):
        if dp2[i][j] == 0 and S[i][j] == '.':
            c = 0
            for k in range(j, W):
                if S[i][k] == '.':
                    c += 1
                else:
                    break
            for k in range(j, W):
                if S[i][k] == '.':
                    dp2[i][k] = c
                else:
                    break

ans = max(
    dp1[i][j] + dp2[i][j] - 1
    for i in range(H)
    for j in range(W)
)
print(ans)
### BUGGY CODE ###

#!/usr/bin/python3
# -*- coding: utf-8 -*-
import numpy as np
n, k = map(int, input().split())
s_list = []
a_list = np.zeros((n + 1), dtype=int)
a_list[1] = 1
for i in range(k):
    l, r = map(int, input().split())
    s_list.append([l, r + 1])

for i in range(1, n):
    if a_list[i] > 998244353:
        a_list[i] %= 998244353
    if a_list[i] == 0:
        continue
    for l, r in s_list:
        if i + l > n:
            continue
        if i + r > n + 1:
            a_list[(i+l):(n+1)] += a_list[i]
        else:
            a_list[(i+l):(i+r)] += a_list[i]
print(a_list[n] % 998244353)



### FIXED CODE ###

#!/usr/bin/python3
# -*- coding: utf-8 -*-
n, k = map(int, input().split())
s_list = []
a_list = [0] * (n + 1)
b_list = [0] * (n + 1)
a_list[1] = 1
b_list[1] = 1
for i in range(k):
    l, r = map(int, input().split())
    s_list.append([l, r + 1])

for i in range(2, n + 1):
    for l, r in s_list:
        t2 = max(0, i - l)
        t1 = max(0, i - r)
        a_list[i] += b_list[t2] - b_list[t1]
    b_list[i] = (b_list[i - 1] + a_list[i]) % 998244353

print(a_list[n] % 998244353)
### BUGGY CODE ###

import itertools


def main():
    N = int(input())
    S = input()

    ans = 0
    for ix_i, i in enumerate(S):
        for j in range(ix_i+1, N):
            if i == S[j]:
                continue
            else:
                if (i == "R") and (S[j] == "G"):
                    ans += S[j + 1:].count("B")
                    if j+(j-ix_i) < N:
                        if S[j + (j - ix_i)] == "B":
                            ans -= 1
                elif (i == "R") and (S[j] == "B"):
                    ans += S[j + 1:].count("G")
                    if j+(j-ix_i) < N:
                        if S[j + (j - ix_i)] == "G":
                            ans -= 1
                elif (i == "G") and (S[j] == "B"):
                    ans += S[j + 1:].count("R")
                    if j+(j-ix_i) < N:
                        if S[j + (j - ix_i)] == "R":
                            ans -= 1
                elif (i == "G") and (S[j] == "R"):
                    ans += S[j + 1:].count("B")
                    if j+(j-ix_i) < N:
                        if S[j + (j - ix_i)] == "B":
                            ans -= 1
                elif (i == "B") and (S[j] == "R"):
                    ans += S[j + 1:].count("G")
                    if j+(j-ix_i) < N:
                        if S[j + (j - ix_i)] == "G":
                            ans -= 1
                elif (i == "B") and (S[j] == "G"):
                    ans += S[j + 1:].count("R")
                    if j+(j-ix_i) < N:
                        if S[j + (j - ix_i)] == "R":
                            ans -= 1
    print(ans)
    return 0

if __name__ == '__main__':
    main()

### FIXED CODE ###

import math
import collections

def main():
    N = int(input())
    S = input()

    c = collections.Counter(S)
    c = c['R'] * c['G'] * c['B']

    count = 0
    for i in range(N):
        for j in range(i+1, N):
            k = 2*j-i
            if k < N:
                if (S[i] != S[j]) and (S[j] != S[k]) and (S[i] != S[k]):
                    count += 1

    print(c - count)

    return 0

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

n=int(input())
L_lst=sorted(list(map(int,input().split())))
cnt=0
for j in range(n-1,1,-1):
    i=j-1
    x=0
    while x<i:
        if L_lst[i]+L_lst[x]>L_lst[j]:
            cnt+=i-x
            i-=1
            x=0
        else:
            x+=1
print(cnt)

### FIXED CODE ###

n=int(input())
L_lst=sorted(list(map(int,input().split())))
cnt=0
for j in range(n-1,1,-1):
    i=j-1
    x=0
    while x<i:
        if L_lst[i]+L_lst[x]>L_lst[j]:
            cnt+=i-x
            i-=1
        else:
            x+=1
print(cnt)
### BUGGY CODE ###

n,k = map(int,input().split())
a = list(map(int,input().split()))
l = [1,a[0]]
tp = a[0]-1
while True:  
  if a[tp] not in l: 
    l.append(a[tp])
    tp = a[tp] -1
  else:
    l.append(a[tp])
    break
    
last = l[-1]

loop = len(l[l.index(last):-1])
first = l.index(last)
if len(l)>k:
  print(l[k])
  exit()
k -=first
k %=loop
if k==0:
  k+=loop
print(l[k+first])

### FIXED CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
l = [1]

for i in range(n):
  l.append(a[l[i]-1])
p = l.index(l[n])
#print(p,l[n])
if k<=n:
  print(l[k])
else:
  x = (k-n+1)%(n-p)
  if x ==0:
    x += (n-p)
    print(l[x-1])
  else:
    print(l[x+p-1])
### BUGGY CODE ###

T = "X"+input()
ans = ""
for i in range(1, len(T)):
    if T[i] == "?":
        if T[i-1] == "D":
            ans += "P"
        else:
            ans += "D"
    else:
        ans += T[i]
print(ans)


### FIXED CODE ###

T = list("X"+input())
for i in range(1, len(T)):
    if T[i] == "?":
        T[i] = "D"

print("".join(T[1:]))
### BUGGY CODE ###

from itertools import product

n = int(input())
P = [0, 0] + [int(i) for i in input().split()]
X = [0] + [int(i) for i in input().split()]

C = [[] for i in range (n+1)]

for i, p in enumerate(P):
    C[p].append(i)

def dfs(i):
    if not C[i]:
        return X[i], 0
    A = set()
    for c in C[i]:
        A.add(dfs(c))

    B = []
    for bits in range(2**(len(A)-1)):
        a, b = 0, 0
        for j, c in enumerate(A):
            a += c[bits >> j & 1]
            b += c[((bits >> j & 1) + 1) % 2]
        if a <= X[i]:
            B.append((X[i], b))
        if b <= X[i]:
            B.append((X[i], a))
    if not B:
        print('IMPOSSIBLE')
        exit()

    return min(B)

dfs(1)
print('POSSIBLE')

### FIXED CODE ###

from itertools import product

n = int(input())
P = [0, 0] + [int(i) for i in input().split()]
X = [0] + [int(i) for i in input().split()]

C = [[] for i in range (n+1)]

for i, p in enumerate(P):
    C[p].append(i)

def dfs(i):
    if not C[i]:
        return X[i], 0

    A = []
    
    for c in C[i]:
        A.append(dfs(c))

    S = 0
    for a in A:
        S += sum(a)

    dp = [[False]*(X[i]+1) for j in range(len(A)+1)]
    dp[0][0] = True

    for j in range(len(A)):
        for k in range(X[i]+1):
            a, b = A[j]
            if a <= k and dp[j][k-a]:
                dp[j+1][k] = True
            elif b <= k and dp[j][k-b]:
                dp[j+1][k] = True
        if not any(dp[j+1]):
            print('IMPOSSIBLE')
            exit()

    b = 0
    for j in range(X[i], -1, -1):
        if dp[len(A)][j]:
            b = j
            break

    return X[i], S - b

dfs(1)
print('POSSIBLE')
### BUGGY CODE ###

x = int(input())
a, b = 0, 0
nx = 'a'
while True:
    if a ** 5 - b ** 5 == x:
        print('{} {}'.format(a, b))
        break
    if -a ** 5 - b ** 5 == x:
        print('{} {}'.format(-a, b))
        break
    if a ** 5 - (-b) ** 5 == x:
        print('{} {}'.format(a, -b))
        break
    if -a ** 5 - (-b) ** 5 == x:
        print('{} {}'.format(-a, -b))
        break
    if nx == 'a':
        a += 1
        nx = 'b'
    else:
        b += 1
        nx = 'a'


### FIXED CODE ###

x = int(input())
for b in range(1000):
    for a in range(1000):
        if a ** 5 - b ** 5 == x:
            print('{} {}'.format(a, b))
            exit()
        if (-a) ** 5 - b ** 5 == x:
            print('{} {}'.format(-a, b))
            exit()
        if a ** 5 - (-b) ** 5 == x:
            print('{} {}'.format(a, -b))
            exit()
        if (-a) ** 5 - (-b) ** 5 == x:
            print('{} {}'.format(-a, -b))
            exit()
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
mul = 1
for i in range(n):
  mul *= a[i]
if (mul > 1000000000000000000):
  print(-1)
else:
  print(mul)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
a = sorted(a)
if 0 in a:
  print(0)
  exit(0)

mul = 1
for i in range(n):
  mul *= a[i]
  if (mul > 1000000000000000000):
  	print(-1)
  	exit(0)

print(mul)
### BUGGY CODE ###

import copy

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

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

if n>2:
    memo = [1]

    for k in range(n):
        t = copy.copy(s_all)
        t.pop(k)

        c = gcd(t[0], t[1])

        for i in t:
            c = gcd(c,i)
            if c<max(memo):
                break

        memo.append(c)

    print(max(memo))

if n==2:
    print(max(s_all))

### FIXED CODE ###

import numpy as np

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

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

l = [0]*n
r = [0]*n

for i in range(1,n):
    l[i]=gcd(l[i-1],s[i-1])

tmp = list(range(0,n-1))
tmp.reverse()
for i in tmp:
    r[i]=gcd(r[i+1],s[i+1])
    
m = list([])

for i in range(n):
    m.append(gcd(l[i],r[i]))

print(max(m))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**8)

N,M = map(int,input().split())
src = [tuple(map(lambda x:int(x)-1,input().split())) for i in range(M)]
Q = int(input())
qs = [tuple(map(int,input().split())) for i in range(Q)]

es = [[] for i in range(N)]
for a,b in src:
    es[a].append(b)
    es[b].append(a)

cs = [0] * N
depth = [0] * N

def rec(v,d,c):
    if d < depth[v]: return
    depth[v] = d
    if cs[v]==0:
        cs[v] = c
    if d==0: return
    for to in es[v]:
        rec(to,d-1,c)

for v,d,c in qs[::-1]:
    rec(v-1,d,c)

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

### FIXED CODE ###

import sys
sys.setrecursionlimit(101010)

N,M = map(int,input().split())
es = [[] for i in range(N)]
for i in range(M):
    a,b = map(lambda x:int(x)-1,input().split())
    es[a].append(b)
    es[b].append(a)
Q = int(input())
qs = [tuple(map(int,input().split())) for i in range(Q)]

mem = [[0,-1] for i in range(N)] # [color,depth] for v
def paint(v,d,c):
    mc,md = mem[v]
    if d <= md: return
    mem[v] = [mc if mc else c, d]
    if d == 0: return
    for to in es[v]:
        paint(to,d-1,c)

for v,d,c in reversed(qs):
    paint(v-1,d,c)
for c,d in mem:
    print(c)
### BUGGY CODE ###

n,k = map(int,input().split())
f = [int(input()) for i in range(n)]
li = []
f.sort()
for i in range(n-k+1) :
    li.append(max(f[i:i+k])-min(f[i:i+k]))
print(min(li))

### FIXED CODE ###

n,k = map(int,input().split())
f = [int(input()) for i in range(n)]
li = []
f.sort()
for i in range(n-k+1) :
    li.append(f[i+k-1]-f[i])
print(min(li))
### BUGGY CODE ###

def main():
  def dp(i):
    for a,b in AB:
      C[i]=min(C[i],C[i-a if i>a else 0]+b)

  H,N=map(int,input().split())
  AB=[list(map(int,input().split())) for _ in range(N)]
  C=[0]+[10**8]*H

  for i in range(1,H+1):
    dp(i)

  print(C[H])

if __name__=='__main__':
  main()


### FIXED CODE ###

import sys
input=sys.stdin.readline

def main():
  def dp(i):
    for a,b in AB:
      T=C[i-a if i>a else 0]+b
      C[i]=T if T<C[i] else C[i]

  H,N=map(int,input().split())
  AB=[list(map(int,input().split())) for _ in range(N)]
  C=[0]+[10**8]*H

  for i in range(1,H+1):
    dp(i)

  print(C[H])

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

n, m = map(int, input().split())
li = []
for i in range(m):
  li.append(list(input().split()))
a = []
b = 0
for j in range(m):
  if li[j][1] == "AC":
    a.append(li[j][0])
  elif li[j][1] == "WA" and li[j][0] not in a:
    b += 1
for k in range(m):
  if li[k][0] not in a:
    b -= 1
print(len(set(a)), b)

### FIXED CODE ###

n, m = map(int, input().split())
li = []
for i in range(m):
  li.append(list(input().split()))
li_a = [0 for i in range(n)]
li_b = [0 for i in range(n)]
a = 0
b = 0
for j in range(m):
  if li[j][1] == "WA":
    li_b[int(li[j][0])-1] += 1
  elif li[j][1] == "AC" and li_a[int(li[j][0])-1] == 0:
    a += 1
    b += li_b[int(li[j][0])-1]
    li_a[int(li[j][0])-1] += 1
print(a, b)
### BUGGY CODE ###

from bisect import bisect_left, bisect_right

n = int(input())
a = list(map(int, input().split()))
a.sort()
m = a[-1]
c = [0] * (m + 1)

for ai in a:
    for i in range(ai, m + 1, ai):
        if bisect_right(a, i) - bisect_left(a, i) == 1:
            c[i] += 1

print(c.count(1))

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
a.sort()
m = a[-1]
c = [0] * (m + 1)

for ai in a:
    for i in range(ai, m + 1, ai):
        c[i] += 1

ans = 0
for ai in a:
    if c[ai] == 1:
        ans += c[ai]

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

import math
from functools import reduce

N = int(input())
s = 0

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

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

for i in range(1, N+1):
    for j in range(1, N+1):
        for k in range(1, N+1):
            s += gcd(i, j, k)


print(s)



### FIXED CODE ###

'''
import math
from functools import reduce

N = int(input())
s = 0

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

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

for i in range(1, N+1):
    for j in range(1, N+1):
        for k in range(1, N+1):
            s += gcd(i, j, k)


print(s)
'''

import math
from functools import reduce
import itertools


N = int(input())
s = 0

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

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

seq = list(range(1, N+1))
comb = list(itertools.combinations_with_replacement(seq,3))

#print(seq)
#print(comb)

i = 1
for c in comb:
    if i == 1 or (c[0] == c[1] and c[1] == c[2]):
        s += gcd(c[0], c[1], c[2])
    elif c[0] != c[1] and c[1] != c[2] and c[0] != c[2]:
        s = s + gcd(c[0], c[1], c[2]) * 6
    else:
        s = s + gcd(c[0], c[1], c[2]) * 3
    i += 1

print(s)
### BUGGY CODE ###

import numpy as np
import sys
# import copy


def xnxn(n=0, flag="v"):
    """
    args:
        int n: a number of lows to read
    example:
        input   1
        retrun  1

        input   1 2 3
        return  [1,2,3]
        input   1 2 3
                4 
        return  [[1,2,3],
                [4]]
    """
    if n == 0:
        temp = list(map(int, input().split()))
        if len(temp) == 1:
            if flag == "l":
                return temp
            else:
                return temp[0]
        elif len(temp) > 1:
            return temp
    else:
        temp = [list(map(int, input().split())) for _ in range(n)]
        return temp


n, k = xnxn()
a = np.array(xnxn(flag="l"))
for _ in range(k):
    tmp = np.zeros(n, dtype="int")
    for i in range(0, n):
        idx_min = max(0, i - a[i])
        idx_max = min(n-1, i + a[i])
        tmp[idx_min:idx_max+1] = tmp[idx_min:idx_max+1]+1
    if np.all(a == tmp):
        break
    a = tmp

for i in a:
    print(i, end=" ")


### FIXED CODE ###

# import numpy as np
import sys
# import copy


def xnxn(n=0, flag="v"):
    """
    args:
        int n: a number of lows to read
    example:
        input   1
        retrun  1

        input   1 2 3
        return  [1,2,3]
        input   1 2 3
                4 
        return  [[1,2,3],
                [4]]
    """
    if n == 0:
        temp = list(map(int, input().split()))
        if len(temp) == 1:
            if flag == "l":
                return temp
            else:
                return temp[0]
        elif len(temp) > 1:
            return temp
    else:
        temp = [list(map(int, input().split())) for _ in range(n)]
        return temp


n, k = xnxn()
a = xnxn(flag="l")
for _ in range(k):
    tmp = [0]*(n+1)
    for i in range(0, n):
        l = max(0, i - a[i])
        r = min(n, i + a[i]+1)
        tmp[l] += 1
        tmp[r] -= 1
    for i in range(1, n):
        tmp[i] += tmp[i - 1]
    if a == tmp:
        break
    a = tmp

for i in a[:n]:
    print(i, end=" ")
### BUGGY CODE ###

import sys
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def LIST(): return list(map(int, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 0, 1, -1, 1, -1, -1, 1]
dy = [1, -1, 0, 0, 1, -1, 1, -1]


NN = 10 ** 6 + 100
primes = []
isprime = [True for _ in range(NN + 1)]
min_factor = [-1 for _ in range(NN + 1)]
#エラトステネスの篩
for i in range(2, NN + 1):
    if not isprime[i]:
        continue
    primes.append(i)
    min_factor[i] = i
    for j in range(i * 2, NN + 1, i):
        isprime[j] = False
        if min_factor[j] == -1:
            min_factor[j] = i
def prime_factrize(n):
    res = []
    while n != 1:
        prime = min_factor[n]
        exp = 0
        while min_factor[n] == prime:
            exp += 1
            n //= prime
        res.append([prime, exp])
    return res


n = INT()
a = LIST()
ll = []
for i in range(n):
    aa = prime_factrize(a[i])
    for j in range(len(aa)):
        if len(ll) == 0:
            ll.append(aa[j])
            ll.sort(key=lambda x: x[0])
        else:
            left = 0
            rght = len(ll) - 1
            while left < rght:
                cntr = (rght + left) // 2
                if ll[cntr][0] == aa[j][0]:
                    left = cntr
                    rght = cntr
                elif ll[cntr][0] > aa[j][0]:
                    rght = cntr - 1
                elif ll[cntr][0] < aa[j][0]:
                    left = cntr + 1
            if ll[left][0] == aa[j][0]:
                ll[left][1] = max(ll[left][1], aa[j][1])
            else:
                ll.append(aa[j])
                ll.sort(key=lambda x: x[0])
l = 1
for i in range(len(ll)):
    l *= pow(ll[i][0], ll[i][1], mod)
ans = 0
for i in range(n):
    ans += l // a[i]
    ans %= mod
print(ans)

### FIXED CODE ###

import sys
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def LIST(): return list(map(int, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 0, 1, -1, 1, -1, -1, 1]
dy = [1, -1, 0, 0, 1, -1, 1, -1]

n = INT()
a = LIST()
l = 1
for i in a:
    l = lcm(l, i)
l %= mod
ans = 0
for i in a:
    ans += l * pow(i, mod - 2, mod)
print(ans % mod)