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

"""
dp[i][j][k] => i行目、j列のマスまで見る。k個取る時の最高値。
"""
def main():
    import sys
    input = sys.stdin.readline
    R,C,K = map(int,input().split())
    items = [[0]*C for _ in range(R)]
    for _ in range(K):
        r,c,v = map(int,input().split())
        items[r-1][c-1] = v

    dp = [[[0]*4 for _ in range(C)]for _ in range(R)]

    for i in range(R):
        for j in range(C):
            v = items[i][j]
            if i == 0 and j == 0 and v != 0:
                dp[i][j][1] = v

            #上から降りてくる場合の価値を求める
            if i != 0:
                #i行目j列のアイテムを取らない場合
                dp[i][j][0] = max(dp[i-1][j])
                #i行目j列のアイテムを取る場合
                if v!=0:
                    dp[i][j][1] = max(dp[i-1][j]) + v

            #左から入ってくる場合の価値を求める
            if j != 0:
                if v == 0:
                    for k in range(4):
                        dp[i][j][k] = max(dp[i][j][k],dp[i][j-1][k])
                else:
                    for k in range(1,4):
                        dp[i][j][k] = max(dp[i][j][k],dp[i][j-1][k],dp[i][j-1][k-1]+v)
        if i > 0:
            dp[i-1] = []
    print(max(dp[-1][-1]))
main()

### FIXED CODE ###

"""
dp[i][j]　=> i行目j列目がゴールの場合の最大値
"""
def main():
    import sys
    input = sys.stdin.readline
    R,C,K = map(int,input().split())
    items = [[0]*(C) for _ in range(R)]

    for _ in range(K):
        r,c,v = map(int,input().split())
        items[r-1][c-1] = v

    dp = [[0]*4 for _ in range(C)]
    dp[0][1] = items[0][0]
    for i in range(R):
        for j in range(C):
            v = items[i][j]
            if i==0 and j == 0:
                continue

            if i!=0:
                #上から入る場合のシミュレート
                dp[j][0] = max(dp[j])
                if v:
                    dp[j][1] = dp[j][0]+v

            if j!=0:
                #左から入る場合のシミュレート
                dp[j][0] = max(dp[j][0],dp[j-1][0])
                if v:
                    #itemが存在する場合の処理
                    for k in range(1,4):
                        dp[j][k] = max(dp[j][k],dp[j-1][k-1]+v,dp[j-1][k])
                else:
                    for k in range(1,4):
                        dp[j][k] = max(dp[j][k],dp[j-1][k])
    print(max(dp[-1]))
main()
### BUGGY CODE ###

print(sum([i for i in range(int(input()))]))

### FIXED CODE ###

