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

import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))

#################

import numpy as np

def F2_GaussJordan(A, is_extended = False):
    rank = 0
    for col in range(len(A[0])):
        if (is_extended and col == len(A[0])-1):
            break
        pivot = -1
        for row in range(rank,len(A)):
            if A[row][col]:
                pivot = row
                break
        if pivot == -1: 
            continue
        A[[pivot,rank]] = A[[rank,pivot]]
        for row in range(len(A)):
            if (row != rank and A[row][col]):
                A[row] ^= A[rank]
        rank += 1
    return A

N = I()
A = III()

xor = 0
for i in range(N):
    xor ^= A[i]

use_digit = []
ans = 0
for j in range(60)[::-1]:
    if xor>>j & 1:
        ans += 2**j
    else:
        use_digit.append(j)

a = np.zeros((N,len(use_digit)), dtype=bool)
k = 0
for k,j in enumerate(use_digit):
    for i in range(N):
        if A[i]>>j & 1:
            a[i][k] = 1
        else:
            a[i][k] = 0

g = F2_GaussJordan(a,False)

s = np.zeros(len(use_digit),dtype=bool)
row = 0
for j in range(len(use_digit)):
    for i in range(row,N):
        if g[i][j]==1:
            s ^= g[i]
            row = i+1
            break

for j,k in enumerate(s):
    ans += k*2**(use_digit[j]+1)

print(ans)

### FIXED CODE ###

import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))

#################

N = I()
A = III()

xor = 0
for i in range(N):
    xor ^= A[i]

for i in range(N):
    A[i] &= ~xor

max_digit = len(format(max(A), 'b'))
rank = 0
for col in range(max_digit)[::-1]:
    pivot = -1
    for row in range(rank,N):
        if A[row]>>col & 1:
            pivot = row
            break
    if pivot == -1: 
        continue
    A[pivot],A[rank] = A[rank],A[pivot]
    for row in range(rank+1,N):
        if A[row]>>col & 1:
            A[row] ^= A[rank]
    rank += 1

val = 0
for i in range(N):
    val = max(val,val^A[i])

print(2*val + xor)
### BUGGY CODE ###

A, B, C, D, E, F = map(int, input().split())

sugar_water = -1
sugar = -1
concentration = -1

