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

t=int(input())
for _ in range(t):
  n=int(input())
  a=list(map(int,input().split()))
  s=input()
  if "1" not in s:
    print(0)
    continue
  r=s.rfind("1")
  o=[]
  so=set()
  z=[]
  sz=set()
  for i in range(n):
    if s[i]=="0" and i>r:
      for j in z:
        if a[i]^j not in sz:
          z.append(a[i]^j)
          sz.add(a[i]^j)
      if a[i] not in sz:
        z.append(a[i])
        sz.add(a[i])
    elif s[i]=="1":
      for j in o:
        if a[i]^j not in so:
          o.append(a[i]^j)
          so.add(a[i]^j)
      if a[i] not in so:
        o.append(a[i])
        so.add(a[i])
  if sz<=so:print(0)
  else:print(1)

### FIXED CODE ###

for _ in range(int(input())):
  n=int(input())
  a=list(map(int,input().split()))
  s=input()
  b=[]
  ans=0
  for i in range(n-1,-1,-1):
    for j in b:
      a[i]=min(a[i],a[i]^j)
    if a[i]!=0:
      if s[i]=="0":
        b.append(a[i])
      else:
        ans=1
  print(ans)
### BUGGY CODE ###

from bisect import bisect_left
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
AB = [[int(i) for i in input().split()] for _ in range(N)]

AB.sort(key=lambda x: x[1], reverse=True)

s = [i for i in range(1, M + 1)]
ret = 0
for a, b in AB :
    if a > s[-1] :
        continue
    
    a = bisect_left(s, a)
    s.pop(a)
    ret += b
    if not s :
        break
print(ret)


### FIXED CODE ###

from heapq import heappush, heappop

N, M = map(int, input().split())
AB = [[] for _ in range(M+1)]

for _ in range(N) :
    a, b = map(int, input().split())
    if a <= M :
        AB[M-a].append(b)
    
q = []
for a in range(M+1) :
    for b in AB[a] :
        heappush(q, b)
        if len(q) > a + 1 :
            heappop(q)
            
print(sum(q))
### BUGGY CODE ###

def dfs(g, last, vs, first):
    if vs:return min(g[last][v] + dfs(g, v, vs - {v}, first) for v in vs)
    else:return g[last][first]

from sys import stdin
from collections import defaultdict
from math import isinf

readline = stdin.readline

v, e = map(int, readline().split())
g = [[float('inf')] * v for _ in range(v)]
for _ in range(e):
    s, t, d = map(int, readline().split())
    g[s][t] = d

cost = []
vs = set(range(v))

first = 0
for second in range(1, v):
    if isinf(g[first][second]):continue
    cost.append(g[first][second] + dfs(g, second, vs - {first,second}, first))
        
ans = min(cost) if cost else -1
print(-1 if isinf(ans) else ans)

### FIXED CODE ###

# http://www.geocities.jp/m_hiroi/light/pyalgo65.html

def memoize(f):
    table = {}
    def func(*args):
        if not args in table:
            table[args] = f(*args)
        return table[args]
    return func

@memoize
def tsp(p, v):
    if (1 << point_size) - 1 == v:
        return distance_table[p][0]
    else:
        return min(distance_table[p][x] + tsp(x, v | (1 << x)) for x in range(point_size) if not (v & (1 << x)))

from sys import stdin
from collections import defaultdict
from math import isinf

readline = stdin.readline

point_size, e = map(int, readline().split())
distance_table = [[float('inf')] * point_size for _ in range(point_size)]
for _ in range(e):
    s, t, d = map(int, readline().split())
    distance_table[s][t] = d
ans = tsp(0,1)
print(-1 if isinf(ans) else ans)
### BUGGY CODE ###

from itertools import product
N, A = map(int, input().split())
x = list(map(int, input().split()))
x_max = max(max(x), A)

dp = [[[0 for s in range(x_max * (N + 1))] for n in range(N + 1)] for i in range(N + 1)]
dp[0][0][0] = 1

for i, n, s in product(range(1, N + 1), range(N + 1), range(x_max * (N + 1))):
    if s < x[i - 1]:
        dp[i][n][s] = dp[i - 1][n][s]
    elif 0 < n and x[i - 1] <= s:
        dp[i][n][s] = dp[i - 1][n][s] + dp[i - 1][n - 1][s - x[i - 1]]

