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

import math
import sys
input = sys.stdin.readline

N, M, L = list(map(int, input().split()))

T = []
T1 = []
for _ in range(N):
    T.append([float("inf")] * N)
    T1.append([float("inf")] * N)
for n in range(N):
    T[n][n] = 0
    T1[n][n] = 0

for _ in range(M):
    A, B, C = list(map(int, input().split()))
    T[A-1][B-1] = C
    T[B-1][A-1] = C

for k in range(N):
    for i in range(N):
        for j in range(N):
            T[i][j] = min(T[i][j], T[i][k] + T[k][j])

for j in range(N):
    for i in range(N):
        if T[j][i] <= L:
            T1[j][i] = 1
            T1[i][j] = 1

for k in range(N):
    for i in range(N):
        for j in range(N):
            T1[i][j] = min(T1[i][j], T1[i][k] + T1[k][j])

Q = int(input())
for _ in range(Q):
    S, G = list(map(int, input().split()))
    if math.isinf(T1[S-1][G-1]):
        print(-1)
    else:
        print(T1[S-1][G-1]-1)


### FIXED CODE ###

import math
import sys
input = sys.stdin.readline

N, M, L = list(map(int, input().split()))

T = []
T1 = []
for _ in range(N):
    T.append([float("inf")] * N)
    T1.append([float("inf")] * N)
for n in range(N):
    T[n][n] = 0
    T1[n][n] = 0

for _ in range(M):
    A, B, C = list(map(int, input().split()))
    A -= 1
    B -= 1
    T[A][B] = C
    T[B][A] = C

for k in range(N):
    for i in range(N):
        for j in range(N):
            if T[i][j] > T[i][k] + T[k][j]:
                T[i][j] = T[i][k] + T[k][j]

for j in range(N):
    for i in range(N):
        if i == j:
            continue
        if T[j][i] <= L:
            T1[j][i] = 1
            T1[i][j] = 1

for k in range(N):
    for i in range(N):
        for j in range(N):
            if T1[i][j] > T1[i][k] + T1[k][j]:
                T1[i][j] = T1[i][k] + T1[k][j]

Q = int(input())
for _ in range(Q):
    S, G = list(map(int, input().split()))
    if math.isinf(T1[S-1][G-1]):
        print(-1)
    else:
        print(T1[S-1][G-1]-1)
### BUGGY CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))

for i in range(M):
    b, c = map(int, input().split())
    A += [c] * b
    if len(A) > 10**7:
        A.sort(reverse=True)
        A = A[:N]
    
A.sort(reverse=True)
print(sum(A[:N]))

### FIXED CODE ###


N, M = map(int, input().split())
A = list(map(int, input().split()))

A.sort()

CB = []
for i in range(M):
    B, C = map(int, input().split())
    CB.append([C, B])
    
CB.sort(reverse=True)

idx = 0
c = 0
for i in range(N):
    if A[i] < CB[idx][0]:
        A[i] = CB[idx][0]
        c += 1
    if CB[idx][1] <= c:
        idx += 1
        c = 0
    if idx >= M:
        break
    #print(A)
        
print(sum(A))
### BUGGY CODE ###

R, G, B, N = map(int, input().split())

ans = 0
for r in range(int(N/R)+1):
    for g in range(int(N/G)+1):
        if r*R + g*G <= N:
            if (N - (r*R + g*G))%B == 0:
                ans += 1

print(ans)


### FIXED CODE ###

R, G, B, N = map(int, input().split())
     
ans = 0
for r in range(int(N/R)+1):
    for g in range(int(N/G)+1):
        if r*R + g*G <= N:
            if (N - (r*R + g*G))%B == 0:
                ans += 1
     
print(ans)
### BUGGY CODE ###

# import numpy as np
h,w = map(int,input().split())
field = []
accum=[[0 for i in range(w)] for j in range(h)]
accumrev=[[0 for i in range(w)] for j in range(h)]
stack = [[0 for i in range(w)] for j in range(h)]
stackrev = [[0 for i in range(w)] for j in range(h)]

for i in range(h):
    field.append(list(input()))
# field = np.array(field)

for i in range(h):
    s = field[i]
    temp = 0
    for j in range(w):
        if s[j] == "#":
            accum[i][j] = 0
            temp = 0
        else:
            temp += 1
            accum[i][j] = temp
    accum[i][-1] = temp
