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

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

dp = [[[False]*1009 for _ in range(4)] for _ in range(30009)]
dp[0][0][0] = True

for i in range(N):
    for j in range(4):
        for k in range(1000):
            if not dp[i][j][k]:
                continue

            dp[i + 1][j][k] = True
            if j <= 2:
                dp[i+1][j+1][k*10 + int(S[i])] = True

print(sum(dp[N][3]))


### FIXED CODE ###

def ok(target, S):
    for t in target:
        if t in S:
            S = S[S.index(t)+1:]
        else:
            return False
    return True


N = int(input())
S = input()
ans = 0

for i in range(0, 999+1):
    target = str(i).zfill(3)
    ans += ok(target, S)

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

import sys
sys.setrecursionlimit(10**6)

def dfs(v, u, k):
    for i in d[v]:
        if i[0] == u:
            continue
        kkyori[i[0]] = k + i[1]
        dfs(i[0], v, k + i[1])

N = int(input())
d = [[] for _ in range(N)]
for i in range(N - 1):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    d[a].append((b, c))
    d[b].append((a, c))
kkyori = [0] * N

Q, K = map(int, input().split())
dfs(K - 1, -1, 0)
for i in range(Q):
    x, y = map(int, input().split())
    print(kkyori[x - 1] + kkyori[y - 1])

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)

def dfs(v, u, k):
    for i in d[v]:
        if i[0] == u:
            continue
        kkyori[i[0]] = k + i[1]
        dfs(i[0], v, k + i[1])

N = int(input())
d = [[] for _ in range(N)]
for i in range(N - 1):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    d[a].append((b, c))
    d[b].append((a, c))
kkyori = [0] * N

Q, K = map(int, input().split())
dfs(K - 1, -1, 0)
for i in range(Q):
    x, y = map(int, input().split())
    print(kkyori[x - 1] + kkyori[y - 1])
### BUGGY CODE ###


from collections import defaultdict

def main():
    #bfならどう解く？
    #O(n2)で解ける
    N = int(input())
    S = input()
    
    length = 1
    ans = 0
    while length<= N//2:
        seen = defaultdict(int)
        for start in range(length):
            for idx in range(start, N-length+1, length):
                sub = S[idx:idx+length]
                if sub in seen:
                    prev_idx = seen[sub]
                    if prev_idx + length <= idx:
                        ans = length
                        break
                else:
                    seen[sub] = idx
        length += 1
    
    print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

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

    ans = 0
    dp = [[0] * (N+1) for _ in range(N+1)]
    for i in range(N-1, -1, -1):
        for j in range(N-1, i, -1):
            if S[i] == S[j]:
                dp[i][j] = dp[i+1][j+1] + 1
                tmp = min(dp[i][j], j-i)
                ans = max(ans, tmp)
    print(ans)

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

import sys

def f(x):
    p=0
    cnt=0
    for i in range(n-1,-1,-1):
        while p<n and a[i]+a[p]<x:
            p+=1
        cnt+=n-p
    return cnt

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

l,r=a[0]*2,a[n-1]*2

while r-l>0:
    if r-l<=1:
        if f(r)==m: md=r;break 
        else: md=l;break
    md=(r+l)//2
    k=f(md)
    if k==m: break
    elif k>m: l=md
    else: r=md

p=0
cnt=0
ans=0

for q in range(n-1,-1,-1):
    try:
        while p<n and a[q]+a[p]<=md:
            p+=1
    except:
        b=1
        while True:
            b+=1

    if p==n: break
    cnt+=n-p
    ans+=a[q]*(n-p)*2


ans+=(m-cnt)*md
print(ans)


### FIXED CODE ###

import sys

def f(x):
    p=0
    cnt=0
    for i in range(n-1,-1,-1):
        while p<n and a[i]+a[p]<x:
            p+=1
        cnt+=n-p
    return cnt

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

