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

n, a, q, ms = int(input()), list(map(int, input().split())), input(), map(int, input().split())

cache = {}


def sum_a(tmp, b, i=0, mask=1):
    global a, cache
    if not b:
        return tmp
    elif b in cache:
        return tmp + cache[b]
    elif b & mask:
        tmp += a[i]
        new_b = b ^ mask
    else:
        new_b = b
    result = sum_a(tmp, new_b, i + 1, mask << 1)
    cache[b] = result
    return result


for m in ms:
    for b in range(1, 2 ** n):
        if sum_a(0, b) == m:
            print('yes')
            break
    else:
        print('no')

### FIXED CODE ###

from itertools import combinations

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

l = set(sum(t) for i in range(n) for t in combinations(a, i + 1))

for m in map(int, input().split()):
    print('yes' if m in l else 'no')
### BUGGY CODE ###

if __name__ == '__main__':
    l, r = map(int, input().split())
    min = 2020
    for i in range(l, r):
        res_i = i % 2019
        for j in range(i + 1, r + 1):
            res_j = j % 2019
            res = (res_i * res_j) % 2019
            if min > res:
                min = res
    print(min)


### FIXED CODE ###

if __name__ == '__main__':
    l, r = map(int, input().split())
    if l + 2019 <= r:
        print(0)
        exit()
    m = 2019
    for i in range(l, r):
        res_i = i % 2019
        for j in range(l + 1, r + 1):
            res_j = j % 2019
            res = (res_i * res_j) % 2019
            if m > res:
                m = res
    print(m)
### BUGGY CODE ###

h, w = map(int, raw_input().split())
maze = [list(raw_input()) for i in xrange(h)]

INF = 10 ** 10
my = [-1, 0, 1, 0]
mx = [0, -1, 0, 1]
def bfs(sy, sx, ey, ex):
    q = [(sy, sx)]
    dp = [ [INF for j in xrange(w)] for i in xrange(h) ]
    dp[sy][sx] = 0
    while q:
        (y, x) = q.pop(0)
        if (y, x) == (ey, ex):
            break
        for (dy, dx) in zip(my, mx):
            ny = y + dy
            nx = x + dx
            if ny < 0 or nx < 0 or ny >= h or nx >= w:
                continue
            if maze[ny][nx] == '#':
                continue
            if dp[ny][nx] != INF:
                continue
            dp[ny][nx] = dp[y][x] + 1
            q.append((ny, nx))
    res = dp[ey][ex]
    assert res < INF
    return res

res = 0
for sy in xrange(h):
    for sx in xrange(w):
        if maze[sy][sx] == '#':
            continue
        for ey in xrange(h):
            for ex in xrange(w):
                if maze[ey][ex] == '#':
                    continue
                res = max(res, bfs(sy, sx, ey, ex))
print res


### FIXED CODE ###

h, w = map(int, raw_input().split())
maze = [list(raw_input()) for i in xrange(h)]

INF = 10 ** 10
my = [-1, 0, 1, 0]
mx = [0, -1, 0, 1]
def bfs(sy, sx):
    q = [(sy, sx)]
    dp = [ [INF for j in xrange(w)] for i in xrange(h) ]
    dp[sy][sx] = 0
    while q:
        (y, x) = q.pop(0)
        for (dy, dx) in zip(my, mx):
            ny = y + dy
            nx = x + dx
            if ny < 0 or nx < 0 or ny >= h or nx >= w:
                continue
            if maze[ny][nx] == '#':
                continue
            if dp[ny][nx] != INF:
                continue
            dp[ny][nx] = dp[y][x] + 1
            q.append((ny, nx))
    res = 0
    for i in xrange(h):
        for j in xrange(w):
            if maze[i][j] != '#':
                res = max(res, dp[i][j])
    return res

res = 0
for sy in xrange(h):
    for sx in xrange(w):
        if maze[sy][sx] == '#':
            continue
        res = max(res, bfs(sy, sx))
print res
### BUGGY CODE ###