ans = sum([dp[N][n][n*A] for n in range(1, N + 1)])
print(ans)

### FIXED CODE ###

from itertools import product

N, A = map(int, input().split())
x = [int(xi) for xi in input().split()]
y = [xi - A for xi in x]
X = max(max(x), A)

dp = [[0 for _ in range(2 * N * X + 1)] for _ in range(N + 1)]

dp[0][N * X] = 1
for k, t in product(range(1, N + 1), range(2 * N * X + 1)):
    if k > 0 and (t - y[k - 1] < 0 or t - y[k - 1] > 2 * N * X):
        dp[k][t] = dp[k - 1][t]
    elif k > 0 and t - y[k - 1] <= 2 * N * X:
        dp[k][t] = dp[k - 1][t] + dp[k - 1][t - y[k - 1]]

print(dp[N][N * X] - 1)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
# 
import math
import sys
import itertools

# なんこか入力
n,m = map(int, input().split())


# n行の複数列ある数値を二次元配列へ。x[n][?]
x = [[int(i) for i in input().split()] for i in range(n)] 

x = sorted(x, key=lambda x: x[0])
x = sorted(x, key=lambda x: -x[1])
y = [0]*m
#print(x)


for i in range(n):
    for j in range(x[i][0]-1,m):
        if y[j] == 0:
            y[j] = x[i][1]
            break
#    print(y)

answer=0
for i in range(m):
    answer += y[i]
print(answer)



### FIXED CODE ###

# -*- coding: utf-8 -*-
# 
import math
import sys
import itertools
import heapq
from operator import itemgetter

# なんこか入力
n,m = map(int, input().split())

# n行の複数列ある数値を二次元配列へ。x[n][?]
x = [[int(i) for i in input().split()] for i in range(n)] 

x = sorted(x,key=itemgetter(1),reverse = True)
x = sorted(x,key=itemgetter(0))

work = []
j = 0
answer = 0
for i in range(1,m+1,1):
    while j < n and x[j][0] == i:
        heapq.heappush(work,-x[j][1])
#        print(work)
        j += 1
    if work:
        answer -= heapq.heappop(work)

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

#!/usr/bin/env python3
import sys
from collections import Counter
from collections import defaultdict


def solve(N: int, P: int, S: str):

    if P == 2 or P == 5:
        tot = 0
        for i, c in enumerate(S):
            c = int(c)
            if c % P == 0:
                tot += i+1
        print(tot)
        return

    U = [int(S[i:]) % P for i in range(N)]+[0]
    table = Counter()
    tot = 0
    for i in range(N-1, -1, -1):
        tot += table[U[i]]
        table[U[i]] += 1
    tot += table[0]
    print(tot)

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    P = int(next(tokens))  # type: int
    S = str(next(tokens))  # type: int
    solve(N, P, S)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys


def solve(N: int, P: int, S: str):

    if P == 2 or P == 5:
        tot = 0
        for i, c in enumerate(S):
            c = int(c)
            if c % P == 0:
                tot += i+1
        print(tot)
        return

    U = [0]*(N+1)
    a = 0
    beki = 1
    for i in range(N-1, -1, -1):
        a += beki*int(S[i])
        a %= P
        U[i] = a
        beki = (beki * 10) % P
    table = [0]*P
    tot = 0
    for i in range(N-1, -1, -1):
        tot += table[U[i]]
        table[U[i]] += 1
    tot += table[0]
    print(tot)

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    P = int(next(tokens))  # type: int
    S = str(next(tokens))  # type: int
    solve(N, P, S)


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

def distance(P, p1, p2):
    return min(abs(P[p1][1]-P[p2][1]), abs(P[p1][2]-P[p2][2]))

N = int(input())
P = [[j]+[int(i) for i in input().split(' ')] for j in range(N)]
sortX = sorted(P,key=lambda x:x[1])
sortY = sorted(P,key=lambda x:x[2])
EX = [sorted([sortX[i][0],sortX[i+1][0]]) for i in range(N-1)]
EY = [sorted([sortY[i][0],sortY[i+1][0]]) for i in range(N-1)]
E = EX + EY

