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

def main():
    import queue
    h,w = map(int,input().split())
    S = [[] for i in range(h)]
    q = queue.Queue()
    cnt = 0
    for i in range(h):
        s = input()
        for j in range(w):
            S[i].append(s[j])
            if s[j]=='#':
                q.put([i,j])
                cnt += 1
    ans = 0
    while cnt<h*w:
        ans += 1
        q_ = queue.Queue()
        while q.qsize()>0:
            b = q.get(0)
            if b[0]>0:
                if S[b[0]-1][b[1]]=='.':
                    cnt += 1
                    S[b[0]-1][b[1]]='#'
                    q_.put([b[0]-1,b[1]])
            if b[0]<h-1:
                if S[b[0]+1][b[1]]=='.':
                    cnt += 1
                    S[b[0]+1][b[1]]='#'
                    q_.put([b[0]+1,b[1]])
            if b[1]>0:
                if S[b[0]][b[1]-1]=='.':
                    cnt+=1
                    S[b[0]][b[1]-1]='#'
                    q_.put([b[0],b[1]-1])
            if b[1]<w-1:
                if S[b[0]][b[1]+1]=='.':
                    cnt += 1
                    S[b[0]][b[1]+1]='#'
                    q_.put([b[0],b[1]+1])
        q = q_
    print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###

from collections import deque
def main():
    h,w = map(int,input().split())
    S = [list(input()) for i in range(h)]
    q = [(i,j) for i,a in enumerate(S) for j,b in enumerate(a) if b=='#']
    q = deque(q)
    ans = 0
    s = h*w
    cnt = len(q)
    nxt = [(0,1),(1,0),(-1,0),(0,-1)]
    while cnt < s:
        ans += 1
        q_ = deque([])
        while q:
            a,b = q.pop()
            for x,y in nxt:
                X,Y = a+x,b+y
                if 0>X or X>h-1 or 0>Y or Y>w-1:
                    continue
                if S[X][Y]=='.':
                    S[X][Y]='#'
                    q_.append((X,Y))
        q = q_
        cnt += len(q_)
    print(ans)

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

n = int(input())
a = input().split()
num = []

for i in a:
    if i not in num:
        num.append(i)
    else:
        print("NO")
        break
else:
    print("YES")

### FIXED CODE ###

n = int(input())
a = input().split()
num = []

a_s = list(set(a))

print("YES" if len(a) == len(a_s) else "NO")
### BUGGY CODE ###

import math

n,k = input().split()
p = input().split()

n = int(n)
k = int(k)
p = [int(s) for s in p]

#print(p)

ex =0
ext = []
for f in range(n):
    xs = list(range(1,p[f]+1))
    #print(n,f, p[f],xs,sum(xs))
    xs = [s*1/p[f] for s in xs]
    #print(sum(xs))
    ext.append(sum(xs))
    #print(ext)
    
for i in range(n-k+1):

    txs = [ext[g] for g in range(i,i+k)]
    if sum(txs) > ex: ex = sum(txs)
print('{:.12f}'.format(ex))


### FIXED CODE ###

import math

n,k = input().split()
p = input().split()

n = int(n)
k = int(k)
#p = [int(s) for s in p]

#print(p)

ex =0
ext = []
ext2 = []
for f in range(n):
    pi = int(p[f])
    xs =(pi+1)/2
    ext.append(xs)

ext2.append(ext[0])
for i in range(1,n):
    ext2.append(ext2[i-1]+ext[i])

ex = ext2[k-1]
for j in range(1,n-k+1):
    ext3 =ext2[j+k-1]-ext2[j-1]
    if ext3 > ex: ex = ext3

print('{:.12f}'.format(ex))
### BUGGY CODE ###

def N(): return int(input())
def NM():return map(int,input().split())
def L():return list(NM())
def LN(n):return [N() for i in range(n)]
def LL(n):return [L() for i in range(n)]
import sys
sys.setrecursionlimit(10**6)
n=N()
p=L()
size=(n+1)**2+1
ans=[0]*size
for i in range(1,n+1):
    for j in range(1,n+1):
        k=i*(n+1)+j
        ans[k]=min(i-1,j-1,n-i,n-j)