l,r=a[0]*2,a[n-1]*2
md=(r+l)//2
while r-l>0:
    if r-l<=1:
        if f(r)==m: md=r;break 
        else: md=l;break
    md=(r+l)//2
    k=f(md)
    if k==m: break
    elif k>m: l=md
    else: r=md

p=0
cnt=0
ans=0

for q in range(n-1,-1,-1):
    try:
        while p<n and a[q]+a[p]<=md:
            p+=1
    except:
        b=1
        while True:
            b+=1

    if p==n: break
    cnt+=n-p
    ans+=a[q]*(n-p)*2


ans+=(m-cnt)*md
print(ans)
### BUGGY CODE ###

s = input()
q = int(input())
q_list = [input().split() for i in range(q)]

flag = False
for q_num in q_list:
    if int(q_num[0]) == 1:
        if flag == False:
            flag = True
        else:
            flag = False
    
    else:
        if int(q_num[1]) == 1 and flag == False or int(q_num[1]) == 2 and flag == True:
            s = q_num[2] + s
        else:
            s = s + q_num[2]

if flag:
    print(s[::-1])
else:
    print(s)

### FIXED CODE ###

s = input()
q = int(input())
q_list = [input().split() for i in range(q)]

flag = False
add_after = ""
add_before = ""
for q_num in q_list:
    if int(q_num[0]) == 1:
        if flag == False:
            flag = True
        else:
            flag = False
    
    else:
        if int(q_num[1]) == 1 and flag == False or int(q_num[1]) == 2 and flag == True:
            add_before = q_num[2] + add_before
        else:
            add_after = add_after + q_num[2]

result = add_before + s + add_after
if flag:
    print(result[::-1])
else:
    print(result)
### BUGGY CODE ###

n = int(input())
xys = [[] for _ in range(n)]
for i in range(n):
    a = int(input())
    for j in range(a):
        x, y = map(int, input().split())
        xys[i].append((x-1, y))

def digitsum(x, base=2):
    ret = 0
    while x>0:
        ret += x % base
        x = x // base
    return(ret)

ans = 0
for i in range(1<<n):
    ok = True
    for j in range(i):
        # if jth person may be honest, verify testimony of him.
        if (i>>j) & 1 == 1:
            for xy in xys[j]:
                x, y = xy
                if (i>>x) & 1 != y:
                    ok = False
                    break
        if not ok:
            break
    if ok:
        ans = max(ans, digitsum(i))
print(ans)

### FIXED CODE ###

n = int(input())
xys = [[] for _ in range(n)]
for i in range(n):
    a = int(input())
    for j in range(a):
        x, y = map(int, input().split())
        xys[i].append((x-1, y))

def digitsum(x, base=2):
    ret = 0
    while x>0:
        ret += x % base
        x = x // base
    return ret

ans = 0
for i in range(1<<n):
    ok = True
    for j in range(n):
        # if jth person may be honest, verify testimony of him.
        if (i>>j) & 1 == 1:
            for xy in xys[j]:
                x, y = xy
                if (i>>x) & 1 != y:
                    ok = False
                    break
        if not ok:
            break
    if ok:
        ans = max(ans, digitsum(i))
print(ans)
### BUGGY CODE ###