C = [0]
NC = [i for i in range(1,N)]
sumDis = 0
while len(NC) > 0:
    minDis = 1000000000
    for c in C:
        relatedE = [e for e in E if c in e]
        for e in relatedE:
            target = e[0] if e[0] != c else e[1]
            if not target in NC:
                continue
            dis = distance(P, c, target) 
            if minDis > dis:
                minDis = dis
                minTarget = target 
                minEdge = e
    NC.remove(minTarget) 
    C.append(minTarget)
    while minEdge in E:
        E.remove(minEdge)
    sumDis += minDis
print(sumDis)

### FIXED CODE ###


import sys
sys.setrecursionlimit(int(2e9))

def distance(P, p1, p2):
    return min(abs(P[p1][1]-P[p2][1]), abs(P[p1][2]-P[p2][2]))
def root(CI, p):
    if CI[p] == p:
        return p
    else:
        CI[p] = root(CI, CI[p])
        return CI[p] 

N = int(input())
P = [[j]+[int(i) for i in input().split(' ')] for j in range(N)]
sortX = sorted(P,key=lambda x:x[1])
sortY = sorted(P,key=lambda x:x[2])
EX = [[sortX[i][0], sortX[i+1][0], distance(P,sortX[i][0],sortX[i+1][0])] for i in range(N-1)]
EY = [[sortY[i][0], sortY[i+1][0], distance(P,sortY[i][0],sortY[i+1][0])] for i in range(N-1)]
E = EX + EY
E = sorted(E, key=lambda x:x[2])
CI = [i for i in range(N)]
disSum = 0
for e in E:
    s,l = min(e[0],e[1]),max(e[0],e[1])
#     if CI[s] != CI[l]:
#         CI = list(map(lambda x:CI[s] if x == CI[l] else x, CI))
#         disSum += e[2]
    if root(CI, s) != root(CI, l):
        CI[root(CI, l)] = root(CI, s)
        disSum += e[2]
print(disSum)
### BUGGY CODE ###

import numpy as np
import bisect
n = int(input())
l = np.array([int(i) for i in input().split()])
l = np.sort(l)

ans = 0
for i in range(1, n - 1):
    m = l[:i]
    for j in range(i + 1, n):
        tmp = l[j] - l[i]
        cnt = bisect.bisect_right(m, tmp)
        ans += i-cnt
print(ans)


### FIXED CODE ###

import bisect
n = int(input())
L = list(map(int, input().split()))
L.sort()

ans = 0
for i in range(n - 2):
    l = L[i]
    for j in range(i + 1, n - 1):
        ll = l + L[j]

        ind = bisect.bisect_left(L, ll)
        ans += ind - j - 1

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

n = int(input())
a = list(map(int, input().split()))
b = []
for i in range(n):
  ai = a[i]
  b.append(ai)
  b.reverse()
print(' '.join(map(str, b)))

### FIXED CODE ###

from collections import deque

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

b = deque()

if n%2 == 0:
  for i in range(n):
    ai = a[i]
    if i%2 == 0:
      b.append(ai)
    else:
      b.appendleft(ai)
else:
  for i in range(n):
    ai = a[i]
    if i%2 == 0:
      b.appendleft(ai)
    else:
      b.append(ai)
print(' '.join(map(str, b)))
### BUGGY CODE ###

N = int(input())
ans = 0
while N >= 1:
    ans += N % 10
    ans = ans % 9
    N = N // 10
if ans == 0:
    print('Yes')
else:
    print('No')


### FIXED CODE ###

N = input()
ans = 0
while N:
    ans += int(N[-1])
    ans = ans % 9
    N = N[:-1]
if ans == 0:
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

INF = 1 << 32


def main(n, k, heights):
    costs = [INF for i in range(n)]
    costs[0] = 0
    for i in range(n):
        for j in range(1, k + 1):
            if i + j >= n:
                break
            costs[i + j] = min(costs[i + j], abs(heights[i] - heights[i + j]) + costs[i])
    return costs[n - 1]


if __name__ == '__main__':
    N, K = map(int, input().split())
    H = list(map(int, input().split()))
    print(main(N, K, H))


### FIXED CODE ###

import numpy as np


def main(n, k, heights):
    heights = np.array(heights, dtype=int)
    costs = np.zeros(n, dtype=int)
    for i in range(1, n):
        start = max(0, i - k)
        costs[i] = np.min(costs[start:i] + np.abs(heights[i] - heights[start:i]))
    return costs[-1]


