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

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

for i in range(0, m):
    a, b = map(int, input().split())
    bridge.append([a - 1, b - 1])

bridge = bridge[1:]
bridge = reversed(bridge)
result = []
groups = []

value = n * (n - 1) // 2
result.append(value)

def find_group(v):
    for i, a in enumerate(groups):
        if v in a:
            return i
    return -1

for b in bridge:
    if value <= 0:
        result.append(0)
        continue
    b1 = find_group(b[0])
    b2 = find_group(b[1])
    if b1 < 0 and b2 < 0:
        groups.append(b)
        value -= 1
    elif b1 == b2:
        pass
    elif b1 >= 0 and b2 >= 0:
        value -= (len(groups[b1]) * len(groups[b2]))
        if b1 < b2:
            groups[b1].extend(groups[b2])
            del groups[b2]
        else:
            groups[b2].extend(groups[b1])
            del groups[b1]
    elif b1 >= 0:
        value -= len(groups[b1])
        groups[b1].append(b[1])
    else:
        value -= len(groups[b2])
        groups[b2].append(b[0])
    result.append(max(value, 0))

result = reversed(result)
for r in result:
    print(r)


### FIXED CODE ###

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

for i in range(0, m):
    a, b = map(int, input().split())
    bridge.append([a - 1, b - 1])

bridge = bridge[1:]
bridge = reversed(bridge)
result = []


parent = [-1] * n
size = [1] * n
def root(v):
    p = parent[v]
    if p >= 0:
        return root(p)
    return v

value = n * (n - 1) // 2
result.append(value)

for b in bridge:
    if value <= 0:
        result.append(0)
        continue
    p0 = root(b[0])
    p1 = root(b[1])
    if p0 == p1:
        result.append(value)
        continue
    s0 = size[p0]
    s1 = size[p1]
    if p0 < p1:
        parent[p1] = p0
        size[p0] += size[p1]
    else:
        parent[p0] = p1
        size[p1] += size[p0]
    value -= s0 * s1
    result.append(max(value, 0))

result = reversed(result)
for r in result:
    print(r)
### BUGGY CODE ###

import numpy as np
import sys
from collections import deque

n,m = map(int,input().split())
ab = [[int(i) for i in input().split()] for i in range(m)]
abl=[[] for i in range(n)]
for i in range(len(ab)):
    abl[ab[i][0]-1].append(ab[i][1])
    abl[ab[i][1]-1].append(ab[i][0])

an=[0]*(n-1)
i=1
wk=deque([i])
wwk=deque([])
il=deque(abl[0])

while any(wk):
    i=wk.pop()
    il=deque(abl[i-1])
    while any(il):
        iwk=il.pop()
        if an[iwk-2]==0 and iwk>1:
            wwk.append(iwk)
            an[iwk-2]=i
            if all(an):
                print('Yes')
                for i in an:
                    print(i)
                sys.exit()
    if not(any(wk)):
        wk=deque(wwk)
        wwk=deque([])
print('No')

### FIXED CODE ###

def main():
    from collections import deque
 
    n,m =map(int,input().split())
    abl=[[] for i in range(n+1)]
    for i in range(m):
        a,b = map(int,input().split())
        abl[a].append(b)
        abl[b].append(a)
 
    an=[0]*(n+1)
    an[0]=1
    tg = deque([1])
    while len(tg):
        itg = tg.popleft()
        for j in abl[itg]:
            if an[j]==0:
                an[j]=itg
                tg.append(j)

    if all(an):
        print('Yes')
        for j in an[2:]:
            print(j)
    else:
        print('No')
 
main()
### BUGGY CODE ###

import math

import numpy as np


def get_pseudo_input():
    N = 3
    A = np.array([6, 10, 16])
    return N, A


def get_input():
    N = int(input())
    A = np.array([int(x) for x in input().split()])
    return N, A