def main():
    n = int(input())
    S = list(input())
    q = int(input())
    for _ in range(q):
        t, i, c = input().split()
        if t == '1':
            S[int(i)-1] = c
        else:
            print(len(set(S[int(i)-1:int(c)])))
        
if __name__ == "__main__":
    main()   

### FIXED CODE ###

def main():
    n = int(input())
    a = ord("a")
    orda = lambda x: ord(x)-a
    s = list(map(orda, list(input())))
    q = int(input())
    bits = [BIT(n) for _ in range(26)]
    for i, si in enumerate(s, 1):
        bits[si].add(i, 1)
    for _ in range(q):
        t, i, c = input().split()
        i = int(i)
        if t == "1":
            bits[s[i-1]].add(i, -1)
            bits[ord(c)-a].add(i, 1)
            s[i-1] = ord(c)-a
        else:
            c = int(c)
            cnt = 0
            for bit in bits:
                is_in = bit.sum_(c) - bit.sum_(i-1)
                if is_in:
                    cnt += 1
            print(cnt)
            
            
class BIT:
    __slots__ = ["length", "data"]
    def __init__(self, length):
        self.data = [0]*(length+1)
        self.length = length
    
    def add(self, i, x):
        while i < self.length+1:
            self.data[i] += x
            i += i&-i
    
    def sum_(self, i):
        x = 0
        while i > 0:
            x += self.data[i]
            i -= i&-i
        return x


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

import sys
input = sys.stdin.buffer.readline