if __name__ == '__main__':
    N, K = map(int, input().split())
    H = list(map(int, input().split()))
    print(main(N, K, H))
### BUGGY CODE ###

from collections import deque

def clamp(a,b,c):
  return min(max(a,b),c)

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

D = [[-1]*W for _ in range(H)]
dd = [(1,0),(-1,0),(0,1),(0,-1)]
Q = deque()
res = 0

for i in range(H):
  for j in range(W):
    if A[i][j] == "#":
      D[i][j] = 0
      Q.append([i,j,0])
      
while len(Q)>0:
  x,y,n = Q.popleft()
  for dx,dy in dd:
    xx = clamp(x+dx,0,H-1)
    yy = clamp(y+dy,0,W-1)
    if D[xx][yy] == -1:
      D[xx][yy] = n+1
      Q.append([xx,yy,n+1])
      res = n+1
      
print(res)

### FIXED CODE ###

from collections import deque

def clamp(a,b,c):
  return min(max(a,b),c)

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

D = [[-1]*W for _ in range(H)]
dd = [(1,0),(-1,0),(0,1),(0,-1)]
Q = deque()
res = 0

for i in range(H):
  for j in range(W):
    if A[i][j] == "#":
      D[i][j] = 0
      Q.append([i,j,0])
      
while len(Q)>0:
  x,y,n = Q.popleft()
  for dx,dy in dd:
    xx = clamp(x+dx,0,H-1)
    yy = clamp(y+dy,0,W-1)
    if D[xx][yy] == -1:
      D[xx][yy] = n+1
      Q.append([xx,yy,n+1])
      res = n+1
      
print(res)
### BUGGY CODE ###

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

A = 0
for i in range(N-K+1):
  B = 0
  for j in range(K):
    E = 0
    for k in range(P[i+j]):
      E += k + 1
    E /= P[i+j]
    B += E
    if B > A:
      A = B

print(A)

### FIXED CODE ###

N,K = map(int,input().split())
p = list(map(int,input().split()))
E = [(1+i)/2 for i in p]
S = [0]*(N+1)
sum = 0
for i in range(N):
  sum += E[i]
  S[i+1] = sum
ans = 0
i = 0
while N-K-i >= 0:
  A = S[K+i] -S[i]
  ans = max(ans,A)
  i += 1
print(ans)
### BUGGY CODE ###

def solve(way, height, n):
  ans = [i for i in range(n)]
  for a,b in way:
    if height[a-1] == height[b-1]:
      remove_1 = a-1
      remove_2 = b-1
      if remove_1 in ans:
        ans.remove(a-1)
      if remove_2 in ans:
        ans.remove(b-1)
    else:
      remove_idx = a if height[a-1] < height[b-1] else b
      remove_idx = remove_idx -1
      if remove_idx in ans:
        ans.remove(remove_idx)
  return len(ans)


if __name__ == "__main__":
  n,m = map(int, input().split())
  height = [int(i) for i in input().split()]
  way = [tuple(map(int, input().split())) for i in range(m)]
  print(solve(way, height, n))


### FIXED CODE ###

def solve(way, height, n):
  ss = []
  for a,b in way:
    if height[a-1] <= height[b-1]:
      ss.append(a)
    if height[a-1] >= height[b-1]:
      ss.append(b)
  return n - len(set(ss))


if __name__ == "__main__":
  n,m = map(int, input().split())
  height = [int(i) for i in input().split()]
  way = [tuple(map(int, input().split())) for i in range(m)]
  print(solve(way, height, n))
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
ans=0
for i in range(N-1):
    for j in range(i+1,N):
        ans+=(A[i]*A[j])%(10**9+7)
ans=ans%(10**9+7)
print(ans)


### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
ans=0
s=sum(A)
for i in range(N-1):
    s-=A[i]
    ans+=(A[i]*(s))%(10**9+7)
print(ans%(10**9+7))
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
dp = [[-1]*N for _ in range(N)]
for i in range(N):
    dp[i][i] = 0


def main(l, r):
    if dp[l][r] != -1:
        return dp[l][r]
    ret = 10**15
    for i in range(l, r):
        ret = min(ret, main(l, i)+main(i+1, r))
    ret += sum(A[l:r+1])
    dp[l][r] = ret
    return ret