def sieve_of_eratosthenes(x: int):
    ret = np.full(x + 1, -1)
    for i in range(1, x + 1):
        ret[i] = i
    p_max = int(math.sqrt(x))
    for p in range(2, p_max + 1):
        if ret[p] < p:  # p is not a prime number
            continue
        for i in range(p, x + 1, p):
            if ret[i] > p:
                ret[i] = p
    return ret


A_max = 10 ** 6
p_table = sieve_of_eratosthenes(A_max)

N, A = get_input()
# Store a number of unique Ais using the prime number
p_nums = np.zeros(A_max + 1)
p_nums[1] = N
max_p_nums = 0
for a in A:
    # print(f"a={a}")
    while a > 1:
        p = p_table[a]
        while a % p == 0:
            a = a // p
        # print(f"  a={a}")
        p_nums[p] += 1
        if max_p_nums < p_nums[p]:
            max_p_nums = p_nums[p]
# print(max_p_nums)
if max_p_nums <= 1:
    # GCD of A is 1
    print("pairwise coprime")
elif max_p_nums == N:
    # GCD of A is not 1
    print("not coprime")
else:
    print("setwise coprime")

### FIXED CODE ###

import math


def get_pseudo_input():
    N = 3
    A = [6, 10, 16]
    return N, A


def get_input():
    N = int(input())
    A = [int(x) for x in input().split()]
    return N, A


def sieve_of_eratosthenes(x: int):
    ret = [-1] * (x + 1)
    for i in range(1, x + 1):
        ret[i] = i
    p_max = int(math.sqrt(x))
    for p in range(2, p_max + 1):
        if ret[p] < p:  # p is not a prime number
            continue
        for i in range(p, x + 1, p):
            if ret[i] > p:
                ret[i] = p
    return ret


A_max = 10 ** 6
p_table = sieve_of_eratosthenes(A_max)

N, A = get_input()
# Store a number of unique Ais using the prime number
p_nums = [0] * (A_max + 1)
p_nums[1] = N
max_p_nums = 0
for a in A:
    # print(f"a={a}")
    while a > 1:
        p = p_table[a]
        while a % p == 0:
            a = a // p
        # print(f"  a={a}")
        p_nums[p] += 1
        if max_p_nums < p_nums[p]:
            max_p_nums = p_nums[p]
# print(max_p_nums)
if max_p_nums <= 1:
    # GCD of A is 1
    print('pairwise coprime')
elif max_p_nums == N:
    # GCD of A is not 1
    print('not coprime')
else:
    print('setwise coprime')
### BUGGY CODE ###

n = int(input())
a = [int(input()) for i in range(n)]
print(max(a[1:]))
for i in range(1,n):
  ans = max(a[0:i] + a[i+1:n])
  print(ans)

### FIXED CODE ###

n = int(input())
a = [int(input()) for i in range(n)]

sorted_a = sorted(a)
max_a = sorted_a[-1]
max_a_r = sorted_a[-2]

for i in range(n):
  if a[i] == max_a:
    print(max_a_r)
  else:
    print(max_a)
### BUGGY CODE ###

n = int(input())

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

q = int(input())

#初期化

a_dic ={}


for i in a:
    if i not in a_dic:
        a_dic[i] = 1
    else:
        a_dic[i] += 1

#a_sorted = sorted(a)
for i in range(q):
    ans = 0
    b,c = map(int, input().split())
    #print(a_dic)
    
    if b in a_dic:
        if c not in a_dic:
            a_dic[c] = a_dic[b]

        else:
            tmp_c = a_dic[c]
            tmp_c += a_dic[b]
            a_dic[c] = tmp_c
        a_dic.pop(b) 
    for k,v in a_dic.items():
        ans += k*v
    print(ans)

### FIXED CODE ###

n = int(input())

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

q = int(input())

#初期化

a_dic ={}
ans = 0

for i in a:
    if i not in a_dic:
        a_dic[i] = 1
    else:
        a_dic[i] += 1
    
    ans += i