A = 100*A
B = 100*B
max_sugar = (F//100) * E

for a in range(0,F+1,A):
    for b in range(0,F-a+1,B):
        for c in range(0,max_sugar + 1,C):
            for d in range(0,max_sugar-c+1,D):
                tmp_sugar_water = a + b + c + d
                if tmp_sugar_water == 0:
                    continue
                tmp_concentration = 100 * (c + d) / (tmp_sugar_water)
                if tmp_sugar_water <= F and tmp_concentration <= (100 * E) / (100 + E):
                    if concentration < tmp_concentration:
                        concentration = tmp_concentration
                        sugar_water = tmp_sugar_water
                        sugar = c + d

print(sugar_water,sugar)

### FIXED CODE ###

A, B, C, D, E, F = map(int, input().split())

sugar_water = -1
sugar = -1
concentration = -1

for i in range(F//(A*100)+1):
    for j in range((F-A*100*i)//(B*100)+1):
        for k in range((F-A*i*100-B*100*j)//C+1):
            for l in range((F-A*i*100-B*100*j-C*k)//D+1):
                x = i * A + j * B
                y = k * C + l * D
                if x == 0:
                    continue
                if x * E >= y and concentration < (100 * y)/(x*100+y):
                    sugar_water = 100 * x + y
                    sugar = y
                    concentration = (100 * y)/(x*100+y)

print(sugar_water,sugar)
### BUGGY CODE ###

import numpy as np
n = int(input())
aa = list(map(int, input().split()))
aa.sort()

oks = np.ones(len(aa))
for i in range(n):
    oks[i+1:] = [oks[j]*int(not aa[j]%aa[i] == 0)  for j in range(i+1,n)]
    if i < n-1:
        if aa[i+1] == aa[i]:
            oks[i] = 0
print(int(oks.sum()))

### FIXED CODE ###

import numpy as np
from collections import Counter
n = int(input())
aa = list(map(int, input().split()))
ngs = np.zeros((10**6)+1, dtype=int)

for a in set(aa):
    ngs[2*a::a] = 1
    
dic = Counter(aa)
times = np.array(list(dic.keys()))[np.array(list(dic.values())) > 1]

for i in times:
    ngs[i] = 1
cnt = 0
for a in aa:
    cnt += 1-ngs[a]
print((cnt))
### BUGGY CODE ###

x,y=map(int,input().split())
if(x==y):print(-1)
else:
  i=1
  while(1):
    if((x*i)%y!=0):
      print(x*i)
      break
    i+=1


### FIXED CODE ###

x,y=map(int,input().split())
if(x%y==0):print(-1)
else:
  i=y
  while(1):
    if((x*i)%y!=0):
      print(x*i)
      break
    i+=1
### BUGGY CODE ###

import sys
n = int(input())
a = list(map(int,input().split()))
cnt = 0
for i in range(n):
  for j in range((i + 1),n):
    if(a[i] == a[j]):
      print("NO")
      sys.exit()
print("YES")

### FIXED CODE ###

import sys
n = int(input())
a = list(map(int,input().split()))
if(len(a) != len(set(a))):
	print("NO")
else:
  	print("YES")
### BUGGY CODE ###

x,y,z,k = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = list(map(int,input().split()))

ab = []
for i in range(x):
    for j in range(y):
        ab.append(a[i] + b[j])
ab.sort(reverse = True)

abc = []
for i in range(min(k,len(ab))):
    for j in range(z):
        abc.append(ab[i] + c[j])

abc.sort(reverse = True)

for i in range(k):
    print(abc[i])

### FIXED CODE ###

x,y,z,k = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = list(map(int,input().split()))

ab = []
for i in range(x):
    for j in range(y):
        ab.append(a[i] + b[j])
ab.sort(reverse = True)

abc = []
for i in range(min(k,len(ab))):
    for j in range(z):
        abc.append(ab[i] + c[j])

abc.sort(reverse = True)

for i in range(k):
    print(abc[i])
### BUGGY CODE ###

N,K=map(int,input().split())
Array=[]
for n in range(0,N):
    a,b=map(int,input().split())
    for n in range(0,b):
        Array.append(a)
    Array.sort()
print(Array[K-1])


### FIXED CODE ###

N,K=map(int,input().split())
Array={}
for n in range(0,N):
    a,b=map(int,input().split())
    if a in Array:
        Array[a]+=b
    else:
        Array[a]=b
numbers=sorted(list(Array.keys()))
n=0
k=0
while True:
    k+=Array[numbers[n]]
    if k>=K:
        break
    n+=1
print(numbers[n])
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
sum_num=sum(a)
mylist=[0]*(10**5)
for i in range(1,10**5+1):
    mylist[i-1]=a.count(i)
q=int(input())
for i in range(q):
    b,c=map(int,input().split())
    sum_num+=(c-b)*mylist[b-1]
    print(sum_num)
    mylist[c-1]+=mylist[b-1]
    mylist[b-1]=0

### FIXED CODE ###

from collections import Counter
n=int(input())
a=list(map(int,input().split()))
sum_num=sum(a)
cnt=Counter(a)
q=int(input())
for i in range(q):
    b,c=map(int,input().split())
    sum_num+=(c-b)*cnt[b]
    print(sum_num)
    cnt[c]+=cnt[b]
    cnt[b]=0
### BUGGY CODE ###

n = int(input())
s = input()
from itertools import combinations as cmb
counter = 0
for i, j, k in cmb(list(range(n)), 3):
  #print(i, j, k, s[i], s[j], s[k])
  if j - i != k - j and s[i] != s[j] and s[i] != s[k] and s[j] != s[k]:
    counter += 1
    #print("OK")
print(counter)

### FIXED CODE ###

n = int(input())
s = input()

r_total = s.count("R")
g_total = s.count("G")
b_total = s.count("B")

r_c = []
g_c = []
b_c = []

for moji in s:
  if moji == "R":
    r_total -= 1
  if moji == "G":
    g_total -= 1
  if moji == "B":
    b_total -= 1
  r_c.append(r_total)
  g_c.append(g_total)
  b_c.append(b_total)

color_dic = {"R": r_c, "G": g_c, "B": b_c}
#print(color_dic)
  
from itertools import combinations as cmb
counter = 0
RGB = set(["R", "G", "B"])
for i, j in cmb(list(range(n)), 2):
  #print(i, j, s[i], s[j])
  if s[i] != s[j]:
    rest_color = list(RGB - set([s[i], s[j]]))[0]
    #print(rest_color)
    counter += color_dic[rest_color][j]
    try:
      if s[2 * j - i] == rest_color:
        counter -= 1
    except IndexError:
      pass
print(counter)
### BUGGY CODE ###

N, M, Q = map(int, input().split())
train = [[0]*(N+1) for _ in range(N+1)]

for i in range(M):
  a, b = map(int, input().split())
  train[a][b] += 1
  
for i in range(1, N+1):
  for j in range(1, N+1):
    train[i][j] += train[i][j-1]


for i in range(Q):
  ans = 0
  l, r = map(int, input().split())
  for j in range(l, r+1):
    ans += train[j][r]-train[j][l-1]
  print(ans)

### FIXED CODE ###

N, M, Q = map(int, input().split())
train = [[0]*(N+1) for _ in range(N+1)]

for i in range(M):
  a, b = map(int, input().split())
  train[a][b] += 1
  
for i in range(1, N+1):
  for j in range(1, N+1):
    train[i][j] += train[i][j-1]


for i in range(Q):
  ans = 0
  l, r = map(int, input().split())
  for j in range(l, r+1):
    ans += train[j][r]-train[j][l-1]
  print(ans)
### BUGGY CODE ###

n = int(input())
s = input()

import collections
dp = collections.defaultdict(int)
for i in range(n-1, -1, -1):
    for j in range(i+1, n):
        if s[i] == s[j]:
            dp[i,j] = dp[i+1, j+1] + (j - i > dp[i+1, j+1])
try:
    print(max(dp.values()))
except:
    print(0)


### FIXED CODE ###

n = int(input())
s = input()

def check(length):
    d = set()
    for i in range(n - 2 * length + 1):
        d.add(s[i:i + length])
        if s[i + length:i + 2 * length] in d:
            return True
    return False
 
 
lo = 0
hi = n // 2 + 1
while lo + 1 < hi:
    mid = (lo + hi) // 2
    if check(mid):
        lo = mid
    else:
        hi = mid
if check(hi):
	print(hi)
else:
  	print(lo)
### BUGGY CODE ###

n,k = map(int, input().split())
p = [int(e) for e in input().split()]

max = 0
for i in range(n-k+1):
  s = sum(p[i:(i+k)])
  if max < s:
    max = s
    
print((max+k)/2.0)


### FIXED CODE ###

n,k = map(int, input().split())
p = [int(e) for e in input().split()]
s = sum(p[0:k])
max = s
for i in range(n-k):
  s = s - p[i] + p[i+k]
  if max < s:
    max = s
    
ex = (max+k)/2.0
print(ex)
### BUGGY CODE ###

a, b, x = tuple(int(x) for x in input().split())

y = -1
for i in range(a, b + 1):
    if i % x == 0:
        y = i
        break

if y == -1:
    ans = 0
else:
    ans = (b - y) // x + 1

print(ans)


### FIXED CODE ###

a, b, x = tuple(int(x) for x in input().split())

if a == 0:
    y = 0
else:
    y = x * ((a - 1) // x + 1)


if y == -1:
    ans = 0
else:
    ans = (b - y) // x + 1

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

n,m=map(int,input().split())
s=[[]for i in range(n+1)]
t=[1]*(n+1)
p=0
for i in range(m):
    a,b=map(int,input().split())
    if i==0:
        k=[a,b]
        t[a],t[b]=0,0
    else:
        if a==k[0] and t[b]==1:
            k=[b]+k
            t[b]=0
        elif b==k[0] and t[a]==1:
            k=[a]+k
            t[a]=0
        elif a==k[-1] and t[b]==1:
            k.append(b)
            t[b]=0
        elif b==k[-1] and t[a]==1:
            k.append(a)
            t[a]=0
        else:
            s[a].append(b)
            s[b].append(a)
p=len(k)
while p!=n:
    c=0
    for i in s[k[-1]]:
        if t[i]:
            t[i]=0
            k.append(i)
            p+=1
            break
    else:
        c+=1
    for i in s[k[0]]:
        if t[i]:
            t[i]=0
            k=[i]+k
            p+=1
            break
    else:
        c+=1
        if c==2:
            break
print(p)
print(*k)

### FIXED CODE ###

n,m=map(int,input().split())
s=[[]for i in range(n+1)]
t=[1]*(n+1)
for i in range(m):
    a,b=map(int,input().split())
    s[a].append(b)
    s[b].append(a)
a,b=[],[]
p=1
t[1]=0
while 1:
    for i in s[p]:
        if t[i]:
            t[i]=0
            p=i
            a.append(i)
            break
    else:
        break
p=1
while 1:
    for i in s[p]:
        if t[i]:
            t[i]=0
            p=i
            b.append(i)
            break
    else:
        break
print(1+len(a)+len(b))
t=a[::-1]+[1]+b
print(*t)
### BUGGY CODE ###


N = int(input())

D = [int(a) for a in input().split() ]

if D[0] != 0 or D.count(0) !=1:
    print("0")
    exit()

m = max(D)

#calc
result = 1
x = D.count(1)
for i in range(2,m+1):
    y = D.count(i)
    if y!= 0:
        result = result * pow(x,y)
        x = y
print(result%998244353)





### FIXED CODE ###

import collections
N = int(input())

D = [int(a) for a in input().split() ]

counted = collections.Counter(D)

if D[0] != 0 or counted[0] !=1:
    print("0")
    exit()

#calc
result = 1
x = counted[1]
for i in range(2,N+1):
    y = counted[i]
    result = result * pow(x,y) %998244353
    x = y
print(result)
### BUGGY CODE ###

n = int(input())
s = input()
count = 0
for i in range(1,n-1):
    for j in range((i+1),n):
        for k in range((j+1),n+1):
            if not j-i == k-j:
                if i<j<k:
                    if not s[i-1] == s[j-1] and not \
                    s[i-1] == s[k-1] and not s[j-1] == s[k-1]:
                        count +=1
print(count)

### FIXED CODE ###

n = int(input())
s = input()
all = s.count("R")*s.count("G")*s.count("B")
for x in range(n-1):
    for y in range(1,(n-1-x)//2+1):
        if s[x] != s[x+y] and s[x]!= s[x+2*y]\
        and s[x+y]!=s[x+2*y]:
            all -=1
print(all)
### BUGGY CODE ###

N = int(input())
ls = []
for i in range(N):
  x,y,h = map(int, input().split())
  ls += [(h,x,y)]


ans = []
for i in range(101):
  for j in range(101):
    ans += [(i,j)]
log = []
for a in ans:
  i, j = a
  pH = -1
  for l in ls:
    h, x, y = l
    if h>0:
      H = h+abs(x-i)+abs(y-j)
      if pH==-1:
        pH = H
      elif not H==pH:
        break
  else:
    x, y = a
    log += [(x,y,H)]
if len(log)>1:
  while True:
    u = 1
print(*log[0])

### FIXED CODE ###

N = int(input())
ls = []
for i in range(N):
  x,y,h = map(int, input().split())
  ls += [(x,y,h)]
ls.sort(key=lambda x:x[2])
px, py, ph = ls[-1]

ans = []
flag = False
for i in range(101):
  for j in range(101):
    H = ph+abs(px-i)+abs(py-j)
    for l in ls:
      x, y, h = l
      u = max(H - abs(x-i) - abs(y-j), 0)
      if not u==h:
        break
    else:
      ans = (i,j,H)
      flag = True
      break
  if flag:
    break
print(*ans)
### BUGGY CODE ###

n = int(input())
arr = [int(x) for x in input().split()]
Max = 3005

dp = [[0 for i in range(Max)] for i in range(Max)]

for l in range(n-1,-1,-1):
    for r in range(l, n):
        if l == r:
            dp[l][r] = arr[l]
        else:
            dp[l][r] = max(arr[l] - dp[l+1][r], arr[r] - dp[l][r-1])

print(dp[0][n-1])

### FIXED CODE ###

def deque(n, arr):
    dp = [[0] * n for _ in range(n)]
    for i in range(n):
        dp[i][i] = arr[i]

    for l in range(n-2, -1, -1):
        for r in range(l+1, n):
            L = arr[l] - dp[l+1][r]
            R = arr[r] - dp[l][r-1]
            dp[l][r] = L if L > R else R
    return dp[0][n-1]

n = int(input())
arr = [int(x) for x in input().split()]
print(deque(n, arr))
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
m = (n * (n + 1) // 2) // 2 + 1


class BIT1():
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (self.n + 1)
        self.data = [0] * (self.n + 1)

    def add(self, idx, x):
        # add x to idx-th element
        # idx: 1-indexed
        self.data[idx] += x
        while idx <= self.n:
            self.bit[idx] += x
            idx += (idx & (-idx))

    def sum(self, idx):
        # get sum of [1, idx]
        # idx: 1-indexed
        s = 0
        while idx:
            s += self.bit[idx]
            idx -= (idx & (-idx))
        return s


def check(x):
    # MofM が x以下である
    # x以下の要素が (n*(n+1)//2)//2 + 1 個以上ある

    s = 0
    c = [0] * (n + 1)
    for i in range(n):
        c[i + 1] = c[i]
        if a[i] <= x:
            c[i + 1] += 1
    d = [2 * c[i] - i + n + 1 for i in range(n + 1)]
    d_max = max(d)
    bit = BIT1(d_max)

    cnt = 0
    for i in range(n + 1):
        cnt += bit.sum(d[i] - 1)
        bit.add(d[i], 1)
    return cnt >= m


lb = 0  # False
ub = max(a) + 1  # True
while ub - lb > 1:
    mid = (ub + lb) // 2
    if check(mid):
        ub = mid
    else:
        lb = mid

print(ub)


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
m = (n * (n + 1) // 2) // 2 + 1


class BIT1():
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (self.n + 1)
        self.data = [0] * (self.n + 1)

    def add(self, idx, x):
        # add x to idx-th element
        # idx: 1-indexed
        self.data[idx] += x
        while idx <= self.n:
            self.bit[idx] += x
            idx += (idx & (-idx))

    def sum(self, idx):
        # get sum of [1, idx]
        # idx: 1-indexed
        s = 0
        while idx:
            s += self.bit[idx]
            idx -= (idx & (-idx))
        return s


def check(x):
    # MofM が x以下である
    # x以下の要素が (n*(n+1)//2)//2 + 1 個以上ある

    s = 0
    c = [0] * (n + 1)
    for i in range(n):
        c[i + 1] = c[i]
        if a[i] <= x:
            c[i + 1] += 1
    d = [2 * c[i] - i + n + 1 for i in range(n + 1)]
    d_max = max(d)
    bit = BIT1(d_max)

    cnt = 0
    for i in range(n + 1):
        cnt += bit.sum(d[i] - 1)
        bit.add(d[i], 1)
    return cnt >= m


lb = 0  # False
ub = max(a) + 1  # True
while ub - lb > 1:
    mid = (ub + lb) // 2
    if check(mid):
        ub = mid
    else:
        lb = mid

print(ub)
### BUGGY CODE ###

#!/usr/bin python3
# -*- coding: utf-8 -*-

import sys
input = sys.stdin.readline

def main():
    A, B, N = map(int, input().split())
    N = min(B-1, N)
    ret = 0
    for x in range(N+1):
        ret = max(ret, (x * A)//B - A * (x//B))

    print(ret)



if __name__ == '__main__':
    main()

### FIXED CODE ###

#!/usr/bin python3
# -*- coding: utf-8 -*-

import sys
input = sys.stdin.readline

def main():
    A, B, N = map(int, input().split())
    N = min(B-1, N)
    ret = (N * A)//B - A * (N//B)
    print(ret)



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

N = int(input())

ans = 1
for i in range(1, N+1):
    ans *= i

print(ans%(10**9+7))


### FIXED CODE ###

from math import factorial

N = int(input())

print(factorial(N)%(10**9+7))
### BUGGY CODE ###

import queue

def penetrate(x, y, count):
    global max_idx
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if 0 <= nx < h and 0 <= ny < w and A[nx][ny] == "." and d[nx][ny] == -1:
            d[nx][ny] = count + 1
            q.put((nx, ny, d[nx][ny]))
            max_idx = max(max_idx, d[nx][ny])


h, w = map(int, input().split())
d = [[-1] * w for _ in range(h)]

A = [[] for i in range(h)]
q = queue.Queue()

for i in range(h):
    A[i] = list(input())
    for j in range(w):
        if A[i][j] == "#":
            d[i][j] = 0
            q.put((i, j, d[i][j]))

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
max_idx = 0

while q.empty() == False:
    idx = q.get()
    penetrate(idx[0], idx[1], idx[2])

print(max_idx)


### FIXED CODE ###

from collections import deque

def penetrate(x, y, count):
    global max_idx
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if 0 <= nx < h and 0 <= ny < w and A[nx][ny] == "." and d[nx][ny] == -1:
            d[nx][ny] = count + 1
            q.append((nx, ny, d[nx][ny]))
            max_idx = max(max_idx, d[nx][ny])


h, w = map(int, input().split())
d = [[-1] * w for _ in range(h)]

A = [[] for i in range(h)]
q = deque()

for i in range(h):
    A[i] = list(input())
    for j in range(w):
        if A[i][j] == "#":
            d[i][j] = 0
            q.append((i, j, d[i][j]))

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
max_idx = 0

while len(q) > 0:
    idx = q.popleft()
    penetrate(idx[0], idx[1], idx[2])

print(max_idx)
### BUGGY CODE ###

from collections import Counter

N = int(input())
a_list = list(map(int, input().split()))
Q = int(input())

a = Counter(a_list)
for i in range(Q):
    b, c = map(int, input().split())
    a[c] += a[b]
    a[b] = 0
    print(sum([x*y for x, y in a.items()]))
    #print(sum(a.elements()))

### FIXED CODE ###

from collections import Counter

N = int(input())
a = Counter(map(int, input().split()))
Q = int(input())

sum_a = sum(a.elements())

for i in range(Q):
    b, c = map(int, input().split())
    a[c] += a[b]
    sum_a += (c-b) * a[b]
    a[b] = 0
    print(sum_a)
### BUGGY CODE ###

import itertools
n=int(input())
s=input()
k=list(set(s))

d = {i: s.count(i) for i in k}

counta=0
for i in k:
    counta+=s.count(i)



for i in range(2,len(k)+1):
    li=list(itertools.combinations(k,i))    
    for h in li:
        z="".join(h)
        q=d[z[0:(len(h)-1)]]*d[z[-1]]
            
        d[z]=q
        counta+=q
    
print(counta%(10**9+7))

### FIXED CODE ###

n=int(input())
s=input()
k=list(set(s))
d = {i: s.count(i) for i in k}
counta=0

for i in k:
    counta=counta*d[i]+d[i]+counta


print(counta%(10**9+7))
### BUGGY CODE ###

from collections import Counter

def extended_euclid(a, b):
    x1, y1, m = 1, 0, a
    x2, y2, n = 0, 1, b
    while m % n != 0:
        q, r = divmod(m, n)
        x1, y1, m, x2, y2, n = x2, y2, n, x1 - q * x2, y1 - q * y2, r
    return (x2, y2, n)

def modular_inverse(a, mod):
    x, _, g = extended_euclid(a, mod)
    if g != 1:
        return None # Modular inverse of a does not exist
    else:
        return x % mod

def prime_factorization(n):
    '''
    Trial division.
    Input: 
        n : a positive integer
    Output:
        a dictionary of #(each prime factors) of n,
    '''
    result = []
    app = result.append
    if n < 2:
        return Counter()
    while n % 2 == 0:
        app(2)
        n //= 2
    p = 3
    while p*p <= n:
        while n % p == 0:
            app(p)
            n //= p
        p += 2
    if n > 1:
        app(n)
    return Counter(result)

MOD = 10**9 + 7

N = int(input())
*A, = map(int, input().split())
ans = 0
lcm = Counter()
for a in A:
    lcm |= prime_factorization(a)
L = 1
for x, y in lcm.items():
    L *= pow(x, y, MOD)
    L %= MOD
for a in A:
    ans += L * modular_inverse(a, MOD)
    ans %= MOD
print(ans)

### FIXED CODE ###

from collections import Counter

def extended_euclid(a, b):
    x1, y1, m = 1, 0, a
    x2, y2, n = 0, 1, b
    while m % n != 0:
        q, r = divmod(m, n)
        x1, y1, m, x2, y2, n = x2, y2, n, x1 - q * x2, y1 - q * y2, r
    return (x2, y2, n)

def modular_inverse(a, mod):
    x, _, g = extended_euclid(a, mod)
    if g != 1:
        return None # Modular inverse of a does not exist
    else:
        return x % mod

def prime_factorization(n):
    '''
    Trial division.
    Input: 
        n : a positive integer
    Output:
        a dictionary of #(each prime factors) of n,
    '''
    result = []
    app = result.append
    if n < 2:
        return Counter()
    while n % 2 == 0:
        app(2)
        n //= 2
    p = 3
    while p*p <= n:
        while n % p == 0:
            app(p)
            n //= p
        p += 2
    if n > 1:
        app(n)
    return Counter(result)

MOD = 10**9 + 7

N = int(input())
*A, = map(int, input().split())
ans = 0
lcm = {}
for a in A:
    for x, y in prime_factorization(a).items():
        if x not in lcm.keys():
            lcm[x] = y
        else:
            lcm[x] = max(lcm[x], y)
L = 1
for x, y in lcm.items():
    L *= pow(x, y, MOD)
    L %= MOD
for a in A:
    ans += L * modular_inverse(a, MOD)
    ans %= MOD
print(ans)
### BUGGY CODE ###

N=int(input())

ans=0
result=[]
for i in range(N):
    s= ''.join(sorted(input()))
    ans+=result.count(s)
    result.append(s)
print(ans)

### FIXED CODE ###

import collections as cl
import math
N=int(input())

result_=[]
for i in range(N):
    s= ''.join(sorted(input()))
    result_.append(s)

result=list(cl.Counter(result_).values())

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

ans=0
for j in range(len(result)):
    if result[j]==1:
        continue
    else:
        ans+=combinations_count(result[j],2)

print(ans)