c=[1]*size
di=[-1,1,n+1,-n-1]
def f(k):
    for i in di:
        if k+i>=size:
            continue
        if ans[k]+c[k]<ans[k+i]:
            ans[k+i]-=1
            q.add(k+i)
t=0
for i in p:
    y=i%n
    if y==0:
        y=n
    x=(i+n-1)//n
    k=x*(n+1)+y
    c[k]=0
    t+=ans[k]
    q=set([k])
    while q:
        k=q.pop()
        f(k)
print(t)

### FIXED CODE ###

def N(): return int(input())
def NM():return map(int,input().split())
def L():return list(NM())
def LN(n):return [N() for i in range(n)]
def LL(n):return [L() for i in range(n)]
import sys
sys.setrecursionlimit(10**6)
n=N()
p=L()
size=(n+1)**2+1
ans=[0]*size
for i in range(1,n+1):
    for j in range(1,n+1):
        k=i*(n+1)+j
        ans[k]=min(i-1,j-1,n-i,n-j)
c=[1]*size
di=[-1,1,n+1,-n-1]
def f(k,i):
    if k+i>=size:
        return
    if ans[k]+c[k]<ans[k+i]:
        ans[k+i]-=1
        q.append(k+i)
t=0
for i in p:
    y=i%n
    if y==0:
        y=n
    x=(i+n-1)//n
    k=x*(n+1)+y
    c[k]=0
    t+=ans[k]
    q=[k]
    while q:
        k=q.pop()
        f(k,1)
        f(k,-1)
        f(k,n+1)
        f(k,-n-1)
print(t)
### BUGGY CODE ###

N,M=map(int,input().split())
ab=[list(map(int,input().split())) for l in range(N)]
ct=0
money=0
l=[]
for i in range(N):
    l.append(ab[i][0])
while True:
    min_id=l.index(min(l))
    for i in range(ab[min_id][1]):
        money+=l[min_id]
        ct+=1
        if ct==M:
            break
    ab[min_id][0]=1000000
    l[min_id]=100000
    if ct==M:
        break
print(money)

### FIXED CODE ###

N,M=map(int,input().split())
ab=[list(map(int,input().split())) for l in range(N)]
ct=0
ct1=0
ct2=0
money=0
l=[]
id=[]
for i in range(N):
    l.append(ab[i][0])
id=sorted(range(len(l)),key=lambda k: l[k])
l.sort()
while ct<M:
    while ct2<ab[id[ct1]][1]:##
        money+=l[ct1] #l[ct1]
        #print(money,l[ct1])
        ct+=1
        ct2+=1
        if ct==M:
            break
    ct1+=1
    ct2=0
print(money)
### BUGGY CODE ###

KS = input().split()
K,S = int(KS[0]), int(KS[1])
S_count = 0

for x in range(K+1):
  for y in range(K+1):
    for z in range(K+1):
      if x + y + z == S:
        S_count += 1
print(S_count)

### FIXED CODE ###

KS = input().split()
K,S = int(KS[0]), int(KS[1])
S_count = 0

for x in range(K+1):
  for y in range(K+1):
    if S - x - y <= K and S - x - y >= 0:
      S_count += 1
print(S_count)
### BUGGY CODE ###

import sys

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(IN())
mod=1000000007

#+++++

def main():
	#a = int(input())
	#b , c = tin()
	s = list(input())
	while True:
		p=''
		pi=-1
		is_exist_st=False
		#pa(s)
		for i, c in enumerate(s):
			if p == 'S' and c == 'T':
				s[pi] = 'e'
				s[i] = 'e'
				#print(s)
				is_exist_st = True
				p=''
				for bj in range(i):
					if s[i-1-bj]!='e':
						p=s[i-1-bj]
						pi=i-1-bj
						break
				
			elif c == 'e':
				pass
			else:
				p=c
				pi=i
		
		if not is_exist_st:
			break	
	return len(s)-s.count('e')
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

### FIXED CODE ###

import sys

input_methods=['clipboard','file','key']
using_method=1
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(IN())
mod=1000000007