#print(ans)
#a_sorted = sorted(a)
for i in range(q):
    #ans = 0
    b,c = map(int, input().split())
    #print(a_dic)
    
    if b in a_dic:
        if c not in a_dic:
            a_dic[c] = a_dic[b]

        else:
            tmp_c = a_dic[c]
            tmp_c += a_dic[b]
            a_dic[c] = tmp_c
        tmp_a = (c-b) * a_dic[b]
        a_dic.pop(b)
        ans += tmp_a
    print(ans)
### BUGGY CODE ###

import math
a,b,n = map(int,input().split())

x = 0
now = 0
result = 0

    

for i in range(n+1):
    if x > b:
        break
    x = i
    now = (((a * x)//b)) - (a * (x//b))
    #now = math.ceil(((a * x)/b)) - (a * math.ceil(x/b))
    #print("now=",now,"x=",x)
    #print(result,now)
    result = max(result,now)

print(result)
    



### FIXED CODE ###


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

x = min(b-1,n)

print((((a * x)//b)) )
### BUGGY CODE ###

import sys, math

def input():
    return sys.stdin.readline()[:-1]

def main():
    N = int(input())
    T = []
    G = [[] for k in range(N+1)]
    for k in range(N-1):
        a, b = map(int,input().split())
        G[a].append(b)
        G[b].append(a)
        T.append(str(a)+"0"+str(b))

    V = [0 for k in range(N+1)]
    C = [set() for k in range(N+1)]
    ans = dict()
    m = 0
    V[1] = 1
    Q = [1]
    while len(Q) > 0:
        ima = Q.pop()
        for tsugi in G[ima]:
            if V[tsugi] == 0:
                V[tsugi] = 1
                t = 1
                while t in C[ima] or t in C[tsugi]:
                    t += 1
                m = max(m,t)
                C[ima].add(t)
                C[tsugi].add(t)
                ans[str(ima)+"0"+str(tsugi)] = t
                Q.append(tsugi)
    print(m)
    for e in T:
        print(ans[e])

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys, math

def input():
    return sys.stdin.readline()[:-1]

def main():
    N = int(input())
    T = []
    G = [[] for k in range(N+1)]
    for k in range(N-1):
        a, b = map(int,input().split())
        G[a].append(b)
        G[b].append(a)
        T.append(str(a)+"0"+str(b))

    V = [0 for k in range(N+1)]
    C = [set() for k in range(N+1)]
    ans = dict()
    m = 0
    V[1] = 1
    Q = [1]
    while len(Q) > 0:
        ima = Q.pop()
        t = 1
        for tsugi in G[ima]:
            if V[tsugi] == 0:
                V[tsugi] = 1
                while t in C[ima] or t in C[tsugi]:
                    t += 1
                m = max(m,t)
                C[ima].add(t)
                C[tsugi].add(t)
                ans[str(ima)+"0"+str(tsugi)] = t
                Q.append(tsugi)
    print(m)
    for e in T:
        print(ans[e])

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

N, M = map(int, input().split())
A = list(map(int, input().split()))
rewritelist = []
for i in range(0, M):
	rewritelist.append(list(map(int, input().split())))
A.sort()
rewritelist.sort(key = lambda val: val[1], reverse = True)
cardlist = []
for i in range(0, N):
	if rewritelist == []: break
	cardlist.append(rewritelist[0][1])
	rewritelist[0][0] -= 1
	if rewritelist[0][0] == 0: rewritelist.pop(0)
for i in range(0, len(cardlist)):
	if cardlist[i] <= A[i]: break
	A[i] = cardlist[i]
sum = 0
for i in range(0, N):
	sum += A[i]
print(sum)

### FIXED CODE ###

def smaller(x, y):
	if x < y: return x
	return y
def larger(x, y):
	if x > y: return x
	return y

N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
Asum = []
sum = 0
for i in range(0, N):
	sum += A[i]
	Asum.append(sum)
controllist = []
for i in range(0, M):
	controllist.append(list(map(int, input().split())))
controllist.sort(key = lambda v: v[1], reverse = True)
addlist = []
flag = False
for i in range(0, M):
	for j in range(0, controllist[i][0]):
		addlist.append(controllist[i][1])
		if len(addlist) == N:
			flag = True
			break
	if flag: break
sum = 0
for i in range(0, smaller(N, len(addlist))):
	sum += larger(A[i], addlist[i])
for i in range(len(addlist), N):
	sum += A[i]
print(sum)
### BUGGY CODE ###

from collections import deque
inf = 10**10
dxdy = ((0,1),(0,-1),(1,0),(-1,0)) 
h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
s = ['#'*(w+2)] + ['#' + input() + '#' for _ in range(h)] + ['#'*(w+2)]
d = [[inf]*(w+1) for _ in range(h+1)]
d[ch][cw] = 0
q = deque([(ch,cw)])
while q: 
    y,x = q.pop() 
    for dx,dy in dxdy: 
        if s[y+dy][x+dx]=='.' and d[y+dy][x+dx] > d[y][x]:
            d[y+dy][x+dx] = d[y][x]
            q.append((y+dy,x+dx))
    for i in range(-2,3):
        for j in range(-2,3):
            if i==j==0:
                continue 
            elif 1<=y+i<=h and 1<=x+j<=w and s[y+i][x+j]=='.' and d[y+i][x+j]>d[y][x]+1:
                
                d[y+i][x+j] = d[y][x]+1
                q.append((y+i,x+j)) 
ans = d[dh][dw] 
if ans == inf:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

from collections import deque
inf = 10**10
dxdy = ((0,1),(0,-1),(1,0),(-1,0)) 
h, w = map(int, input().split())
ch, cw = map(int, input().split())
dh, dw = map(int, input().split())
s = ['#'*(w+2)] + ['#' + input() + '#' for _ in range(h)] + ['#'*(w+2)]
d = [[inf]*(w+1) for _ in range(h+1)]
d[ch][cw] = 0
q = deque([(ch,cw)])
while q: 
    y,x = q.pop() 
    for dx,dy in dxdy: 
        if s[y+dy][x+dx]=='.' and d[y+dy][x+dx] > d[y][x]:
            d[y+dy][x+dx] = d[y][x]
            q.append((y+dy,x+dx))
    for i in range(-2,3):
        for j in range(-2,3):
            if i==j==0:
                continue 
            elif 1<=y+i<=h and 1<=x+j<=w and s[y+i][x+j]=='.' and d[y+i][x+j]>d[y][x]+1:
                
                d[y+i][x+j] = d[y][x]+1
                q.appendleft((y+i,x+j)) 
ans = d[dh][dw] 
if ans == inf:
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

n,x=map(int,input().split())
for i in range(n+1):
        for j in range(n+1):
                for z in range(n+1):
                        total=10000*i+5000*j+1000*z
                        if total==x and i+j+z==n:
                                print(i,j,z)
                                exit()
print(-1,-1,-1)

### FIXED CODE ###

def test():
    n,y=map(int,input().split())
    a,b,c=10000,5000,1000
    for i in range(n+1):
        for j in range(n+1):
            ans=a*i+b*j
            if y<ans:
                break
            if (y-ans)%c==0:
                k=(y-ans)//c
                if i+j+k==n:
                    return i,j,k
    return -1,-1,-1
one,two,three=test()
print(one,two,three)
### BUGGY CODE ###

import itertools
import collections

N=int(input())
S=list(input())
answer=0
col = collections.Counter(S)
values, counts = zip(*col.most_common())

def soujou(li):
    atai=1
    for j in li:
        atai=j*atai
    return atai

for i in range(N):
    C=list(itertools.combinations(counts, i+1))
    kumiawase=[soujou(j) for j in C]
    answer=(answer+sum(kumiawase))%(7+10**9)
print(answer)

### FIXED CODE ###

N=list(range(int(input())))
S=list(input())
S=sorted(S)
answer=0

prev=S[0]
counts = []
counter=0

for k in S:
    if k==prev:
        counter+=1
    else:
        prev=k
        if counter!=0:
            counts.append(1+counter)
        counter=1
if counter!=0:
    counts.append(1+counter)

def soujou(li):
    atai=1
    for j in li:
        atai=j*atai
    return atai

answer=soujou(counts)-1
print(answer%(7+10**9))
### BUGGY CODE ###

n,m,k=map(int,input().split())
A=list(map(int, input().split()))
B=list(map(int, input().split()))
ans=0
a, b=[0], [0]
for i in range(n):
    a.append(a[i]+A[i])
for i in range(m):
    b.append(b[i]+B[i])
for i in range(n+1):
    if k<a[i]:
        break
    j=m
    while b[j]>k-a[i]:
        j-=1
    ans=max(ans,i+j)
print(ans)

### FIXED CODE ###

n,m,k=map(int,input().split())
A=list(map(int, input().split()))
B=list(map(int, input().split()))
ans=0
a, b=[0], [0]
for i in range(n):
    a.append(a[i]+A[i])
for i in range(m):
    b.append(b[i]+B[i])
j=m
for i in range(n+1):
    if k<a[i]:
        break
    while b[j]>k-a[i]:
        j-=1
    ans=max(ans,i+j)
print(ans)
### BUGGY CODE ###

S = input()
ans = 0
A = [0] * (len(S) + 1)
for i in range(len(S)):
    A[i+1] = int(S[-i:]) % 2019

for i in range(2020):
    num = A.count(i)
    ans += int(num * (num-1) / 2)

print(ans)

### FIXED CODE ###

p=d=2019
z=[0]*p
for i,j in enumerate(input()[::-1]):
	d=d+int(j)*pow(10,i,p)
	z[d%p]+=1
r=z[0]
for i in z:
	r+=i*(i-1)//2
print(r)
### BUGGY CODE ###

MOD = 10 ** 9 + 7

n = int(input())
alst = list(map(int, input().split()))
bin_s = [2 ** i for i in range(60)]
cnt = [0 for _ in range(60)]

for a in alst:
    for j in range(60):
        if bin_s[j] & a:
            cnt[j] += 1

ans = 0
for i in range(60):
    ans += bin_s[i] * cnt[i] * (n - cnt[i])
    ans %= MOD
print(ans)

### FIXED CODE ###

MOD = 10 ** 9 + 7

n = int(input())
alst = list(map(int, input().split()))
bin_s = [2 ** i for i in range(60)]
cnt = [0 for _ in range(60)]

for a in alst:
    for j in range(60):
        if bin_s[j] & a:
            cnt[j] += 1

ans = 0
for i in range(60):
    ans += bin_s[i] * cnt[i] * (n - cnt[i])
    ans %= MOD
print(ans)
### BUGGY CODE ###

import collections
N = int(input())
A = [int(x) for x in input().split()]
a = collections.Counter(A)
Q = int(input())
for i in range(Q):
  B, C = map(int, input().split())
  if B in a:
    a[C] += a[B]
    a[B] = 0
  tmp = 0
  for i in a:
    tmp += a[i] * i
  print(tmp)

### FIXED CODE ###

N = int(input())
A = [int(x) for x in input().split()]
S =sum(A)
D = [0]*(10**5+1)
for a in A:
  D[a] += 1
Q = int(input())
for i in range(Q):
  b, c = map(int, input().split())
  S -= D[b]*b
  S += D[b]*c
  D[c] += D[b]
  D[b] = 0
  print(S)
### BUGGY CODE ###

N = int(input())
ans = 0
nums = []
for _ in range(N):
    A = int(input())
    if A in nums:
        ans -= 1
        nums.remove(A)
    else:
        ans += 1
        nums.append(A)
print(ans)


### FIXED CODE ###

N = int(input())
ans = 0
nums = set()
for _ in range(N):
    A = int(input())
    if A in nums:
        ans -= 1
        nums.remove(A)
    else:
        ans += 1
        nums.add(A)
print(ans)
### BUGGY CODE ###

from collections import deque

def main():
    N, M = list(map(int, input().split()))
    R = [set() for _ in range(N+1)]
    for _ in range(M):
        x = list(map(int, input().split()))
        R[x[0]].add(x[1])
        R[x[1]].add(x[0])
    
    q = deque()
    s = set()
    r = [0] * (N+1)
    q.append(1)
    while any(q):
        x = q.popleft()
        s.add(x)
        ro = R[x]
        for i in ro:
            if r[i] == 0 and i not in s and i not in q:
                r[i] = x
                if r.count(0) == 2:
                    print("Yes")
                    print("\n".join(map(str, r[2:])))
                    exit()
                else:
                    q.append(i)
    if len(s) == N:
        print("Yes")
        print("\n".join(map(str, r[2:])))
    else:
        print("No")

if __name__ == '__main__':
    main()

### FIXED CODE ###

from collections import deque

def main():
    N, M = list(map(int, input().split()))
    R = [set() for _ in range(N+1)]
    for _ in range(M):
        x = list(map(int, input().split()))
        R[x[0]].add(x[1])
        R[x[1]].add(x[0])
    
    q = deque()
    #s = set()
    r = [0] * (N+1)
    q.append(1)
    while any(q):
        x = q.popleft()
        #s.add(x)
        ro = R[x]
        for i in ro:
            #if r[i] == 0 and i not in s and i not in q:
            if r[i] == 0: 
                r[i] = x
                q.append(i)
    #if len(s) == N:
    print("Yes")
    print("\n".join(map(str, r[2:])))
    #else:
    #    print("No")

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

from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq

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

if n % 2 == 1:
    for i in range(1,m+1):
        print(i,n-i+1)
    sys.exit()

else:
    a = [0]*n
    i = 0
    j = 1
    while True:
        if a[i % n] == 0 and a[(i+j) % n] == 0:
            a[i % n] = 1
            a[(i+j) % n] = 1
            print((i % n) + 1, ((i+j) % n) +1)
            j = j + 1
        else:
            i = i + 1
            
        if len(a) == m: sys.exit()




### FIXED CODE ###

from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq

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

p = m // 2
for i in range(p):
    print(p-i,p+2+i)

q = m // 2 + 1
if m % 2 == 1:
    for i in range(q):
        print(m+q-i,m+q+i+1)
else:
    for i in range(q-1):
        print(m+q-i,m+q+i+1)
### BUGGY CODE ###

N = int(input())
S = input()
R = []
nsum = 0
for i in range(N):
    if S[i] == "R":
        R.append(i)
B = []
for i in range(N):
    if S[i] == "B":
        B.append(i)
g = 0
for i in range(N):
    if S[i] == "G":
        g += 1
        for r in R:
            for b in B:
                if abs(i - b) - abs(b - r) == 0 or abs(b - i) - abs(r - i) == 0 or abs(b - r) - abs(i - r) == 0:
                    nsum += 1
                    if max(i,b,r) == b: break
print(len(R)*len(B)*g - nsum)

### FIXED CODE ###

N = int(input())
S = input()
R = 0
G = 0
B = 0
nsum = 0
for s in S:
    if s == "R":
        R += 1
    elif s == "G":
        G += 1
    else:
        B += 1
count = 0
for i in range(N):
    for k in range(i+1,N):
        if not S[i] == S[k]:
            if 2*k - i <= N - 1:
                if S[i] != S[2*k - i] and S[k] != S[2*k - i]:
                    count += 1
print(R*G*B - count)
### BUGGY CODE ###

# D Anything Goes to Zero

n = int(input())
x = input()
for i in range(n):
  xi = int(x, 2)
  xi = xi ^ (1 << n-i-1)

  ans = 0
  while xi != 0:
    xi = xi % bin(xi).count("1")
    ans += 1
  print(ans)


### FIXED CODE ###

# D Anything Goes to Zero

n = int(input())
x = input()

original_pop_count = x.count("1")
one_pop_count = original_pop_count - 1
zero_pop_count = original_pop_count + 1

one_mod = 0
zero_mod = 0
for b in x:
  if one_pop_count != 0:
    one_mod = (one_mod * 2 + int(b)) % one_pop_count
  zero_mod = (zero_mod * 2 + int(b)) % zero_pop_count

#fの前計算
f = [0] * 220000
pop_count = [0] * 220000
for i in range(1, 220000):
  pop_count[i] = pop_count[i//2] + i % 2
  f[i] = f[i % pop_count[i]] + 1

#pow2の前計算
one_pow2 = [1] * 220000
zero_pow2 = [1] * 220000
for i in range(1, 220000):
  if one_pop_count != 0:
    one_pow2[i] = one_pow2[i-1] * 2 % one_pop_count
  zero_pow2[i] = zero_pow2[i-1] * 2 % zero_pop_count

for i in range(n-1, -1, -1):
  if x[n-1-i] == "1":
    if one_pop_count != 0:
      nxt = one_mod
      nxt -= one_pow2[i]
      nxt %= one_pop_count
      print(f[nxt] + 1)
    else:
      print(0)
  if x[n-1-i] == "0":
    nxt = zero_mod
    nxt += zero_pow2[i]
    nxt %= zero_pop_count
    print(f[nxt] + 1)
### BUGGY CODE ###

import bisect

n=int(input())
a=[int(i) for i in input().split()]
b=[int(i) for i in input().split()]
b.sort()
c=[int(i) for i in input().split()]
c.sort()
#print(n,a,b,c)

ans=0
for j in range(n):
    aa=bisect.bisect_right(b, a[j])
    if aa < n:
        for i in range(aa,n):
            ans+=n-bisect.bisect_right(c, b[i])

print(ans)


### FIXED CODE ###

import bisect

n=int(input())
a=[int(i) for i in input().split()]
a.sort()
b=[int(i) for i in input().split()]
c=[int(i) for i in input().split()]
c.sort()
#print(n,a,b,c)

ans=0
for j in range(n):
    aa=bisect.bisect_left(a, b[j])
    bb=bisect.bisect_right(c, b[j])
    ans+=aa*(n-bb)

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

N = int(input())
X = [int(i) for i in input().split()]
for i in range(N): print((lambda j: sorted([x for k, x in enumerate(X) if not k == j]))(i)[N//2-1])

### FIXED CODE ###

N = int(input())
X = [int(i) for i in input().split()]
X_sorted = sorted(X)

X_med = X_sorted[N//2-1:N//2+1]
for xi in X:
  if xi <= X_med[0]: print(X_med[1])
  else: print(X_med[0])
### BUGGY CODE ###

S = raw_input()
count = 0
flag = True
while(flag):
    if '01' in S:
        S = S.replace('01','',1)
        count += 2
        continue
    elif '10' in S:
        S = S.replace('10','',1)
        count += 2
        continue                                                                                                    
    flag = False
print count


### FIXED CODE ###

S = raw_input()
print 2*min(S.count('0'), S.count('1'))
### BUGGY CODE ###

from fractions import gcd


def solve():
    N, *A = map(int, open(0).read().split())
    MOD = 10 ** 9 + 7

    lcm = 1
    for a in A:
        lcm = a * lcm // gcd(a, lcm)

    ans = [lcm // a for a in A]
    print(sum(ans) % MOD)


if __name__ == '__main__':
    solve()


### FIXED CODE ###

from fractions import gcd


def solve():
    N, *A = map(int, open(0).read().split())
    MOD = 10 ** 9 + 7

    lcm = 1
    for a in A:
        lcm = a * lcm // gcd(a, lcm)

    ans = [lcm // a for a in A]
    print(sum(ans) % MOD)


if __name__ == '__main__':
    solve()