print(main(0, N-1))

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
dp = [[-1]*N for _ in range(N)]
for i in range(N):
    dp[i][i] = 0


def main(l, r):
    if dp[l][r] != -1:
        return dp[l][r]
    ret = 10**15
    for i in range(l, r):
        ret = min(ret, main(l, i)+main(i+1, r))
    ret += sum(A[l:r+1])
    dp[l][r] = ret
    return ret


print(main(0, N-1))
### BUGGY CODE ###

#
N=int(input())
S=[]
for i in range(N):
    S.append(input())
ans=[]

#
while len(S):
    if len(S)==1:
        x = [S.pop(-1), 1]
        ans.append(x)
        break
    x = [S.pop(-1), 1]
    for i in S[:]:
        if x[0] == i:
            S.remove(i)
            x[1]+=1
    ans.append(x)
ans.sort()
ans.sort(key=lambda x:x[1],reverse=True)

for i in range(len(ans)):
    t=ans[0][1]
    if ans[i][1]==t:
        print(ans[i][0])


### FIXED CODE ###

#
N=int(input())
S={}
for i in range(N):
    x=input()
    if x in S:
        S[x]+=1
    else:
        S[x]=1
t=max(S.values())
ans=[k for (k,v) in S.items() if v==t]
ans.sort()

for i in ans:
    print(i)
""""
#
while len(S):
    if len(S)==1:
        x = [S.pop(), 1]
        ans.append(x)
        break
    x = [S.pop(), 1]
    for i in S[:]:
        if x[0] == i:
            S.remove(i)
            x[1]+=1
    ans.append(x)
ans.sort()
ans.sort(key=lambda x:x[1],reverse=True)

for i in range(len(ans)):
    t=ans[0][1]
    if ans[i][1]==t:
        print(ans[i][0])



import queue

q=queue.Queue()
for i in S:
    q.put(i)

while not q.empty():
    x = [q.get(), 1]
    if len(ans)==0:
        ans.append(x)
        continue
    t=0
    for i in range(len(ans)):
        if x[0] == ans[i][0]:
            ans[i][1]+=1
            t+=1
            break
    if t==0:
        ans.append(x)
ans.sort()
ans.sort(key=lambda x:x[1],reverse=True)

for i in range(len(ans)):
    t=ans[0][1]
    if ans[i][1]==t:
        print(ans[i][0])

"""
### BUGGY CODE ###

N, M, L = map(int, input().split())
INF = float('inf')

dist = [[INF] * N for _ in range(N)]
fuel = [[INF] * N for _ in range(N)]

for i in range(N):
    dist[i][i] = 0
    fuel[i][i] = 0

for _ in range(M):
    fr, to, cost = map(int, input().split())
    if cost > L:
        continue
    fr -= 1
    to -= 1
    dist[fr][to] = cost
    dist[to][fr] = cost

for k in range(N):
    for i in range(N):
        for j in range(N):
            d = dist[i][k] + dist[k][j]
            dist[i][j] = min(dist[i][j], d)
            if d <= L:
                fuel[i][j] = 1

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

Q = int(input())
ans = []
for _ in range(Q):
    start, end = map(int, input().split())
    start -= 1
    end -= 1

    ans.append(fuel[start][end] - 1 if fuel[start][end] != INF else -1)

print(*ans, sep='\n')


### FIXED CODE ###

import sys
input = sys.stdin.readline
INF = float('inf')

N, M, L = map(int, input().split())
ABC = [tuple(map(int, input().split())) for _ in range(M)]
Q = int(input())
ST = [tuple(map(int, input().split())) for _ in range(Q)]

dist = [[INF] * N for _ in range(N)]
fuel = [[INF] * N for _ in range(N)]

for i in range(N):
    dist[i][i] = 0
    fuel[i][i] = 0

for fr, to, cost in ABC:
    if cost > L:
        continue
    fr -= 1
    to -= 1
    dist[fr][to] = cost
    dist[to][fr] = cost

for k in range(N):
    for i in range(N):
        for j in range(N):
            d = dist[i][k] + dist[k][j]
            if dist[i][j] > d:
                dist[i][j] = d
            if d <= L:
                fuel[i][j] = 1

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