n=int(input())
print(n*(n-1)//2)
### BUGGY CODE ###

import heapq

xs,ys,xt,yt = map(int,input().split())

N = int(input())

xyr = []
xyr.append([xs,ys,0])

#0からN+1までの距離

for i in range(N):

    x,y,r = map(int,input().split())
    xyr.append([x,y,r])

xyr.append([xt,yt,0])

d = [[float("inf")] * (N+2) for i in range(N+2) ]

for i in range(N+2):

    for j in range(N+2):

        nowd = ((xyr[i][0] - xyr[j][0]) ** 2 + (xyr[i][1] - xyr[j][1]) ** 2) ** 0.5
        nowd = max ( 0 , nowd - xyr[i][2] - xyr[j][2] )

        d[i][j] = nowd
        d[j][i] = nowd

ans = [float("inf")] * (N+2)
ans[0] = 0

q = [[0,0]]

#print (d)

while len(q) > 0:

    np = heapq.heappop(q)
    now = np[1]
    if ans[now] != np[0]:
        continue

    for i in range(N+2):
        if ans[i] > ans[now] + d[now][i]:
            ans[i] = ans[now] + d[now][i]
            heapq.heappush(q,[ans[i] , i])

#print (ans)
print (ans[-1])
    


### FIXED CODE ###

import heapq

xs,ys,xt,yt = map(int,input().split())

N = int(input())

xyr = []
xyr.append([xs,ys,0])

#0からN+1までの距離

for i in range(N):

    x,y,r = map(int,input().split())
    xyr.append([x,y,r])

xyr.append([xt,yt,0])

d = [[float("inf")] * (N+2) for i in range(N+2) ]

for i in range(N+2):

    for j in range(N+2):

        nowd = ((xyr[i][0] - xyr[j][0]) ** 2 + (xyr[i][1] - xyr[j][1]) ** 2) ** 0.5
        nowd = max ( 0 , nowd - xyr[i][2] - xyr[j][2] )

        d[i][j] = nowd
        d[j][i] = nowd

ans = [float("inf")] * (N+2)
ans[0] = 0
used = [False] * (N+2)

while True:

    v = -1

    #未到達の点に関して最も数値の小さい点を選ぶ
    for i in range(N+2):
        if not used[i] and (v == -1 or ans[v] > ans[i]):
            v = i
    
    if v == -1:
        break
    
    used[v] = True
    for i in range(N+2):
        ans[i] = min(ans[i] , ans[v] + d[v][i])

#print (used,ans)
print (ans[-1])
### BUGGY CODE ###

import sys
input = sys.stdin.readline

n, k = map(int, input().split())
h = tuple(map(int, input().split()))

dp = [0] + [float("inf")] * (n-1)
#print(dp)

for i in range(1,n):
    K = max(0, i - k) # K: 'i' ループ目の最大ジャンプ幅 'k' 
    H = h[i]          # H: 'i' ループ目の足場の高さ'h'
    for j in range(K, i):
        dp[i] = min(dp[i], dp[j]+abs(H - h[j]))
#print(dp)

print(dp[-1])



### FIXED CODE ###

n, k = map(int, input().split())
l = list(map(int, input().split()))

dp = [float('inf') for _ in range(n)]
dp[0] = 0

for i in range(n-1):
    for j in range(1, k+1):
        if i+j <= n-1:
            temp = dp[i] + abs(l[i+j] - l[i])
            if temp < dp[i+j]:
                dp[i+j] = temp

print(dp[-1])
### BUGGY CODE ###

import math, heapq
from operator import itemgetter as ig
from collections import defaultdict as dd
# 定数
INF = float("inf")
MOD = int(1e9 + 7)
# データ構造：ヒープ
class heapque:
    def __init__(self, *args):
        self.que = []
        for arg in args:
            self.push(arg)
    def push(self, v):
        heapq.heappush(self.que, v)
    def pop(self):
        return heapq.heappop(self.que)
# 最大公約数 / 最小公倍数
def gcd(v1, v2):
    if v2 == 0:
        return v1
    return gcd(v2, v1 % v2)
def lcm(v1, v2):
    return (v1 // gcd(v1, v2)) * v2
# 二分探索
def bsr(a, v, lo=0, hi=None):
    if hi == None:
        hi = len(a) - 1
    if hi < lo:
        return lo
    mi = (lo + hi) // 2
    if v < a[mi]:
        return bsr(a, v, lo, mi - 1)
    else:
        return bsr(a, v, mi + 1, hi)
# Union-Find木
class uft:
    def __init__(self, n):
        self.height = [1] * n
        self.group = [-1] * n
    def root(self, v):
        if self.group[v] < 0:
            return v
        self.group[v] = self.root(self.group[v])
        return self.group[v]
    def size(self, v):
        return - self.group[self.root(v)]
    def merge(self, v1, v2):
        v1, v2 = self.root(v1), self.root(v2)
        if v1 == v2:
            return
        if self.height[v1] < self.height[v2]:
            self.group[v2] += self.group[v1]
            self.group[v1] = v2
            self.height[v2] = max(self.height[v1] + 1, self.height[v2])
        else:
            self.group[v1] += self.group[v2]
            self.group[v2] = v1
            self.height[v1] = max(self.height[v1] , self.height[v2] + 1)

def main():
    S = input()
    dp = [[0 for _ in range(13)] for _ in range(len(S) + 1)]
    dp[0][0] = 1
    for i, s in enumerate(S):
        i += 1
        loop = range(10) if s == "?" else [int(s)]
        for n in range(13):
            for m in loop:
                dp[i][(n * 10 + m) % 13] += dp[i - 1][n]
                dp[i][(n * 10 + m) % 13] %= MOD
    print(dp[-1][5])

main()


### FIXED CODE ###

MOD = 10 ** 9 + 7

S = input()
dp = [[0] * 13 for _ in range(len(S) + 1)]
dp[0][0] = 1

for i, s in enumerate(S):
	if s == "?":
		for n in range(13):
			for m in range(10):
				mod = (n * 10 + m) % 13
				dp[i + 1][mod] += dp[i][n]
				dp[i + 1][mod] %= MOD
	else:
		m = int(s)
		for n in range(13):
			mod = (n * 10 + m) % 13
			dp[i + 1][mod] += dp[i][n]
			dp[i + 1][mod] %= MOD

#for l in dp:
#	print(l)

print(dp[-1][5])
### BUGGY CODE ###

from collections import deque
import copy
H,W = map(int, input().split())
field = [[j == "#" for j in input()] for _ in range(H)]
dy = [1,-1,0,0]
dx = [0,0,1,-1]

queue = deque()
# sy,sx = 0,0
# gy,gx = H-1,W-1
for i in range(H):
    for j in range(W):
        if field[i][j] == True:
            queue.append([i,j])
# queue = [[sy,sx]]
flag = False
count = 0
while True:
    count += 1
    nqueue = deque()
    while queue:
        h,w = queue.popleft()
        for i in range(4):
            nh = h + dy[i]
            nw = w + dx[i]
            if (0<=nh<H) and (0<=nw<W):
                if field[nh][nw] == False:
                    field[nh][nw] = True
                    nqueue.append([nh,nw])
    if nqueue:
        queue = copy.copy(nqueue)
    else:
        break
print(count-1)
    

### FIXED CODE ###

from collections import deque
import copy

def main():
    h, w = map(int, input().split())
    a = [[j == "#" for j in input()] for _ in range(h)]


    # スタート地点をqueueに追加
    que = deque([(i, j) for i in range(h) for j in range(w) if a[i][j]])

    count = 0
    while True:
        count += 1
        nque = deque()
        while que:
            y, x = que.popleft()
            if x > 0 and not a[y][x-1]:
                a[y][x-1] = True
                nque.append((y,x-1))
            if x < w-1 and not a[y][x+1]:
                a[y][x+1] = True
                nque.append((y,x+1))
            if y > 0 and not a[y-1][x]:
                a[y-1][x] = True
                nque.append((y-1,x))
            if y < h-1 and not a[y+1][x]:
                a[y+1][x] = True
                nque.append((y+1,x))

        if nque:
            que = copy.copy(nque)
        else:
            break

    print(count - 1)

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

def main():
    N = int(input())
    
    A = [None] * N
    for i in range(N):
        A[i] = list(map(int, input().split()))
        
    
    day = 0
    roop_flag = True
    
    b = [A[i][0] for i in range(N)]

    while roop_flag:
        
        day += 1
        # 基本はNGの状態にしておく
        roop_flag = False
        done = [False] * N
        
        
        for i in range(N):
            if b[i] is None:
                continue
            
            if not done[i] and not done[b[i] - 1]:
                if b[b[i] - 1] == i + 1:
                    roop_flag = True
                    
                    done[i] = True
                    done[b[i] - 1] = True
                    
                    A[i] = A[i][1:]
                    A[b[i] -1] = A[b[i] - 1][1:]

                    if len(A[b[i] - 1]) > 0:
                        b[b[i] - 1] = A[b[i] - 1][0]
                    else:
                        b[b[i] - 1] = None
                    
                    if len(A[i]) > 0:
                        b[i] = A[i][0]
                    else:
                        b[i] = None
                    

        if b == [None] * N:
            print(day)
            quit()
            
        
    print(-1)
    

    
if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
 
N = int(input())

A = [None] * N
# インデックス：-1で先頭にアクセスするため前後反転
# 最初の選手を指す場合０になるように-1した値を保持
# 全組み合わせを試合し終わった時は−１になるようにする
for i in range(N):
    A[i] = [-1] + [int(x) - 1 for x in input().split()[::-1]]


def f(candi):
    
    played = []
    
    # 次に試合する可能性のある選手を順次チェック
    for n in candi:
        target = A[n][-1]
        if A[target][-1] == n:
            played.append(n)
        
    new_candi = set()    
    for n in played:
        # 試合ずみの組み合わせを削除
        A[n].pop()
        # 試合する人の候補に追加
        new_candi.add(n)
        # 次の対戦相手を試合の候補に追加
        if A[n][-1] != -1:
            new_candi.add(A[n][-1])
            
    return len(played), new_candi


answer = 0
# 最悪の試合数（二倍された値）
rest = N*(N-1)
# 試合する人の候補
play_candi = set(range(N))

while True:
    answer += 1
    x, play_candi = f(play_candi)
    # 行われた試合数を確認
    if x == 0:
        answer = -1
        break
        
    rest -= x
    if rest ==0:
        break
        
print(answer)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
ans = []
for i in range(1,n+1):
    ans.append(a.count(i))
for j in ans:
    print(j)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
ans = [0]*n
for i in a:
    ans[i-1] += 1
for j in ans:
    print(j)
### BUGGY CODE ###

import math 
def num_divisors_table(n):
  maxnum=math.floor((n + 1)/2) #3
  table = [0 for _ in range(n+1)]
  length=n-maxnum
  aftersum=int(maxnum*length+length*(length+1)/2)

  for i in range(1, maxnum+1):
    for j in range(i, n+1, i):
      aftersum += j
      #print(i,j)
  return aftersum

N=int(input())
#Nlist,ans_1=num_divisors_table(N)
#print(Nlist)
print(num_divisors_table(N))
#print(int(sum(Nlist)+ans_1))

### FIXED CODE ###

import math 
def num_divisors_table(n):
  maxnum=math.floor((n + 1)/2) #3
  #table = [0 for _ in range(n+1)]
  length=n-maxnum
  aftersum=int(maxnum*length+length*(length+1)/2)
  aftersum+=(1+n)*n/2
  if n>=2:
    if n%2==0:
      aftersum+=(1+n/2)*n/2
    else:
      aftersum+=(1+(n-1)/2)*(n-1)/2

  for i in range(3, maxnum+1):
    for j in range(i, n+1, i):
      aftersum += j
      #print(i,j)
  return aftersum

N=int(input())
#Nlist,ans_1=num_divisors_table(N)
#print(Nlist)
print(int(num_divisors_table(N)))
#print(int(sum(Nlist)+ans_1))
### BUGGY CODE ###

from collections import Counter
N = int(input())
A = sorted(map(int, input().split()), reverse=False)
m = max(A)+1
s = list(set(A))
dp = [True] * m
for x in s:
    t = x * 2
    while t < m:
        dp[t] = False
        t += x
ans = 0
for a in A:
    if Counter(A)[a] == 1 and dp[a]:
        ans += 1
print(ans)



### FIXED CODE ###

from collections import Counter
n = int(input())
a = list(map(int, input().split()))
c = Counter(a)
p = [True] * (10 ** 6 + 1)
s = list(set(a))
for x in s:
    t = x * 2
    while t <= 10 ** 6:
        p[t] = False
        t += x
ans = 0
for x in a:
    if c[x] == 1 and p[x] == True:
        ans += 1
print(ans)
### BUGGY CODE ###

from collections import deque

S_deque = deque(input())
Q = int(input())

for _ in range(Q):
  item = list(input().split())
  if item[0] == '1':
    S_deque.reverse()

  else:
    if item[1] == '1':
      S_deque.appendleft(item[2])

    else:
      S_deque.append(item[2])

S = list(S_deque)
print(''.join(S))

### FIXED CODE ###

from collections import deque
import sys
input = sys.stdin.readline

S_deque = list(input())
S_deque = deque(S_deque[:-1])
Q = int(input())

top_flag = 1 # 0なら末尾、1なら最初

for _ in range(Q):
  item = list(input().split())
  if item[0] == '1':
    if top_flag == 0:
      top_flag = 1
    else:
      top_flag = 0

  else:
    in_flag = top_flag + int(item[1])
    if in_flag % 2 == 0:
      S_deque.appendleft(item[2])
    else:
      S_deque.append(item[2])

if top_flag == 0:
  S_deque.reverse()
else:
  pass

print(''.join(S_deque))
### BUGGY CODE ###

def calcExValue(N):
    ev = []
    for i in range(1, N +1):
        ev.append(i * (1/N))
    return(sum(ev))

N, K = [int(i) for i in input().split()]
array = [int(i) for i in input().split()]

max_numbers = []
max_num = 0
for i in range(N-K+1):
    if sum(array[i:i+K]) > max_num:
        max_num = sum(array[i:i+K])
        max_numbers = array[i:i+K]

exv = 0
for n in max_numbers:
    exv += calcExValue(n)
    
print(exv)

### FIXED CODE ###

import numpy as np

N, K = [int(i) for i in input().split()]
numbers = [int(i) for i in input().split()]

ary = np.array([(1 + n) / 2 for n in numbers])

cumsum = ary.cumsum()

max_exv = cumsum[K-1]
for i in range(N - K):
    if cumsum[i+K] - cumsum[i] > max_exv:
        max_exv = cumsum[i+K] - cumsum[i]
    
print(max_exv)
### BUGGY CODE ###

n,m = map(int, input().split())
x = [0]*n
a = 0
for i in range(m):
  l,r = map(int,input().split())
  for j in range(l-1,r):
    if(n>j):
      x[j] +=1
for i in range(n):
  if(x[i]==m):
    a+=1
print(a)

### FIXED CODE ###

n,m = map(int, input().split())
x = [0]*n
a = 0
l  =[0]*m
r = [0]*m
for i in range(m):
  l[i],r[i]=map(int,input().split())
a = min(r)-max(l)+1
print(max(0,a))
### BUGGY CODE ###

#http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_3_B&lang=jp
#?????\???
#??????????????¨????§?????????¨?????¨?????????????????????????????????????????????????????????
def rrs(quantum, process):
    finished_process = []
    queue = Queue()
    current_time = 0

    for p in process:
       queue.enqueue(p)

    while queue.data:
        p_info = queue.dequeue()
        time = int(p_info[1])
        name = p_info[0]
        if time <= quantum:
            current_time += time
            finished_process.append((name, current_time))
        else:
            current_time += quantum
            queue.enqueue((name, time - quantum))
            
    return finished_process


class Queue:
    def __init__(self):
        self.data = []

    def enqueue(self, d):
        self.data.append(d)

    def dequeue(self):
        r = self.data[0]
        self.data = self.data[1:]
        return r
    
def main():
    info = input().split()
    n_list = int(info[0])
    quantum = int(info[1])
    target_list = [tuple(input().split()) for i in range(n_list)]
    print("\n".join([p + " " + str(t) for p,t in rrs(quantum, target_list)]))
    
if __name__ == "__main__":
    main()

### FIXED CODE ###

#http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_3_B&lang=jp
#?????\???
#??????????????¨????§?????????¨?????¨?????????????????????????????????????????????????????????
def rrs(quantum, process):
    finished_process = []
    queue = Queue()
    current_time = 0
    i = 0
    
    while not len(finished_process) == len(process):
        
        if i < len(process):
            p_info = process[i]
            i += 1
        else:
            p_info = queue.dequeue()
        time = int(p_info[1])
        name = p_info[0]
        
        if time <= quantum:
            current_time += time
            finished_process.append((name, current_time))
        else:
            current_time += quantum
            queue.enqueue((name, time - quantum))
            
    return finished_process


class Queue:
    def __init__(self):
        self.data = []

    def enqueue(self, d):
        self.data.append(d)

    def dequeue(self):
        r = self.data[0]
        self.data = self.data[1:]
        return r
    
def main():
    info = input().split()
    n_list = int(info[0])
    quantum = int(info[1])
    target_list = [tuple(input().split()) for i in range(n_list)]
    print("\n".join([p + " " + str(t) for p,t in rrs(quantum, target_list)]))
    
if __name__ == "__main__":
    main()
### BUGGY CODE ###

from collections import deque
from itertools import product

h, w = map(int, input().split())
c = tuple(map(lambda x: int(x)-1, input().split()))
d = tuple(map(lambda x: int(x)-1, input().split()))
s = list(input() for _ in range(h))

move_a_area = [(0, -1), (-1, 0), (1, 0), (0, 1)]
move_b_area = [(i, j) for i, j in product(range(-2, 3), repeat=2) if (i, j) not in [0, 0] + move_a_area]

INF = 10**12
cost = [[INF] * w for _ in range(h)]
cost[c[0]][c[1]] = 0
que = deque([(c[0], c[1], 0)])

while que:
    y, x, m = que.popleft()
    # Move A
    for dx, dy in move_a_area:
        hh, ww = y + dy, x + dx
        if hh < 0 or h <= hh or ww < 0 or w <= ww or s[hh][ww] == '#' or cost[hh][ww] <= m:
            continue
        cost[hh][ww] = m
        que.append((hh, ww, m))
    # Move B
    for dx, dy in move_b_area:
        hh, ww = y + dy, x + dx
        if hh < 0 or h <= hh or ww < 0 or w <= ww or s[hh][ww] == '#' or cost[hh][ww] <= m + 1:
            continue
        cost[hh][ww] = m + 1
        que.append((hh, ww, m + 1))

print(v if (v := cost[d[0]][d[1]]) < INF else -1)


### FIXED CODE ###

from collections import deque
from itertools import product

h, w = map(int, input().split())
c = tuple(map(lambda x: int(x)-1, input().split()))
d = tuple(map(lambda x: int(x)-1, input().split()))
s = list(input() for _ in range(h))

move_a_area = [(0, -1), (-1, 0), (1, 0), (0, 1)]
move_b_area = [(i, j) for i, j in product(range(-2, 3), repeat=2) if (i, j) not in [(0, 0)] + move_a_area]

cost = [[float('inf')] * w for _ in range(h)]
cost[c[0]][c[1]] = 0
que = deque([(c[0], c[1], 0)])

while que:
    y, x, m = que.popleft()
    # Move A
    for dx, dy in move_a_area:
        hh, ww = y + dy, x + dx
        if hh < 0 or h <= hh or ww < 0 or w <= ww or s[hh][ww] == '#' or cost[hh][ww] <= m:
            continue
        cost[hh][ww] = m
        que.appendleft((hh, ww, m))
    # Move B
    for dx, dy in move_b_area:
        hh, ww = y + dy, x + dx
        if hh < 0 or h <= hh or ww < 0 or w <= ww or s[hh][ww] == '#' or cost[hh][ww] <= m + 1:
            continue
        cost[hh][ww] = m + 1
        que.append((hh, ww, m + 1))

print(cost[d[0]][d[1]] if cost[d[0]][d[1]] < float('inf') else -1)
### BUGGY CODE ###

n,k = map(int,input().split())
list = list(map(int,input().split()))
list.extend([0]*(k-1))

ans = 0
i = 0 
while i < n:
    list_internal = list[i:k+i]
    e = 0
    j = 0
    while j < len(list_internal):
        e += (list_internal[j]+1)/2
        if ans <= e:
            ans = e
        j += 1
    i += 1
print(ans)  

### FIXED CODE ###

n,k = map(int,input().split())
L = list(map(int,input().split()))
 
aaa = sum(L[0:k])
ans = aaa
for i in range(k,n):
    aaa += L[i]
    aaa -= L[i-k]
    if ans <= aaa:
        ans = aaa
    i += 1    
     
print((ans+k)/2)
### BUGGY CODE ###

card, gate = map(int, input().split())
ans = {i for i in range(1, card+1)}
for i in range(gate):
  l, r = map(int, input().split())
  ans = ans & {i for i in range(l, r+1)}
print(len(ans))

### FIXED CODE ###

card, gate = map(int, input().split())
max_l = 0
min_r = 100000
for i in range(gate):
  l, r = map(int, input().split())
  max_l = max(max_l, l)
  min_r = min(min_r, r)
print(len(range(max_l, min_r+1)))
### BUGGY CODE ###

import itertools

N = int(input())
List_S = [""]
for i in range(N):
  S = input()
  if S not in List_S:
    List_S.append(S)
    
print(len(List_S)-1)

### FIXED CODE ###

N = int(input())
List_S = [input() for i in range(N)]
print(len(set(List_S)))
### BUGGY CODE ###

#float型を許すな
#numpyはpythonで
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7
n=I()
lis=LI()
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
lists=[prime_factorize(lis[i]) for i in range(n)]
C=Counter([])
for i in range(n):
    x=Counter(lists[i])
    for j in x.keys():
        C[j]=max(C[j],x[j])
#print(C)

ans=0
for i in range(n):
    x=Counter(lists[i])
    y=1
    for j in C.keys():
        y=y*pow(j,C[j]-x[j],mod)
    #print(y%mod)
    ans=(ans+y)%mod
print(ans%mod)
        
        
    
    
        
    
    


### FIXED CODE ###

#float型を許すな
#numpyはpythonで
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

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

def lcm(a, b):
    return a // gcd(a, b) * b
#print(lcm(lcm(1000000,999999),999998))
#print(999998//2*999999)


#print(1000000*999999*999998%mod)
n=I()
lis=LI()
promod=1
LCM=1
for i in range(n):
    LCM=lcm(lis[i],LCM)
#print(LCM)
for i in range(n):
    promod=(promod*(lis[i]%mod))%mod
smmod=0
for i in range(n):
    smmod=(smmod+promod*pow(lis[i],mod-2,mod))%mod
#print(smmod)
x=(promod*pow(LCM,mod-2,mod))%mod
ans=(smmod*pow(x,mod-2,mod))%mod
print(ans)