#+++++

def main():
	#a = int(input())
	#b , c = tin()
	s = list(input())[:-1]

	count_s = 0
	delete_num=0
	for c in s:
		if c == 'S':
			count_s+=1
		else: #if c == 'T':
			if count_s == 0:
				pass
			else:
				count_s-=1
				delete_num+=2
	return len(s)-delete_num
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)
### BUGGY CODE ###

n,p=map(int,input().split())
s=input()
count=0
for i in range(n):
    num=0
    for j in range(i,n):
        num=(num*10+int(s[j]))%p
        if num==0:
            count+=1
print(count)

### FIXED CODE ###

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

count=0
if p==2:
    for i in range(n):
        if int(s[i])%2==0:
            count+=i+1
elif p==5:
    for i in range(n):
        if int(s[i])%5==0:
            count+=i+1
else:
    lis=[1]
    for i in range(n-1):
        lis.append((lis[i]*10)%p)
    lis.reverse()
    for i in range(n):
        lis[i]=(int(s[i])*lis[i])%p
    unum=[1]
    for i in range(p-1):
        unum.append(0)
    num=0
    for i in range(n):
        num=(num+lis[n-i-1])%p
        unum[num]+=1
    for i in range(p):
        unumi=unum[i]
        count+=(unumi*(unumi-1))*0.5
print(round(count))
### BUGGY CODE ###

import sys
n=int(input())
xyh=[list(map(int,input().split())) for i in range(n)]
#x = [xyh[i][0] for i in range(n)]
#y = [xyh[i][1] for i in range(n)]
h = [xyh[i][2] for i in range(n)]
ch=max(h)
while ch<=10000000000:
  for cx in range(101):
    for cy in range(101):
      flg=0
      for i in range(n):
        if abs(xyh[i][0]-cx)+abs(xyh[i][1]-cy)>ch and xyh[i][2]!=0:
          flg=1
          break
        if abs(xyh[i][0]-cx)+abs(xyh[i][1]-cy)!=ch-xyh[i][2]:
          flg=1
          break
      if flg==0:
        print(cx,cy,ch)
        sys.exit()
  ch+=1   

### FIXED CODE ###

import sys
n=int(input())
xyh=[list(map(int,input().split())) for i in range(n)]
xyh.sort(key=lambda x:x[2],reverse=True)
if xyh[0][2]==0:
  total=0
  for i in range(n):
    total+=xyh[i][0]
  cx=total//n
  total=0
  for i in range(n):
    total+=xyh[i][1]
  cy=total//n
  ch=abs(xyh[0][0]-cx)+abs(xyh[0][1]-cy)
  print(cx,cy,ch)
  sys.exit()  
for cx in range(101):
  for cy in range(101):
    ch=abs(xyh[0][0]-cx)+abs(xyh[0][1]-cy)+xyh[0][2]
    flg=0
    for i in range(n):
      if xyh[i][2]!=max(0, ch-abs(xyh[i][0]-cx)-abs(xyh[i][1]-cy)):
        flg=1
        break
    if flg==0:
      print(cx,cy,ch)
      sys.exit()
### BUGGY CODE ###

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

arr = [set() for _ in range(W)]
arr[0].add(0)
for y in range(H):
    nextarr = [set() for _ in range(W)]
    Ay = A[y]
    By = B[y]
    dh = H - y - 1
    for x in range(W):
        nextset = nextarr[x]
        d = Ay[x] - By[x]
        dw = W - x - 1
        lim = (dh + dw + 1) * 160
        for n in arr[x]:
            if abs(n+d) <= lim:
                nextset.add(n+d)
            if abs(n-d) <= lim:
                nextset.add(n-d)
        if x >= 1:
            for n in nextarr[x-1]:
                if abs(n+d) <= lim:
                    nextset.add(n+d)
                if abs(n-d) <= lim:
                    nextset.add(n-d)
    arr = nextarr
print(min([abs(d) for d in arr[-1]]))

### FIXED CODE ###

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