for start, end in ST:
    print(fuel[start - 1][end - 1] - 1 if fuel[start - 1][end - 1] != INF else -1)
### BUGGY CODE ###

import sys

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

input = sys.stdin.readline
n = int(input())
a_list = list(map(int, input().split()))
ans = 1
for i in range(n):
    if i == 0:
        gcd_r = 0
        r_list = a_list[i+1:]
        for r in r_list:
            if gcd_r == 0:
                gcd_r = r
            else:
                gcd_r = gcd(gcd_r, r)
        m = gcd_r
    elif i == n-1:
        gcd_l = 0
        l_list = a_list[:i]
        for l in l_list:
            if gcd_l == 0:
                gcd_l = l
            else:
                gcd_l = gcd(gcd_l, l)
        m = gcd_l
    else:
        gcd_l, gcd_r = 0, 0
        l_list = a_list[:i]
        r_list = a_list[i+1:]
        for l in l_list:
            if gcd_l == 0:
                gcd_l = l
            else:
                gcd_l = gcd(gcd_l, l)
        for r in r_list:
            if gcd_r == 0:
                gcd_r = r
            else:
                gcd_r = gcd(gcd_r, r)
        m = gcd(gcd_l, gcd_r)
    ans = max(ans, m)
print(ans)


### FIXED CODE ###

import sys

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

input = sys.stdin.readline
n = int(input())
a_list = list(map(int, input().split()))
l_list = [0]
r_list = [0]
l_gcd, r_gcd = 0, 0
for i in range(n-1):
    l_gcd = gcd(l_gcd, a_list[i])
    l_list.append(l_gcd)
    r_gcd = gcd(r_gcd, a_list[-i-1])
    r_list.append(r_gcd)
ans = 1
for i in range(n):
    ans = max(ans, gcd(l_list[i], r_list[-i-1]))
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
INF = float("inf")

MOD = 1000000007  # type: int


def GCD(a, b):
    if a == 0:
        return b
    else:
        return GCD(b % a, a)


# def power(x, y):
#     if y == 0:
#         return 1
#     elif y == 1:
#         return x % MOD
#     elif y % 2 == 0:
#         return power(x, y//2)**2 % MOD
#     else:
#         return power(x, y//2)**2 * x % MOD


# def div(a, b):
#     return (a * power(b, MOD-2)) % MOD


def LCM(a, b):
    return a*b//GCD(a, b)
    # return div(power(a, b), GCD(a, b))


def extGCD(a, b):
    """
    拡張ユークリッド互除法により
    ax + by = gcd(a, b)となるようなx, yを求める
    """
    # print(a, b)
    if a == 0:
        return 0, 1
    s, t = extGCD(b % a, a)
    return t-(b//a)*s, s


def modinv(a, m):
    x, y = extGCD(a, m)
    return x % m


def solve(N: int, A: "List[int]"):

    # 最小公倍数
    lcm = 1
    for a in A:
        lcm = LCM(lcm, a)
    ma = [modinv(a, MOD) for a in A]

    tot = 0
    for a in ma:
        tot += lcm * a
        tot %= MOD
    print(tot)

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
from collections import Counter
import math
MOD = 1000000007  # type: int


def factorial(n):
    prime_count = Counter()

    for i in range(2, int(math.sqrt(n)) + 2):
        while n % i == 0:
            n /= i
            prime_count[i] += 1
    if n > 1:
        prime_count[int(n)] += 1

    return prime_count


def power(x, y):
    if y == 0:
        return 1
    elif y == 1:
        return x % MOD
    elif y % 2 == 0:
        return power(x, y//2)**2 % MOD
    else:
        return power(x, y//2)**2 * x % MOD


def div(a, b):
    return (a * power(b, MOD-2)) % MOD


def solve(N: int, A: "List[int]"):

    lcm = Counter()
    for a in A:
        c = factorial(a)
        for k in c:
            lcm[k] = max(c[k], lcm[k])
    # print(lcm)

    LCM = 1
    for k, v in lcm.items():
        LCM *= power(k, v)
        LCM %= MOD
    # print(LCM)

    tot = 0
    for a in A:
        tot += div(LCM, a)
    print(tot % MOD)

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)


if __name__ == '__main__':
    main()