for i in range(h):
    s = field[i]
    temp = 0
    for j in range(1,w+1):
        if s[-j] == "#":
            accumrev[i][-j] = 0
            temp = 0
        else:
            temp += 1
            accumrev[i][-j] = temp
    accumrev[i][0] = temp
# print(field)
# print(np.array(accum))
# print(np.array(accumrev))

nf = list(zip(*field))

for i in range(w):
    s = nf[i]
    temp = 0
    for j in range(h):
        if s[j] == "#":
            stack[j][i] = 0
            temp = 0
        else:
            temp += 1
            stack[j][i] = temp
    stack[-1][i] = temp

for i in range(w):
    s = nf[i]
    temp = 0
    for j in range(1,h+1):
        if s[-j] == "#":
            stackrev[-j][i] = 0
            temp = 0
        else:
            temp += 1
            stackrev[-j][i] = temp
    stackrev[0][i] = temp

# print(field)
# print(np.array(stack))
# print(np.array(stackrev))

# accum = np.array(accum)
# accumrev = np.array(accumrev)
# stack = np.array(stack)
# stackrev = np.array(stackrev)



ans = 0

for i in range(h):
    for j in range (w):
        temp = accum[i][j] + accumrev[i][j] + stackrev[i][j] + stack[i][j]-3
        if temp > ans:
            ans = temp
print(ans)



### FIXED CODE ###

import numpy as np

H,W = map(int, input().split())
s = [list(input()) for j in range(H)]
s = (np.array(s) == ".") * 1

L = np.zeros((H, W), dtype = int)
R = np.zeros((H, W), dtype = int)
U = np.zeros((H, W), dtype = int)
D = np.zeros((H, W), dtype = int)


for j in range(W):
    if j == 0:
        L[:,j] = s[:,j]
    else:
        L[:,j] = (L[:,j-1] + 1) * s[:,j]
        

for j in reversed(range(W)):
    if j == W-1:
        R[:,j] = s[:,j]
    else:
        R[:,j] = (R[:,j+1] + 1) * s[:,j]


for i in range(H):
    if i == 0:
        U[i,:] = s[i,:]
    else:
        U[i,:] = (U[i-1,:] + 1) * s[i,:]

for i in reversed(range(H)):
    if i == H-1:
        D[i,:] = s[i,:]
    else:
        D[i,:] = (D[i+1,:] + 1) * s[i,:]

print(np.max(L + R + U + D - 3))
### BUGGY CODE ###