def main():
    n, x = map(int, input().split())
    A = list(map(int, input().split()))

    def segfunc(x, y):
        if x <= y:
          return x
        else:
          return y

    def init(init_val):
        # set_val
        for i in range(n):
            seg[i+num-1] = init_val[i]
        # built
        for i in range(num-2, -1, -1):
            seg[i] = segfunc(seg[2*i+1], seg[2*i+2])

    def update(k, x):
        k += num - 1
        seg[k] = x
        while k:
            k = (k-1)//2
            seg[k] = segfunc(seg[2*k+1], seg[2*k+2])

    def query(p, q):
        if q <= p:
            return ide_ele
        p += num - 1
        q += num - 2
        res = ide_ele
        while q-p>1:
            if p&1 == 0:
                res = segfunc(res, seg[p])
            if q&1 == 1:
                res = segfunc(res, seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = segfunc(res, seg[p])
        else:
            res = segfunc(segfunc(res, seg[p]), seg[q])
        return res

    # identity element
    ide_ele = 10**9+1

    # num: n以上の最小の2のべき乗
    num = 2**(n-1).bit_length()
    seg = [ide_ele]*2*num

    init(A)

    ans = 10**18
    for k in range(n):
        t = k*x
        for i in range(n):
            if k <= i:
                t += query(i-k, i+1)
            else:
                temp1 = query(0, i+1)
                temp2 = query(n-(k-i), n)
                if temp1 <= temp2:
                    t += temp1
                else:
                    t += temp2
        if t <= ans:
            ans = t
    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys

n, x = map(int,sys.stdin.readline().split())
A = list(map(int,sys.stdin.readline().split()))

ans = 10**18
mins = [a for a in A]
for k in range(n):
    for i in range(n):
        if k <= i:
            mins[i] = min(A[i-k], mins[i])
        else:
            mins[i] = min(A[n-(k-i)], mins[i])
    ans = min(sum(mins)+k*x, ans)
print(ans)
### BUGGY CODE ###

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

B = [(1000, 0)]

for a in A:
    C = []
    for b1, b2 in B:
        C.append((b1, b2))
        if b1 >= a: C.append((b1 % a, b2 + b1 // a))
        if b2: C.append((b1 + b2 * a, 0))
    B = C
    
answer = 1000
for b1, b2 in B:
    if answer < b1:
        answer = b1
print(answer)

### FIXED CODE ###

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

B = [(1000, 0)]

for (i, a) in enumerate(A):
    C = []
    for b1, b2 in B:
        C.append((b1, b2))
        if b1 >= a: C.append((b1 % a, b2 + b1 // a))
        if b2: C.append((b1 + b2 * a, 0))
    C.sort(reverse = True)

    max_rest_A = 0
    if i < N - 1: max_rest_A = max(A[i + 1:])
    
    price = 0
    temp = (0 , 0)
    for c1, c2 in C:
        if price < c1 + c2 * max_rest_A:
            price = c1 + c2 * max_rest_A
            temp = (c1, c2)
    B = [C[0], temp]

answer = 1000
for b1, b2 in B:
    if answer < b1:
        answer = b1
print(answer)
### BUGGY CODE ###

h, w = map(int, input().split())

M = h + w
blck = [M]*(w+2)
data = [blck]
for ln in range(1, h+1):
    line = list(input().rstrip())
    lineN = [M]*(w+2)
    for r, letter in zip(range(1, w+1), line):
        if letter == '#':
            lineN[r] = 0
    data += [lineN]
data += [blck]


for r, c, d in ((range(1, h+1), range(1,w+1), 1), (range(h, 0, -1), range(w,0,-1), -1)):
    for x in r:
        for y in c:
            data[x][y] = min(data[x][y], data[x-d][y]+1, data[x][y-d]+1)

print(max((data[x][y] for x in range(1, h+1) for y in range(1, w+1))))


### FIXED CODE ###

from collections import deque
H,W = map(int, input().split())
A = 0
dp = [None] * H
mat = [None] * (H*W)
matS = matE = 0
for h in range(H):
    s = list(input())
    for w, x in zip(range(W), s):
        if x == "#":
            mat[matE] = (h, w, 0)
            matE+=1
    dp[h] = s

def search(dp, mat, nH, nW, cnt):
    global matE
    if dp[nH][nW] == ".":
        mat[matE] = (nH, nW, cnt+1)
        matE+=1
        dp[nH][nW] = "#"

while matS < matE:
    h, w, cnt = mat[matS]
    matS += 1

    if h > 0:
        search(dp, mat, h - 1, w, cnt)
    if h < H-1:
        search(dp, mat, h + 1, w, cnt)
    if w > 0:
        search(dp, mat, h , w - 1, cnt)
    if w < W-1:
        search(dp, mat, h , w + 1, cnt)

print(cnt)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(100000)

N, K = map(int, raw_input().split())
H = map(int ,raw_input().split())
cost = [-1]*N

def sumOfCost(i):
  if cost[i] >= 0:
    return cost[i]
  elif i == 0:
    soc = 0
  else:
    soc = 1000000000
    for j in range(1, K+1):
      if i - j < 0:
        continue
      soc = min(soc, sumOfCost(i-j)+abs(H[i]-H[i-j]))
  cost[i] = soc
  return soc

print sumOfCost(N-1)
    



### FIXED CODE ###

import sys

sys.setrecursionlimit(100000)

N, K = map(int, raw_input().split())
H = map(int ,raw_input().split())
cost = [-1]*N

def sumOfCost(i):
  if cost[i] >= 0:
    return cost[i]
  elif i == 0:
    soc = 0
  else:
    soc = 1000000000
    for j in reversed(range(1, min(i+1,K+1))):
      soc = min(soc, sumOfCost(i-j)+abs(H[i]-H[i-j]))
  cost[i] = soc
  return soc

print sumOfCost(N-1)
### BUGGY CODE ###

import sys
import math
readline = sys.stdin.readline

def main():
  N, M = map(int, readline().split())
  n = {}
  m = {}
  A = []
  for i in range(N):
    n[i+1] = -1
    m[i+1] = -1
  n[1] = 0
  m[1] = 0
  for i in range(M):
    ai, bi = map(int, readline().split())
    A.append([ai, bi])
  cnt = 1
  depth = 0
  while cnt < N:
    d = []
    next = []
    for j in range(N):
      if n[j+1] == depth:
        d.append(j+1)
    for i in range(len(A)):
      if A[i][0] in d and n[A[i][1]] == -1:
        n[A[i][1]] = depth + 1
        m[A[i][1]] = A[i][0]
        cnt += 1
      elif A[i][1] in d and n[A[i][0]] == -1:
        n[A[i][0]] = depth + 1
        m[A[i][0]] = A[i][1]
        cnt += 1
      elif n[A[i][0]] == -1 or n[A[i][1]] == -1:
        next.append(A[i])
    A = next
    depth += 1
    if len(next) == 0:
      break
    elif depth > N:
      break
  if cnt == N:
    print('Yes')
    for i in range(1, N):
      print(m[i+1])
  else:
    print('No')

if __name__ == '__main__':
  main()

### FIXED CODE ###

import sys
readline = sys.stdin.readline

def main():
  N, M = map(int, readline().split())
  dist = {}
  pre = {}
  A = {}
  for i in range(N):
    dist[i+1] = -1
    pre[i+1] = -1
    A[i+1] = []
  dist[1] = 0
  pre[1] = 0
  for i in range(M):
    ai, bi = map(int, readline().split())
    A[ai].append(bi)
    A[bi].append(ai)
  cnt = 1
  depth = 1
  D = [1]
  while cnt < N:
    next = []
    for i in range(len(D)):
      for j in range(len(A[D[i]])):
        if dist[A[D[i]][j]] == -1:
          dist[A[D[i]][j]] = depth
          pre[A[D[i]][j]] = D[i]
          next.append(A[D[i]][j])
          cnt += 1
    D = next
    depth += 1
    if len(next) == 0:
      break
    elif depth > N:
      break
  if cnt == N:
    print('Yes')
    for i in range(1, N):
      print(pre[i+1])
  else:
    print('No')

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

import fractions

K = input()

Sum = 0
k = int(K)

for A in range(k):
    a = A + 1
    for B in range(k):
        b = B + 1
        gcd_ab = fractions.gcd(a, b)
        for C in range(k):
            c = C + 1

            Sum = Sum + fractions.gcd(gcd_ab, c)

print(Sum)

### FIXED CODE ###

import math
 
K = input()
 
Sum = 0
k = int(K)
 
for A in range(k):
    a = A + 1
    for B in range(k):
        b = B + 1
        gcd_ab = math.gcd(a, b)
        for C in range(k):
            c = C + 1
 
            Sum = Sum + math.gcd(gcd_ab, c)
 
print(Sum)
### BUGGY CODE ###

from scipy.sparse import csr_matrix, csgraph
n, m, s, t = map(int, input().split())
src = [list(map(int, input().split())) for _ in range(m)]
u, v, a, b = zip(*src)
pa = csgraph.dijkstra(csr_matrix((a, (u, v)), (n + 1, n + 1)), False, s)
pb = csgraph.dijkstra(csr_matrix((b, (u, v)), (n + 1, n + 1)), False, t)

dist = [int(pa[-1] + pb[-1])]
for i in range(n - 1, 0, -1):
    dist.append(min(dist[-1], int(pa[i] + pb[i])))

snuk = 10 ** 15
print(*(snuk - d for d in reversed(dist)), sep='\n')

### FIXED CODE ###

from heapq import heappop, heappush
n, m, s, t = map(int, input().split())
edge_a = [set() for _ in range(n + 1)]
edge_b = [set() for _ in range(n + 1)]
for _ in range(m):
    u, v, a, b = map(int, input().split())
    edge_a[u].add((v, a))
    edge_a[v].add((u, a))
    edge_b[u].add((v, b))
    edge_b[v].add((u, b))

def dijkstra(edge, s):
    sp = [10 ** 19] * (n + 1)
    sp[s] = 0
    q = [(0, s)]
    while q:
        dist, s = heappop(q)
        for t, w in edge[s]:
            if dist + w < sp[t]:
                sp[t] = dist + w
                heappush(q, (sp[t], t))
    return sp

sp_a = dijkstra(edge_a, s)
sp_b = dijkstra(edge_b, t)
dist = [int(sp_a[-1] + sp_b[-1])]
for i in range(n - 1, 0, -1):
    dist.append(min(dist[-1], int(sp_a[i] + sp_b[i])))

snuk = 10 ** 15
print(*(snuk - d for d in reversed(dist)), sep='\n')
### BUGGY CODE ###

import bisect
import collections
import sys

sys.setrecursionlimit(100000)
input = sys.stdin.readline
ACMOD = 1000000007
INF = 1 << 62


def lmi():
    return list(map(int, input().split()))


def llmi(n):
    return [lmi() for _ in range(n)]


A, B, N = lmi()
# (A*(x%B) - (A*x)%B )/B

if N < B:
    ans = -INF
    for i in range(1, N + 1):
        ans = max(ans, (A * (i % B) - (A * i) % B) // B)
    print(ans)
    exit()

i = B - 1
print((A * (i % B) - (A * i) % B) // B)


### FIXED CODE ###

import bisect
import collections
import sys

sys.setrecursionlimit(100000)
input = sys.stdin.readline
ACMOD = 1000000007
INF = 1 << 62


def lmi():
    return list(map(int, input().split()))


def llmi(n):
    return [lmi() for _ in range(n)]


A, B, N = lmi()
# (A*(x%B) - (A*x)%B )/B

# if N < B:
#     ans = -INF
#     for i in range(1, N + 1):
#         ans = max(ans, (A * (i % B) - (A * i) % B) // B)
#     print(ans)
#     exit()
#
i = min(B - 1,N)
print((A * (i % B) - (A * i) % B) // B)
### BUGGY CODE ###

L,R = map(int,input().split())
ans = 2019

for i in range(L,R,1):
    for j in range(L+1,R+1,1):
        ans = min(ans, i*j % 2019)
        if ans==0:
            break
print(ans)


### FIXED CODE ###

L,R = map(int,input().split())
ans = 2019

for i in range(L,min(R,L+2019),1):
    for j in range(L+1,min(L+2019,R+1),1):
        ans = min(ans, i*j % 2019)
        if ans==0:
            break
print(ans)
### BUGGY CODE ###

s=input()
l=len(s)
ans=0

for i in range(l):
    if s[i]=="A":
        for j in range(i+1, l):
            if s[j]=="Z":
                if j-i+1>=ans:
                    ans=j-i+1

print(ans)

### FIXED CODE ###

s=input()
l=len(s)
a=[]
z=[]
ans=0
for i in range(l):
    if s[i]=="A":
        a.append(i)
    elif s[i]=="Z":
        z.append(i)

ans=(max(z)-min(a)+1)

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

N=int(input())
listA=list(map(int,input().split()))
listA.sort()
listA2=[0]*N
for i in listA:
  listA2[i-1]+=1
for i in range(1,N+1):
  if i in listA:
    print(listA2[i-1])
  else:
    print(0)

### FIXED CODE ###

import itertools
N=int(input())
listA=list(map(int,input().split()))
listA.sort()
listA2=[0]*N
for i in listA:
  listA2[i-1]+=1
listA=set(listA)  
for i in range(1,N+1):
  if i in listA:
    print(listA2[i-1])
  else:
    print(0)
### BUGGY CODE ###

import collections

def maxsushi(sushi_list,eaten_sushi):
    max_val = [0,0]
    index = 0
    for i in range(len(sushi_list)):
        if(sushi_list[i][1] not in eaten_sushi):
            tmp = sushi_list[i]
            max_val = sushi_list[i]
            index = i
            break
    return max_val,index

N,K = map(int,input().split())
sushi = []
umasa = []
for _ in range(N):
    i,j = map(int,input().split())
    sushi.append(i)
    umasa.append(j)
l = list(zip(umasa,sushi))
l = sorted(l,reverse=True)
sushi_list = list(l)
eat_sushi = sushi_list[0:K]
eaten_sushi = set()
double_sushi = []
for i in range(K):
    if(sushi_list[i][1] not in eaten_sushi):
        eaten_sushi.add(sushi_list[i][1])
    else:
        double_sushi.append((sushi_list[i]))
manzoku = 0
sushi_list = sushi_list[K:N]
for i in range(len(eat_sushi)):
    manzoku += eat_sushi[i][0]
manzoku = manzoku + (len(eaten_sushi)) ** 2
tmp_manzoku = manzoku 
while double_sushi:
    tmp1 = double_sushi.pop()
    tmp2,index = maxsushi(sushi_list,eaten_sushi)
    if(tmp2[0] == 0 and tmp2[1] == 0):
        break
    sushi_list = sushi_list[index:]
    if not sushi_list:
        break
    eaten_sushi.add(tmp2[1])
    tmp_manzoku = tmp_manzoku + tmp2[0] - tmp1[0] + len(eaten_sushi) ** 2 - (len(eaten_sushi) - 1) ** 2
    if (tmp_manzoku > manzoku):
        manzoku = tmp_manzoku
print(manzoku)

### FIXED CODE ###

import collections

index = 0

def maxsushi(sushi_list,eaten_sushi):
    global index
    max_val = [0,0]
    for i in range(index,len(sushi_list)):
        if(sushi_list[i][1] not in eaten_sushi):
            tmp = sushi_list[i]
            max_val = sushi_list[i]
            index = i
            break
    return max_val

N,K = map(int,input().split())
sushi = []
umasa = []
for _ in range(N):
    i,j = map(int,input().split())
    sushi.append(i)
    umasa.append(j)
l = list(zip(umasa,sushi))
l = sorted(l,reverse=True)
sushi_list = list(l)
eat_sushi = sushi_list[0:K]
eaten_sushi = set()
double_sushi = []
for i in range(K):
    if(sushi_list[i][1] not in eaten_sushi):
        eaten_sushi.add(sushi_list[i][1])
    else:
        double_sushi.append((sushi_list[i]))
manzoku = 0
sushi_list = sushi_list[K:N]
for i in range(len(eat_sushi)):
    manzoku += eat_sushi[i][0]
manzoku = manzoku + (len(eaten_sushi)) ** 2
tmp_manzoku = manzoku 
while double_sushi:
    tmp1 = double_sushi.pop()
    tmp2 = maxsushi(sushi_list,eaten_sushi)
    if(tmp2[0] == 0 and tmp2[1] == 0):
        break
    eaten_sushi.add(tmp2[1])
    tmp_manzoku = tmp_manzoku + tmp2[0] - tmp1[0] + len(eaten_sushi) ** 2 - (len(eaten_sushi) - 1) ** 2
    if (tmp_manzoku > manzoku):
        manzoku = tmp_manzoku
print(manzoku)
### BUGGY CODE ###

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

max_count = 0
for i in range(10**5+1):
    count = 0
    for j in range(-1,2):
        count += A.count(i+j)
    max_count = max(count, max_count)
print(max_count)

### FIXED CODE ###

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

max_count = 0

L = [0]*10**5
for i in A:
    L[i] += 1

for i in range(10**5+1):
    count = 0
    for j in range(-1,2):
        if i+j >= 0 and i+j < 10**5:
            count += L[i+j]
    max_count = max(count, max_count)
print(max_count)
### BUGGY CODE ###

n=int(input())
l=[0]*n
l[:]=map(int,input().split())
ans=0
l=sorted(l)[::-1]
for i in range(n-2):
  for j in range(i+1,n-1):
    for k in range(j+1,n):
      if l[i]<l[j]+l[k]:
        ans+=1
      else:
        break
print(ans)

### FIXED CODE ###

import bisect
N=int(input())
L=list(map(int,input().split()))
L=sorted(L)
ans=0
for i in range(N):
    for j in range(i+1,N):
        k=bisect.bisect_left(L,L[i]+L[j])
        ans+=k-j-1
print(ans)
### BUGGY CODE ###

"""
最長経路問題として解く。

各試合のノードを作成。
各試合ノードごとに、「この試合が終わったら、次はこの試合ができるようになる。」という対応関係を作っていく。
"""
def main():
    import sys
    sys.setrecursionlimit(1000000)

    N = int(input())

    A = [[0]*(N)]
    for _ in range(N):
        A.append([0]+list(map(int,input().split())))
    
    #選手iにとって、選手jが何番目の相手かを逆引きするメモを用意しておく。
    reverseMemo = {i:{} for i in range(1,N+1)}
    for i in range(1,N+1):
        for j in range(1,N):
            a = A[i][j]
            reverseMemo[i][a] = j

    matchs = []
    for i in range(1,N+1):
        for j in range(i+1,N+1):
            matchs.append((i,j))

    edges = {}
    for match in matchs:
        edges[match] = []
        i,j = match
        if reverseMemo[i][j] != N-1:
            nx = A[i][reverseMemo[i][j]+1]
            edges[match].append((min(i,nx),max(i,nx)))
        if reverseMemo[j][i] != N-1:
            nx = A[j][reverseMemo[j][i]+1]
            edges[match].append((min(j,nx),max(j,nx)))

    stepMemo = {}
    def dfs(i,j,cnt):
        if cnt > len(matchs):
            print(-1)
            exit()
        #i,jの試合日を含めて、あと何日必要なのかを返す。
        if (i,j) not in stepMemo:
            res = 1
            for a,b in edges[(i,j)]:
                res = max(res,dfs(a,b,cnt+1)+1)
            stepMemo[(i,j)] = res
        return stepMemo[(i,j)]

    ans = 0
    for i in range(1,N+1):
        for j in range(i+1,N+1):
            ans = max(ans,dfs(i,j,1))
    print(ans)
main()

### FIXED CODE ###

"""
最長経路問題として解く。

各試合のノードを作成。
各試合ノードごとに、「この試合が終わったら、次はこの試合ができるようになる。」という対応関係を作っていく。
"""
def main():
    import sys
    sys.setrecursionlimit(1000000)
    input = sys.stdin.readline

    N = int(input())

    A = [[0]*(N)]
    for i in range(N):
        A.append([0]+list(map(int,input().split())))
    
    #選手iにとって、選手jが何番目の相手かを逆引きするメモを用意しておく。
    reverseMemo = [[-1]*(N+1) for _ in range(N+1)]
    for i in range(1,N+1):
        for j in range(1,N):
            a = A[i][j]
            reverseMemo[i][a] = j
    edges = {}
    for i in range(1,N+1):
        for j in range(i+1,N+1):
            match = (i,j)
            edges[match] = []
            if reverseMemo[i][j] != N-1:
                nx = A[i][reverseMemo[i][j]+1]
                edges[match].append((min(i,nx),max(i,nx)))
            if reverseMemo[j][i] != N-1:
                nx = A[j][reverseMemo[j][i]+1]
                edges[match].append((min(j,nx),max(j,nx)))
    
    del reverseMemo
    del A
    
    stepMemo = {}
    def dfs(i,j,path):
        #i,jの試合日を含めて、あと何日必要なのかを返す。
        if (i,j) not in stepMemo:
            if (i,j) in path:
                print(-1)
                exit()
            else:
                path.add((i,j))
            res = 1
            for a,b in edges[(i,j)]:
                res = max(res,dfs(a,b,path)+1)
            stepMemo[(i,j)] = res
        return stepMemo[(i,j)]

    ans = 0
    for i in range(1,N+1):
        for j in range(i+1,N+1):
            if (i,j) not in stepMemo:
                ans = max(ans,dfs(i,j,set()))
    print(ans)
main()
### BUGGY CODE ###

import sys
input=sys.stdin.buffer.readline
n=int(input())
l=list(map(int,input().split()))
f=l[0]
from fractions import gcd

for i in l:
    f=f*i//gcd(f,i)
mod=10**9+7
ans=0
for i in l:
  ans+=f//i
  ans%=mod
print(ans%mod)


### FIXED CODE ###

def s():
  from sys import stdin
  read=stdin.buffer.readline
  n=int(read())
  l=list(map(int,read().split()))
  f=l[0]
  mod=10**9+7
  def gcd(s,d):
    s,d=max(s,d),min(s,d)
    while  d:
      s,d=d,s%d
    return s
  for i in l:
    f=i*f//gcd(i,f)
  ans=0
  for iu in l:
    b,u,v=mod,1,0
    while b:
      t=iu//b;iu,b=b,iu%b;u-=t*v;u,v=v,u
    ans+=(f*u%mod)%mod
    ans%=mod
  print(ans)
  
if __name__=="__main__":s()