arr = [set() for _ in range(W)]
arr[0].add(A[0][0] - B[0][0])
for x in range(1, W):
    s = arr[x]
    d = A[0][x] - B[0][x]
    for n in arr[x-1]:
        s.add(abs(n+d))
        s.add(abs(n-d))

for y in range(1, H):
    nextarr = [set() for _ in range(W)]
    Ay = A[y]
    By = B[y]
    dh = H - y - 1
    for x in range(W):
        nextset = nextarr[x]
        d = Ay[x] - By[x]
        dw = W - x - 1
        lim = (dh + dw + 1) * 160
        #lim = 1280
        if x >= 1:
            arr[x] |= nextarr[x-1]
        for n in arr[x]:
            if abs(n+d) <= lim:
                nextset.add(abs(n+d))
            if abs(n-d) <= lim:
                nextset.add(abs(n-d))
    arr = nextarr
print(min([abs(d) for d in arr[-1]]))
### BUGGY CODE ###

import heapq
def SME(Whole,start,end,L,ANS):
    A = []
    if end > N : end = N
    count = 0
    for i,x in enumerate(Whole[start:end]):
        heapq.heappush(A,[x,i])
    for j in range(start,end):
        a = heapq.heappop(A)
        for i in range(L):
            idx = a[1] + i
            try :
                if ANS[idx] == 0 and idx < end:
                    ANS[idx] = a[0]
                    count += 1
            except IndexError : continue
        if count > K * 0.999  : break
    for i in range(L):
        if ANS[i] == 0 : ANS[i] = min(Whole[:i+1])
    for i in range(L,N):
        if ANS[i] == 0 : ANS[i] = min(Whole[i+1-L:i+1])
    return ANS

[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ANS = [0]*N
start = 0
K = L * int(N ** 0.3 + 2 )
if K > N : K = N
end = K
while (end <= N):
    ANS = SME(A, start, end, L, ANS)
    start = end
    end += K 
for i in ANS[L-1:-1]:print(i, end=" ")
print(ANS[-1])

### FIXED CODE ###

def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])
### BUGGY CODE ###

#D
from collections import deque
n,q=map(int,input().split())
data=[[] for i in range(n+1)]
counter=deque([0 for i in range(n+1)])
for i in range(n-1):
    a,b=map(int,input().split())
    data[a].append(b)
    data[b].append(a)
for i in range(q):
    p,x=map(int,input().split())
    counter[p]+=x
h=deque([1])
while h:
    a=h.popleft()
    for i in range(len(data[a])):
        counter[data[a][i]]+=counter[a]
        h.append(data[a][i])
        data[data[a][i]].remove(a)
counter.popleft()
print(*counter)


### FIXED CODE ###

#D
n,q=map(int,input().split())
data=[[] for i in range(n+1)]
counter=[0]*(n+1)
for i in range(n-1):
    a,b=map(int,input().split())
    data[a].append(b)
    data[b].append(a)
for i in range(q):
    p,x=map(int,input().split())
    counter[p]+=x
h=[1]
done=[0]*(n+1)
while h:
    a=h.pop()
    for l in data[a]:
        if done[l]==0:
            counter[l]+=counter[a]
            h.append(l)
    done[a]=1
print(*counter[1:])
### BUGGY CODE ###

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()
c=Counter(lis)
dp=[[[-1]*(n+1) for i in range(n+1)] for j in range(n+1)]
dp[0][0][0]=0
def dfs(x,y,z):
    if x+y+z>n or (x<0 or y<0 or z<0) or (x>n or y>n or z>n):
        return 0
    elif dp[x][y][z]>=0:
        return dp[x][y][z]
    else:
        dp[x][y][z]=(n+x*dfs(x-1,y,z)+y*dfs(x+1,y-1,z)+z*dfs(x,y+1,z-1))/(x+y+z)
        return (n+x*dfs(x-1,y,z)+y*dfs(x+1,y-1,z)+z*dfs(x,y+1,z-1))/(x+y+z)