def cmb(n, r, mod):
    num = 1
    cnt = 1
    for i in range(1, r+1):
        num *= (n-i+1)
        cnt *= i
        if num % cnt == 0:
            num = num//cnt
            cnt = 1
    return (num//cnt) % mod


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

mod = 10**9+7

nCa = cmb(n, a, mod)
nCb = cmb(n, b, mod)


if n <= 10**7:
    nCr = 2**n % mod
else:
    sy = n // 10**7
    am = n % (10**7)
    t = 2**(10**7) % mod
    am = 2**am % mod
    nCr = 1
    for i in range(sy):
        nCr = nCr * t % mod
    nCr = nCr * am % mod

print((nCr-1-nCa-nCb) % mod)


### FIXED CODE ###

def cmb(n, r, mod):
    r = min(n-r, r)
    if r == 0:
        return 1
    over, under = 1, 1
    for i in range(1, r+1):
        over = over * (n-i+1) % mod
        under = under * i % mod
    inv = pow(under, mod-2, mod)
    return over * inv % mod


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

print((pow(2, n, mod) - cmb(n, a, mod) - cmb(n, b, mod) - 1) % mod)
### BUGGY CODE ###

from __future__ import annotations

from dataclasses import dataclass, field
from typing import List


@dataclass
class Shop:
    id: int
    price: int
    stock: int

    def buy(self) -> None:
        self.stock -= 1


@dataclass(frozen=True)
class Shops:
    values: List[Shop] = field(default_factory=list)

    def register(self, shop: Shop) -> None:
        return self.values.append(shop)

    def _bargain_shop(self) -> Shop:
        shops_have_stock = [shop for shop in self.values if shop.stock > 0]

        return sorted(shops_have_stock, key=lambda shop: shop.price)[0]

    def how_much(self, required_num: int) -> int:
        drink_count = 0
        payment = 0

        while True:
            bargain_shop = self._bargain_shop()

            bargain_shop.buy()

            payment += bargain_shop.price
            drink_count += 1

            if drink_count == required_num:
                return payment


def actual(N, M, AB):
    shops = Shops()

    for idx, (a, b) in enumerate(AB, start=1):
        shop = Shop(id=idx, price=a, stock=b)
        shops.register(shop)

    return shops.how_much(required_num=M)

N, M = map(int, input().split())
AB = []
for _ in range(N):
  a, b = map(int, input().split())
  AB.append((a,b))
  
print(actual(N, M, AB))

### FIXED CODE ###

def actual(N, M, AB):
    payment = 0

    shop_order_by_price_desc = sorted(AB, key=lambda x: x[0])

    for price, stock in shop_order_by_price_desc:
        if stock >= M:
            # 端数があるときは、残りの必要分だけ買えばよい
            return payment + (price * M)
        else:
            # 端数がないなら買い切る
            M -= stock
            payment += price * stock


N, M = map(int, input().split())
AB = []
for _ in range(N):
    a, b = map(int, input().split())
    AB.append([a, b])

print(actual(N, M, AB))
### BUGGY CODE ###

from collections import deque

N = int(input())

def pToHW(p):
    p = int(p) - 1
    return divmod(p, N)

P = list(map(pToHW, input().split()))

isFilled = [[False] * N for _ in range(N)]

def calcDist():
    minDist = [[10**18] * N for _ in range(N)]
    que = deque([])
    for h in range(N):
        if isFilled[h][0]:
            que.append((h, 0, 1))
        else:
            que.appendleft((h, 0, 0))
        if isFilled[h][N - 1]:
            que.append((h, N - 1, 1))
        else:
            que.appendleft((h, N - 1, 0))
    for w in range(1, N - 1):
        if isFilled[0][w]:
            que.append((0, w, 1))
        else:
            que.appendleft((0, w, 0))
        if isFilled[N - 1][w]:
            que.append((N - 1, w, 1))
        else:
            que.appendleft((N - 1, w, 0))

    while que:
        h, w, dist = que.popleft()

        if minDist[h][w] <= dist:
            continue
        minDist[h][w] = dist

        for toH, toW in ((h + 1, w), (h - 1, w), (h, w + 1), (h, w - 1)):
            if not (0 <= toH < N and 0 <= toW < N):
                continue

            if isFilled[toH][toW]:
                que.append((toH, toW, dist + 1))
            else:
                que.append((toH, toW, dist))
    return minDist

ans = 0
for h, w in P[::-1]:
    ans += calcDist()[h][w]
    isFilled[h][w] = True
print(ans)


### FIXED CODE ###

import sys
import numpy as np

if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC
    cc = CC('my_module')

    @cc.export('solve', 'i4(i4, i4[:])')
    def solve(N, P):
        minDist = np.ones((N, N), dtype=np.int32)
        isFilled = np.ones((N, N), dtype=np.int32)

        for h in range(N):
            for w in range(N):
                minDist[h][w] = min(h, N - h - 1, w, N - w - 1)

        ans = 0
        for p in P:
            h, w = divmod(p, N)
            ans += minDist[h][w]
            isFilled[h][w] = False

            st = [(h, w)]
            while st:
                h, w = st.pop()
                dist = minDist[h][w] + isFilled[h][w]

                if h + 1 < N and minDist[h + 1][w] > dist:
                    minDist[h + 1][w] = dist
                    st.append((h + 1, w))
                if h - 1 >= 0 and minDist[h - 1][w] > dist:
                    minDist[h - 1][w] = dist
                    st.append((h - 1, w))
                if w + 1 < N and minDist[h][w + 1] > dist:
                    minDist[h][w + 1] = dist
                    st.append((h, w + 1))
                if w - 1 < N and minDist[h][w - 1] > dist:
                    minDist[h][w - 1] = dist
                    st.append((h, w - 1))
        return ans

    cc.compile()
    exit(0)

from my_module import solve

N = int(input())
P = np.asarray(list(map(lambda a: int(a) - 1, input().split())), dtype=np.int32)

print(solve(N, P))
### BUGGY CODE ###

N,K=map(int,input().split())
T=list(map(int,input().split()))

for k in range(42):
    A=T[::]
    L=[0 for _ in range(N)]
    R=[0 for _ in range(N)]
    for i in range(N):
        l=(i+1)-A[i]-0.5
        r=(i+1)+A[i]+0.5
        l=int(l+0.999)
        r=int(r)
        l-=1
        if l<0:
            l=0
        L[l]+=1
        if r>=N:
            continue
        R[r]+=1

    #print(L)
    #print(R)
    T=[0 for _ in range(N)]
    T[0]=L[0]
    for i in range(N-1):
        T[i+1]=T[i]+L[i+1]-R[i+1]
    #print(T)
    if (k+1)==K:
        break 

print(*T)


### FIXED CODE ###

import numpy as np
from numba import jit
N,K=map(int,input().split())
A=list(map(int,input().split()))

@jit
def imos(A):
    B=np.zeros_like(A)
    for i,x in enumerate(A):
        a=max(0,i-x)
        b=min(i+x,N-1)
        B[a]+=1
        if b+1<=N-1:
            B[b+1]-=1
    B=np.cumsum(B)
    return B

for i in range(K):
    if i>=50:
        break
    A=imos(A)
print(*A)
### BUGGY CODE ###

def bit_add(bit, i, x):
    i += 1
    n = len(bit)
    while i <= n:
        bit[i - 1] += x
        i += i & -i


def bit_sum(bit, i):
    result = 0
    i += 1
    while i > 0:
        result += bit[i - 1]
        i -= i & -i
    return result


def main():
    from sys import stdin
    from builtins import int, list, map, range
    readline = stdin.readline
    N, D, A = map(int, readline().split())
    XH = [list(map(int, readline().split())) for _ in range(N)]

    XH.sort()
    result = 0
    bit = [0] * (N + 1)
    for i in range(N):
        x, h = XH[i]
        h -= bit_sum(bit, i)
        if h <= 0:
            continue
        c = (h + A - 1) // A
        result += c
        bit_add(bit, i, c * A)

        ok = i
        ng = N
        while ng - ok != 1:
            m = ok + (ng - ok) // 2
            if XH[m][0] <= x + 2 * D:
                ok = m
            else:
                ng = m
        bit_add(bit, ng, -c * A)
    print(result)


main()


### FIXED CODE ###

N, D, A = map(int, input().split())
XH = [list(map(int, input().split())) for _ in range(N)]

XH.sort()
q = []
t = 0
result = 0
for x, h in XH:
    while True:
        if len(q) == 0:
            break
        if x <= q[0][0]:
            break
        t -= q[0][1]
        q.pop(0)
    h -= t
    if h < 0:
        continue
    c = (h + A - 1) // A
    result += c
    t += c * A
    q.append((x + 2 * D, c * A))
print(result)
### BUGGY CODE ###

#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
p = LI()
p = [((i-1)%n, (i-1)//n) for i in p]
ans = 0
dp = [[min(i, j, n - (i + 1), n - (j + 1)) for j in range(n)] for i in range(n)]
dp2 = [[False]*n for _ in range(n)]
dx, dy = [1, 0, -1, 0], [0, 1, 0, -1]
for (q, r) in p:
    ans += dp[r][q]
    dp2[r][q] = True
    h = [(dp[r][q], r, q)]
    while h:
        d, y, x = heappop(h)
        if not dp2[y][x]:
            d += 1
        for j in range(4):
            ny, nx = y + dy[j], x + dx[j]
            if 0 <= ny < n and 0 <= nx < n:
                if dp[ny][nx] > d:
                    dp[ny][nx] = d
                    heappush(h, (d, ny, nx))
print(ans)
    
    

### FIXED CODE ###

#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
p = LI()
p = [((i-1)%n, (i-1)//n) for i in p]
ans = 0
dp = [[min(i, j, n - (i + 1), n - (j + 1)) for j in range(n)] for i in range(n)]
dp2 = [[False]*n for _ in range(n)]
for (q, r) in p:
    ans += dp[r][q]
    dp2[r][q] = True
    h = [(dp[r][q], r, q)]
    while h:
        d, y, x = h.pop()
        if not dp2[y][x]:
            d += 1
        if x != 0:
            if dp[y][x-1] > d:
                dp[y][x-1] = d
                h.append((d, y, x-1))
        if x != n-1:
            if dp[y][x+1] > d:
                dp[y][x+1] = d
                h.append((d, y, x+1))
        if y != 0:
            if dp[y-1][x] > d:
                dp[y-1][x] = d
                h.append((d, y-1, x))
        if y != n-1:
            if dp[y+1][x] > d:
                dp[y+1][x] = d
                h.append((d, y+1, x))
print(ans)
### BUGGY CODE ###

class DLL:
    class Node:
        def __init__(self, x, y, z):
            self.v = x
            self.prv = y
            self.nxt = z

    def __init__(self):
        init = DLL.Node(None, None, None)
        init.prv = init
        init.nxt = init
        self.size = 0
        self.init = init

    def insert(self, x):
        i = self.init
        j = i.nxt
        k = DLL.Node(x, i, j)
        i.nxt = k
        j.prv = k
        self.size += 1

    def deleteFirst(self):
        if self.size != 0:
            i = self.init
            k = i.nxt
            j = k.nxt
            i.nxt = j
            j.prv = i
            self.size -= 1

    def deleteLast(self):
        if self.size != 0:
            i = self.init
            k = i.prv
            j = k.prv
            i.prv = j
            j.nxt = i
            self.size -= 1

    def delete(self, x):
        if self.size != 0:
            i = self.init
            k = i.nxt
            while 1:
                if k.v == x:
                    i = k.prv
                    j = k.nxt
                    i.nxt = j
                    j.prv = i
                    self.size -= 1
                    break
                else:
                    k = k.nxt

    def prt(self):
        f = self.init
        s = f.nxt
        l = f.prv
        while 1:
            if s != l:
                print(s.v, end=' ')
                s = s.nxt
            else:
                print(l.v)
                break

n = int(input())
L = DLL()

for i in range(n):
    com = input()
    if com == "deleteFirst":
        L.deleteFirst()
    elif com == "deleteLast":
        L.deleteLast()
    else:
        C = com.split()
        if C[0] == "insert":
            L.insert(int(C[1]))
        elif C[0] == "delete":
            L.delete(int(C[1]))
    #L.prt()
    
L.prt()



### FIXED CODE ###

from collections import deque

n = int(input())
L = deque()

for i in range(n):
    com = input()
    if com[0] == 'i':
        C = com.split()
        L.appendleft(int(C[1]))
    else:
        if com[6] == 'F':
            L.popleft()
        elif com[6] == 'L':
            L.pop()
        else:
            C = com.split()
            x = int(C[1])
            try:
                L.remove(x)
            except:
                pass

print(*L)
### BUGGY CODE ###

import math

K = int(input())

ans = 0
for a in range(1,K+1):
  for b in range(1,K+1):
    for c in range(1,K+1):
      ans += math.gcd(math.gcd(a,b),c)

print(ans)

### FIXED CODE ###

import math

K = int(input())

ans = 0
for a in range(1,K+1):
  for b in range(1,K+1):
    for c in range(1,K+1):
      ans += math.gcd(math.gcd(a,b),c)

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

import sys
input = sys.stdin.readline

a,b,c,d = map(int,input().split())
answer = -10000000001
for x in range(a,b+1):
    for y in range(c,d+1):
        answer = max(answer,x*y)
print(answer)



### FIXED CODE ###

import sys
from itertools import combinations
input = sys.stdin.readline

a,b,c,d = map(int,input().split())
h = []
h.append(a*c)
h.append(a*d)
h.append(b*c)
h.append(b*d)

print(max(h))
### BUGGY CODE ###

N=int(input())

for n in range(1,N+1):
    ans=0
    for x in range(1,N ):
        for y in range(1, N):
            for z in range(1, N):
                if x**2+y**2+z**2+x*y+y*z+z*x==n:
                        ans+=1
    print(ans)

### FIXED CODE ###

n=int(input())
ans=[0 for _ in range(10001)]

for x in range(1,101):
  for y in range(1,101):
    for z in range(1,101):
      v=x*x+y*y+z*z+x*y+y*z+z*x
      if v<10001:
        ans[v]+=1

for i in range(n):
  print(ans[i+1])
### BUGGY CODE ###

import sys
from collections import deque

sys.setrecursionlimit(2*10**5)

n, m = list(map(int, input().split()))
ablist = [list(map(int, input().split())) for _ in range(m)]

abq = deque(ablist)
cs = [set(range(1, n+1))]

def connect(graph, node) :
    global c
    c.add(node)
    for a, b in graph :
        if a == node :
            if b not in c :
                connect(graph, b)
        elif b == node :
            if a not in c :
                connect(graph, a)

s = 0
for i in range(m) :
    abq.popleft()
    for csi in cs :
        c = set()
        csix = csi.pop()
        csi.add(csix)
        connect(abq, csix)
        if csi != c :
            d = csi - c
            cs.remove(csi)
            cs.append(c)
            cs.append(d)
            s += len(c)*len(d)
    print(s)

### FIXED CODE ###

from sys import setrecursionlimit
setrecursionlimit(10**5)

n, m = list(map(int, input().split()))
ab = [list(map(int, input().split())) for _ in range(m)]

class UnionFind(list) :
    def __init__(self, n) :
        super().__init__(range(n))
        self.dic = {i:1 for i in range(n)}
        self.fubensa = n*(n-1)//2

    def find(self, i) :
        if self[i] == i : return i
        self[i] = self.find(self[i])
        return self[i]

    def union(self, x, y) :
        x = self.find(x)
        y = self.find(y)
        self[y] = x
        if x != y :
            self.fubensa -= self.dic[x]*self.dic[y]
            self.dic[x] += self.dic[y]
            del self.dic[y]

    def sameroot(self, x, y) :
        return self.find(x) == self.find(y)

uf = UnionFind(n)
ans = []
for a, b in reversed(ab) :
    ans.append(uf.fubensa)
    uf.union(a-1, b-1)
    
for a in reversed(ans) :
    print(a)
### BUGGY CODE ###

N,A,B=map(int,input().split())
res=0
if A==0:
    res=0
else:
    res1=(N//(A+B))*A
    res2=0
    for n in range(1,N%(A+B)+1):
        if n<=A:
            res2+=1
    res=res1+res2
print(res)

### FIXED CODE ###

N,A,B=map(int,input().split())
res=0
N1=N//(A+B)
N2=N%(A+B)
if A==0:
    res=0
elif B==0:
    res=N
else:
    res1=(N1)*A
    if A<=N2:
        res2=A
    else:
        res2=N2
    res=res1+res2
print(res)
### BUGGY CODE ###

from statistics import median
N = int(input())
S = input()
R_lst = []
G_lst = []
B_lst = []
cnt = 0
for i,s in enumerate(S):
    if s == "R":
        R_lst.append(i)
    elif s == "G":
        G_lst.append(i)
    else:
        B_lst.append(i)
for r in R_lst:
    for g in G_lst:
        for b in B_lst:
            mid = median([r,g,b])
            if max(r,g,b) - mid != mid - min(r,g,b):
                cnt += 1
print(cnt)

### FIXED CODE ###

N = int(input())
S = input()
total = S.count("R") * S.count("G") * S.count("B")
sub = 0
for i in range(N):
    for j in range(i + 1, N):
        if S[i] == S[j]:
            continue
        h = j + j - i
        if h > N - 1 or S[j] == S[h] or S[h] == S[i]:
            continue
        sub += 1
print(total - sub)
### BUGGY CODE ###

from functools import reduce
from fractions import gcd
N = int(input())
A = list(map(int, input().split()))


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


def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)


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


y = lcm(*A)
MOD = 10 ** 9 + 7
ans = 0
for i, a in enumerate(A):
    ans += y // a
    ans %= MOD

print(ans)


### FIXED CODE ###

from functools import reduce
from fractions import gcd
N = int(input())
A = list(map(int, input().split()))


lcm = A[0]
for a in A[1:]:
    lcm = lcm * a // gcd(lcm, a)


MOD = 10 ** 9 + 7
lcm %= MOD
ans = 0
for a in A:
    ans += lcm * pow(a, MOD-2, MOD)
    ans %= MOD

print(ans)