def divisors(n):
    i = 1
    r = []
    while i * i <= n:
        if n % i == 0:
            r.append(i)
            if i != n // i:
                r.append(n // i)
        i += 1
    return r

def main():
    N = int(input())
    A = list(map(int, input().split()))
    dup = set()
    T = set()
    for a in A:
        if a in T:
            dup.add(a)
        else:
            T.add(a)
    r = 0
    for a in A:
        if a in dup:
            continue
        for d in divisors(a):
            if d == a:
                continue
            if d in T:
                break
        else:
            r += 1
    return r

print(main())


### FIXED CODE ###

def main():
    N = int(input())
    A = list(map(int, input().split()))
    A.sort()
    dp = [False] * (A[-1] + 1)
    r = 0

    for i, a in enumerate(A):
        if dp[a]:
            continue
        dp[a::a] = [True] * len(dp[a::a])
        if i < N - 1 and A[i + 1] == a:
            continue
        r += 1
    return r


print(main())
### BUGGY CODE ###

s=input()
q=int(input())
for _ in range(q):
	k=input()
	if k[0] == "1":
		s = s[::-1]
	else:
		if k[2] == "1":
			s = k[4:]+s
		else:
			s = s+k[4:]
print(s)

### FIXED CODE ###

from collections import deque
s=input()
Q=int(input())
hanten = 0
mae = deque()
ushiro = deque()
for i in range(Q):
	q=input()
	if q=="1":
		hanten ^= 1
	else:
		if q[2] == "1":
			if hanten == 0:
				mae.appendleft(q[4])
			else:
				ushiro.append(q[4])
		else:
			if hanten == 0:
				ushiro.append(q[4])
			else:
				mae.appendleft(q[4])
if hanten == 0:
	print("".join(mae) + s + "".join(ushiro))
else:
	print(("".join(mae) + s + "".join(ushiro))[::-1])
### BUGGY CODE ###

K, S=list(map(int, input().split()))
c=0
for i in range(0, S+1):
    for j in range(0, i+1):
        if j<=K and i-j<=K and S-i<=K:
            c+=1
print(c)

### FIXED CODE ###

K, S=list(map(int, input().split()))
c=0
for i in range(0, min(2*K+1, S+1)):
    for j in range(0, min(K+1,i+1)):
        if j<=K and i-j<=K and S-i<=K:
            c+=1
print(c)
### BUGGY CODE ###

n = int(input())
s = input().split()
count = 0
for i in range(n-1):
    if s[i] == '1':
        count += 1
print(count)
for i in range(n-1):
    count = 0
    num = i + 2
    for j in range(i+1,n-1):
        NUM = int(s[j])
        if NUM == num:
            count += 1
    print(count)

### FIXED CODE ###

n = int(input())
s = input().split()
A = [[0] for i in range(n)]
for i in range (n-1):
    j = int(s[i])-1
    A[j] += [1]
for i in range(n):
    print(len(A[i])-1)
### BUGGY CODE ###

mod=10**9+7
N,K=map(int,input().split())
Ans=[1 for k in range(K)]
c=K
Ans[0]=pow(K,N,mod)
for k in range(2,(K+1)//2+1):
    d=K//k
    if c==d:
        Ans[k-1]=Ans[k-2]
    else:
        Ans[k-1]=pow(d,N,mod)
        c=d
for j in range(K,1,-1):
    for l in range(j//2,0,-1):
        if j%l==0:
            Ans[l-1]-=Ans[j-1]
for j in range(K):
    Ans[j]*=j+1
print(sum(Ans)%mod)

### FIXED CODE ###

N, K = map(int, input().split())
mod = 10**9 + 7

  
fact_count = [0 for _ in range(K+1)]
for k in range(1, K+1):
  fact_count[k] = K//k

ans = 0
count = [0 for _ in range(K+1)]
for k in range(K, 0, -1):
  c = pow(fact_count[k], N, mod)
  j = 2*k
  l = 2
  while(j<=K):
    c -= count[j]
    l += 1
    j = k*l
  count[k] = c
  c = c*k%mod
  ans += c
  ans %= mod
print(ans)
### BUGGY CODE ###

from collections import deque
import copy
def bfs():
  H, W = map(int, input().split())
  maze = [list(input()) for i in range(H)]
  S = []
  for i in range(H):
    for j in range(W):
      if maze[i][j] == ".":
        maze[i][j] = float("inf")
        S.append([i, j])
      else:
        maze[i][j] = -1
  ans = 0
  q = deque()
  for k in range(len(S)):
    maze1 = copy.deepcopy(maze)
    maze1[S[k][0]][S[k][1]] = 0
    q.append([S[k][0],S[k][1]])
    while len(q)>0:
      y, x = q.popleft()
      for i, j in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
        nexty, nextx = y+i, x+j
        if nexty < 0 or nexty>=H or nextx < 0 or nextx>=W:
          continue
        if maze1[nexty][nextx] != -1:
          if maze1[nexty][nextx] > maze1[y][x]:
            maze1[nexty][nextx] = maze1[y][x] + 1
            q.append([nexty, nextx])
            ans = max(ans, maze1[nexty][nextx])
  print(ans)
bfs()

### FIXED CODE ###

from collections import deque
import copy
def bfs():
    h,w = map(int, input().split())
    maze = [list(input()) for i in range(h)]
    S, G = [], []
    for y in range(h):
        for x in range(w):
            if maze[y][x]=='.':
                S.append([y,x])
                G.append([y,x])
                maze[y][x]=float("inf")
            else:
                maze[y][x]=-1
    l = []
    ans = 0
    for i in range(len(S)):
        maze1 = copy.deepcopy(maze)
        maze1[S[i][0]][S[i][1]]=0
        que=deque([[S[i][0],S[i][1]]])
        while que:
          y,x=que.popleft()
          for k,m in [(1,0),(0,1),(-1,0),(0,-1)]:
            nexty,nextx=y+k,x+m
            if nexty < 0 or nexty >= h or nextx < 0 or nextx >= w:
                continue
            dist=maze1[nexty][nextx]
            if dist!=-1:
              if dist>maze1[y][x]+1:
                maze1[nexty][nextx]=maze1[y][x]+1
                que.append([nexty,nextx])
            ans = max(ans, maze1[nexty][nextx])
    print(ans)
bfs()
### BUGGY CODE ###

n,q=map(int,input().split())
neighbor=[[]  for _ in range(n+1)]
ans=[0]*(n+1)

for _ in range(n-1):
    a,b=map(int,input().split())
    neighbor[a].append(b)
    neighbor[b].append(a)


for _ in range(q):
    p,x=map(int,input().split())
    ans[p]+=x

visit=[True]*(n+1)
tmp=[1]
for x in tmp:
    visit[x]=False
    for y in neighbor[x]:
        if visit[y]:
            tmp.append(y)
            ans[y]+=ans[x]

print(" ".join(map(str,ans[1:])))


### FIXED CODE ###

n,q=map(int,input().split())
neighbor=[[]  for _ in range(n+1)]
ans=[0]*(n+1)

for _ in range(n-1):
    a,b=map(int,input().split())
    neighbor[a].append(b)
    neighbor[b].append(a)


for _ in range(q):
    p,x=map(int,input().split())
    ans[p]+=x

visit=[True]*(n+1)
tmp=[1]
for x in tmp:
    visit[x]=False
    for y in neighbor[x]:
        if visit[y]:
            tmp.append(y)
            ans[y]+=ans[x]

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

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

subs = [p[ind:ind+k] for ind in range(n-k+1)]
sums = [sum(elm) for elm in subs]
max_val = float(max(sums))
k = float(k)
print(max_val/2+k/2)

### FIXED CODE ###

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

exps = [(elm+1)/2 for elm in p]
#print(exps)
cum_sums = [0]*(n+1)
for ind in range(n):
  cum_sums[ind+1] = cum_sums[ind]+exps[ind]
#print(cum_sums)
k_exps = [cum_sums[ind+k]-cum_sums[ind] for ind in range(n-k+1)]
#print(k_exps)
print(max(k_exps))
### BUGGY CODE ###

from itertools import combinations

N = int(input())

line = input()
target_itr = (list(combinations(range(N), 3)))


def ok_list(target_itr):
    for target in target_itr:
        if (target[1] - target[0]) != (target[2] - target[1]):
            yield target[0], target[1], target[2]


def itr_line(line, target_itr):
    result = 0
    for combination in target_itr:
        i = line[combination[0]]
        j = line[combination[1]]
        k = line[combination[2]]

        if i != j and i != k and j != k:
            result += 1
    print(result)


itr_line(line, ok_list(target_itr))


### FIXED CODE ###

from itertools import groupby
from statistics import median
from sys import exit

N = int(input())

line = ([(index, v) for index, v in enumerate(input())])


def types(line): return line[1]
def index(line): return line[0]


gp = groupby(sorted(line, key=types), types)

d = {}

for k, v in gp:
    indexes = set([i for i, value in v])
    d[k] = indexes

if 'R' not in d or 'G' not in d or 'B' not in d:
    print(0)
    exit()

delete = 0


for differ in range(1, N):
    for start in range(N):
        if start + differ*2 > N - 1:
            break

        i = line[start]
        j = line[start + differ]
        k = line[start + differ*2]

        if len({i[1], j[1], k[1]}) != 3:
            continue

        upper = max(i[0], j[0], k[0])
        lower = min(i[0], j[0], k[0])
        median_num = median([i[0], j[0], k[0]])
        if upper - median_num == median_num - lower:
            delete += 1

print(len(d['R']) * len(d['G']) * len(d['B']) - delete)
### BUGGY CODE ###

from collections import defaultdict
n,x = map(int,input().split())
a = list(map(int,input().split()))
a.sort(reverse=True)
ls = []
for i in range(n):
  t = x
  for j in range(i+1)[::-1]:
    t %= a[j]
  ls.append(t)
mod = 10**9+7
rng = 300
fctr = [1]
finv = [1]
for i in range(1,rng):
  fctr.append(fctr[-1]*i%mod)
def inv(a):
  return pow(a,mod-2,mod)
dp = [defaultdict(int) for i in range(n+1)]
dp[0][x] = 1
for i in range(n):
  for j in range(i+1,n+1):
    for k in dp[i].keys():
      num = dp[i][k]
      k %= a[j-1]
      dp[j][k] = (dp[j][k]+num*fctr[n-i-1]*inv(fctr[n-j]))%mod
ans = 0
for i,x in dp[n].items():
  ans = (ans+i*x)%mod
print(ans)

### FIXED CODE ###

from collections import defaultdict
n,x = map(int,input().split())
a = list(map(int,input().split()))
a.sort(reverse=True)
mod = 10**9+7
dp = [defaultdict(int) for i in range(n+1)]
dp[0][x] = 1
for i in range(1,n+1):
  for j in dp[i-1].keys():
    k = j%a[i-1]
    dp[i][j] = (dp[i][j]+dp[i-1][j]*(n-i))%mod
    dp[i][k] = (dp[i][k]+dp[i-1][j])%mod
ans = 0
for i,x in dp[n].items():
  ans = (ans+i*x)%mod
print(ans)
### BUGGY CODE ###

S = input()
T = input()
s = len(S)
t = len(T)
C = 100000
for i in range(t):
    for j in range(i, s - t + 1 + i):
        if S[j] == T[i]:
            c = i
            for k in range(1, t - i):
                if S[j + k] != T[i + k]:
                    c += 1
            C = min(C, c)
if C == 100000:
    C = t
print(C)

### FIXED CODE ###

S = input()
T = input()
s = len(S)
t = len(T)
C = 100000
for i in range(t):
    for j in range(i, s - t + 1 + i):
        if S[j] == T[i]:
            c = i
            for k in range(1, t - i):
                if S[j + k] != T[i + k]:
                    c += 1
            C = min(C, c)
if C == 100000:
    C = t
print(C)
### BUGGY CODE ###

import math
L, R = map(int, input().split())
#R=min(R,(L+2019)*2)
m=2018
for i in range(L,R+1):
  for j in range(i,R+1):
    if i==j:
      continue
    if (i*j)%2019<m:
      m=(i*j)%2019
print(m)

### FIXED CODE ###

import math
L, R = map(int, input().split())
R=min(R,L+2019)
m=2018
for i in range(L,R+1):
  for j in range(i,R+1):
    if i==j:
      continue
    if (i*j)%2019<m:
      m=(i*j)%2019
print(m)
### BUGGY CODE ###

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

### FIXED CODE ###

import collections

n=int(input())
a=list(map(int,input().split()))
coun=collections.Counter(a)
for i in range(1,n+1):
  print(coun[i])
### BUGGY CODE ###

n = int(input())
s = input()
c = 0
def cha_3(num_):
    d = 3 - len(num_)
    return d*"0" + num_

for i in range(1000):
    num = cha_3(str(i))
    num_c = 0
    for j in range(len(s)):
        if s[j] == num[num_c]:
            num_c += 1
            if num_c == 3:
                c += 1
                break
print(c)






### FIXED CODE ###

n = int(input())
s = input()
c = 0
def cha_3(num_):
    d = 3 - len(num_)
    return d*"0" + num_

for i in range(1000):
    num = cha_3(str(i))
    num_c = 0
    for j in range(len(s)):
        if s[j] == num[num_c]:
            num_c += 1
            if num_c == 3:
                c += 1
                break
print(c)
### BUGGY CODE ###

n, m = map(int, input().split())
L = [list(map(int, input().split())) for _ in range(m)]
print(sum([all([l <= i+1 <= r for l, r in L]) for i in range(n)]))

### FIXED CODE ###

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

MAX = 10**9 + 7


def main():
    H, N = map(int, input().split())
    damage_costs = [tuple(map(int, input().split())) for _ in range(N)]

    dp = [MAX] * (H + 1 + max(damage_costs, key=lambda x: x[0])[0])
    dp[0] = 0

    for (ai, bi) in damage_costs:
        for i, dp_i in enumerate(dp):
            if i >= ai:
                dp[i] = min(dp_i, dp[i - ai] + bi)

    print(min(dp[H:]))


if __name__ == '__main__':
    main()


### FIXED CODE ###

MAX = 10**9 + 7
 
 
H, N = map(int, input().split())
damage_costs = [tuple(map(int, input().split())) for _ in range(N)]

dp = [MAX] * (H + 1 + max(damage_costs, key=lambda x: x[0])[0])
dp[0] = 0

for (ai, bi) in damage_costs:
    for i, dp_i in enumerate(dp):
        if i >= ai:
            dp[i] = min(dp_i, dp[i - ai] + bi)

print(min(dp[H:]))
### BUGGY CODE ###

N = int(input())
A = input().split()
A = [int(i) for i in A]
A.sort()

while(1):
    
    for i in range(len(A)-1):
        A[i+1] = A[i+1]%A[0]
        if(A[i+1] ==0):
            del A[i+1]
            A.sort()
            break
    if(len(A)==1):
        break
    A.sort()
print(A[0])

### FIXED CODE ###

from sys import stdin
from functools import reduce
import fractions
#input = stdin.readline
N = int(input())
A = list(set(map(int,input().split())))
answer = reduce(fractions.gcd, A)
print(answer)
### BUGGY CODE ###

n,q=map(int,input().split())
s=input()
ac=[0]*(n-1)
for i in range(n-1):
  ac[i]=(s[i]=="A" and s[i+1]=="C")
ans=""
for i in range(q):
  l,r=map(int,input().split())
  ans+=str(sum(ac[l-1:r-1]))+"\n"
print(ans,end="")

### FIXED CODE ###

n,q=map(int,input().split())
s=input()
ac=[0]*(n+1)
for i in range(n):
  ac[i]=ac[i-1]+(s[i:i+2]=="AC")
for i in range(q):
  l,r=map(int,input().split())
  print(ac[r-2]-ac[l-2])
### BUGGY CODE ###

N=int(input())
List=list(map(int,input().split()))
lastindex=N//2
AList=List[:]
List.sort()
for index in range(N):
    BList=List[:]
    BList.remove(AList[index])
    print(BList[N//2-1])

    

### FIXED CODE ###

N=int(input())
List=list(map(int,input().split()))
AList=List[:]
List.sort()
div=List[N//2]
backdiv=List[N//2-1]
for indexnum in AList:
    if div > indexnum:
        print(div)
    else:
        print(backdiv)
### BUGGY CODE ###

def resolve():
    from fractions import gcd
    n = int(input())
    a = list(map(int, input().split()))
    mod = 10**9 + 7
    lsd = a[0]
    for i in range(1, n):
        lsd = (lsd * a[i]) // gcd(lsd, a[i])
 
    ans = 0
    for i in range(n):
        ans += (lsd//a[i]) % mod
 
    print(int(ans % mod))
 
 
if __name__ == '__main__':
    resolve()

### FIXED CODE ###

def resolve():
    def lcm(X, Y):
        x = X
        y = Y
        if y > x:
            x, y = y, x
        while x % y != 0:
            x, y = y, x % y
        return X * Y // y
    n = int(input())
    a = list(map(int, input().split()))
    mod = 10**9 + 7
    lsd = a[0]
    for i in range(1, n):
        lsd = lcm(lsd, a[i])
    lsd = lsd % mod

    ans = 0
    for i in range(n):
        ans += (lsd * pow(a[i], mod-2, mod)) % mod

    print(int(ans % mod))

resolve()
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
AB = (A, B)
INF = 10**18

ans = INF
for state in range(1 << N):
    even = []
    odd = []

    for i in range(N):
        isReverse = (state & (1 << i)) >> i
        val = AB[isReverse][i]

        if i % 2 == 0:
            (even, odd)[isReverse].append((val, i))
        else:
            (odd, even)[isReverse].append((val, i))

    if len(even) != -(-N // 2) or len(odd) != N // 2:
        continue

    even.sort()
    odd.sort()
    odd.append((-1, -1))
    V = []
    P = []
    for (l, i), (r, j) in zip(even, odd):
        V.append(l)
        P.append(i)
        if r >= 0:
            V.append(r)
            P.append(j)

    if not all(l <= r for l, r in zip(V, V[1:])):
        continue

    cnt = 0
    for i, p in enumerate(P):
        for q in P[:i]:
            if p < q:
                cnt += 1
    ans = min(ans, cnt)

print(ans if ans != INF else -1)


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
AB = (A, B)
INF = 10**18

ans = INF
for state in range(1 << N):
    even = []
    odd = []

    for i in range(N):
        isReverse = (state & (1 << i)) >> i
        val = AB[isReverse][i]

        if i % 2 == 0:
            (even, odd)[isReverse].append((val, i))
        else:
            (odd, even)[isReverse].append((val, i))

    if len(even) != -(-N // 2) or len(odd) != N // 2:
        continue

    even.sort()
    odd.sort()
    odd.append((-1, -1))
    V = []
    P = []
    for (l, i), (r, j) in zip(even, odd):
        V.append(l)
        P.append(i)
        if r >= 0:
            V.append(r)
            P.append(j)

    if not all(l <= r for l, r in zip(V, V[1:])):
        continue

    cnt = 0
    for i, p in enumerate(P):
        for q in P[:i]:
            if p < q:
                cnt += 1
    ans = min(ans, cnt)

print(ans if ans != INF else -1)
### BUGGY CODE ###

r,g,b,n =map(int,input().split())
count =0
for i in range(4000):
    if r * i <= n:
        for j in range(4000):
            if (r * i + g * j) <= n:
                for k in range(4000):
                    if r*i+g*j+b*k == n:
                        count += 1
                    elif r*i+g*j+b*k > n:
                        break
            else:
                break
    else: 
        break

print(count)


### FIXED CODE ###

r,g,b,n = map(int,input().split())

count = 0

for i in range(int(n/r)+1):
    for j in range(int((n-i*r)/g)+1):
        k =  n - i * r - j * g
        if k % b == 0:
            count += 1

print(count)