print(dfs(c[1],c[2],c[3]))


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
def main():
    n=int(input())
    a=list(map(int,input().split()))
    # 0個の皿がx0枚、1個の皿がx1枚、2個の皿がx2枚、3個の皿がx3枚
    # x0=n-x1-x2-x3
    ca={1:a.count(1),2:a.count(2),3:a.count(3)}
    memo=[[[-1]*(n+2) for _ in range(n+2)] for _ in range(n+2)]
    memo[0][0][0]=0
    for x3 in range(ca[3]+1):
        for x2 in range(ca[2]+ca[3]+1-x3):
            for x1 in range(ca[1]+ca[2]+ca[3]+1-x3-x2):
                if (x1,x2,x3)==(0,0,0):continue
                tmp=0
                if x1>0:tmp+=memo[x1-1][x2][x3]*x1
                if x2>0:tmp+=memo[x1+1][x2-1][x3]*x2
                if x3>0:tmp+=memo[x1][x2+1][x3-1]*x3
                tmp+=n
                tmp/=x1+x2+x3
                memo[x1][x2][x3]=tmp
    print(memo[ca[1]][ca[2]][ca[3]])
if __name__=='__main__':
    main()
### BUGGY CODE ###

import queue
import sys
input = sys.stdin.readline


def toab(s, ab, node):
    toa, tob = False, False
    for k in ab:
        if k not in node:
            continue
        if s[k - 1] is 'A':
            toa = True
            if tob:
                return True
        elif s[k - 1] is 'B':
            tob = True
            if toa:
                return True
    return False


ab = {}
node = {}
N, M = map(int, input().split())
s = input()
for i in range(M):
    a, b = map(int, input().split())
    if a not in ab:
        ab[a] = {}
    ab[a][b] = True
    if b not in ab:
        ab[b] = {}
    ab[b][a] = True
    node[a] = True
    node[b] = True

for i in range(N + 1):
    if i not in node:
        continue
    q = queue.Queue()
    q.put(i)
    while not q.empty():
        j = q.get()
        if j in node and not toab(s, ab[j], node):
            node.pop(j)
            for k in ab[j]:
                if k in node:
                    q.put(k)

if len(node) == 0:
    print('No')
else:
    print('Yes')


### FIXED CODE ###

import queue
import sys
input = sys.stdin.readline


def toab(s, ab, node):
    toa, tob = False, False
    for k in ab:
        if k not in node:
            continue
        if s[k - 1] == 'A':
            toa = True
            if tob:
                return True
        elif s[k - 1] == 'B':
            tob = True
            if toa:
                return True
    return False


ab = {}
node = {}
N, M = map(int, input().split())
s = input()
for i in range(M):
    a, b = map(int, input().split())
    if a not in ab:
        ab[a] = {}
    ab[a][b] = True
    if b not in ab:
        ab[b] = {}
    ab[b][a] = True
    node[a] = True
    node[b] = True

for i in range(N + 1):
    if i not in node:
        continue
    q = queue.Queue()
    q.put(i)
    while not q.empty():
        j = q.get()
        if j in node and not toab(s, ab[j], node):
            node.pop(j)
            for k in ab[j]:
                if k in node:
                    q.put(k)

if not node:
    print('No')
else:
    print('Yes')
### BUGGY CODE ###

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

for _ in range(m):
  max_i = a_list.index(max(a_list))
  a_list[max_i] = a_list[max_i] // 2

print(sum(a_list))

### FIXED CODE ###

import heapq

n, m = map(int, input().split())
a_list = [a*(-1) for a in list(map(int, input().split()))]

heapq.heapify(a_list)
for _ in range(m):
  min_n = heapq.heappop(a_list)
  heapq.heappush(a_list, (min_n//2 if min_n%2 == 0 else min_n//2+1))
print(sum(a_list) * (-1))
### BUGGY CODE ###

import sys
from collections import Counter

read = sys.stdin.read


def sieve_of_eratosthenes(n):
    sieve = [True] * n
    for i in range(3, int(n ** 0.5) + 1, 2):
        if sieve[i]:
            sieve[i * i::2 * i] = [False] * ((n - i * i - 1) // (2 * i) + 1)
    return [2] + [i for i in range(3, n, 2) if sieve[i]]


def prime_factorize(n, p):
    a = []
    for i in p:
        if n % i != 0:
            continue
        while n % i == 0:
            a.append(i)
            n //= i
        if n == 1:
            return a


N, *A = map(int, read().split())
mod = 10 ** 9 + 7

primes = sieve_of_eratosthenes(10 ** 6)
dic = {i: 0 for i in primes}

n = len(primes)
p = [0] * n
for i in A:
    if i == 1:
        continue
    if dic.get(i):
        dic[i] = max(1, dic[i])
        continue

    tmp = Counter(prime_factorize(i, primes))

    for key, value in tmp.items():
        # print(key, value)
        if dic[key] < value:
            dic[key] = value

lcm = 1
for i, j in dic.items():
    if j == 0:
        continue
    lcm *= pow(i, j, mod)
    lcm %= mod

answer = 0
for i in A:
    answer += lcm * pow(i, mod - 2, mod)
    answer %= mod

print(answer)


### FIXED CODE ###

import sys
from collections import Counter

read = sys.stdin.read


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


def sieve_of_eratosthenes(n):
    sieve = [True] * n
    for i in range(3, int(n ** 0.5) + 1, 2):
        if sieve[i]:
            sieve[i * i::2 * i] = [False] * ((n - i * i - 1) // (2 * i) + 1)
    return [2] + [i for i in range(3, n, 2) if sieve[i]]


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


N, *A = map(int, read().split())
mod = 10 ** 9 + 7

primes = sieve_of_eratosthenes(max(A) + 1)
dic = {i: 0 for i in primes}

n = len(primes)
p = [0] * n
for i in A:
    tmp = Counter(prime_factorize(i))
    for key, value in tmp.items():
        #print(key, value)
        if dic[key] < value:
            dic[key] = value

lcm = 1
for i, j in dic.items():
    if j == 0:
        continue
    lcm *= pow(i, j, mod)
    lcm %= mod

answer = 0
for i in A:
    answer += lcm * pow(i, mod - 2, mod)
    answer %= mod

print(answer)
### BUGGY CODE ###

n,t = map(int,input().split())
ab = [list(map(int, input().split())) for i in range(n)]
ab.sort()
dp = [[0 for i in range(t+1)]for j in range(n+1)]
for i in range(n):
    ti,vi = ab[i]
    for j in range(t+1):
        if j + ti <= t:
            dp[i+1][j+ti] = max(dp[i+1][j+ti],dp[i][j]+vi)
        dp[i+1][j] = max(dp[i][j],dp[i+1][j])
ma = 0
for i in range(n):
    ma = max(ma,dp[i][t-1]+ab[i][1])
print(ma)

### FIXED CODE ###

N, W = map(int, input().split())
items = sorted([list(map(int, input().split())) for i in range(N)])

dp = [[0] * (W + 1) for i in range(N + 1)]

# dpテーブルを埋める
for i in range(N):
    wi, vi = items[i]
    for j in range(W + 1):
        if j + wi <= W:
            dp[i + 1][j + wi] = max(dp[i + 1][j + wi], dp[i][j] + vi)
        dp[i + 1][j] = max(dp[i][j], dp[i + 1][j])


ans = 0
# 最後に入れる商品は、残り容量１の時に入れるとしてしまってよい
for i, (wi, vi) in enumerate(items):
    ans = max(ans, dp[i][W - 1] + vi)

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

N, Q = map(int, input().split())
S = str(input())

def main(s):
  ans = 0
  for i in range(len(s)-1):
    if s[i] == 'A' and s[i+1] == 'C':
      ans += 1
  return ans

for _ in range(Q):
  l, r = map(int, input().split())
  print(main(S[l-1:r]))

### FIXED CODE ###

N, Q = map(int, input().split())
S = str(input())
 
#ac = [1 if S[i] == 'A' and S[i+1] == 'C' else 0 for i in range(N-1) ]
a = 0
lst = [0]
for i in range(1, N):
  if S[i-1] == 'A' and S[i] == 'C':
    a += 1
  lst.append(a)
for _ in range(Q):
  l, r = map(int, input().split())
  print(lst[r-1] - lst[l-1])