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

from collections import deque
n, m = list(map(int, input().split()))
connects = [[0] * n for _ in range(n)]
for _ in range(m):
    i, j =  list(map(int, input().split()))
    connects[i - 1][j - 1] = 1
    connects[j - 1][i - 1] = 1
can = False
d = [float('inf')] * n
d[0] = 0
r = [0] * n
visited = [0] * n
stack = deque([0, ])
while stack:
    x = stack.popleft()
    next = [j for j in range(n) if connects[x][j] == 1]
    for dx in next:
        d[dx] = min(d[dx], d[x] + 1)
        if visited[dx]:
            continue
        else:
            stack.append(dx)
            visited[dx] = 1
print('Yes')
for i in range(1, n):
    d_next = [[j + 1, d[j]] for j in range(n) if connects[i][j] == 1]
    d_min = float('inf')
    i_min = 0
    for i, dx in d_next:
        if dx < d_min:
            d_min = dx
            i_min = i
    print(i_min)

### FIXED CODE ###

from collections import deque
n, m = list(map(int, input().split()))
connects = [[] * n for _ in range(n)]
for _ in range(m):
    i, j = list(map(int, input().split()))
    connects[i - 1].append(j - 1)
    connects[j - 1].append(i - 1)
stack = deque([0, ])
visited = [-1] * n
while stack:
    x = stack.popleft()
    for dx in connects[x]:
        if visited[dx] == -1:
            visited[dx] = x + 1
            stack.append(dx)
        else:
            continue
print('Yes')
[print(i) for i in visited[1:]]
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline

N = int(input())
src = [tuple(map(int,input().split())) for i in range(N-1)]

if N==1:
    print(2)
    exit()

es = [[] for i in range(N)]
for a,b in src:
    a,b = a-1,b-1
    es[a].append(b)
    es[b].append(a)

MOD = 10**9+7
dp = [[1,1] for i in range(N)]

def rec(i,parent):
    for to in es[i]:
        if to==parent: continue
        rec(to,i)
        dp[i][0] *= (dp[to][0] + dp[to][1])
        dp[i][1] *= dp[to][0]
        dp[i][0] %= MOD
        dp[i][1] %= MOD

rec(0,-1)
print(sum(dp[0])%MOD)

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
MOD = 10**9+7

N = int(input())
XY = [tuple(map(int,input().split())) for i in range(N-1)]
es = [[] for _ in range(N)]
for x,y in XY:
    x,y = x-1,y-1
    es[x].append(y)
    es[y].append(x)

dp = [[1,1] for i in range(N)]
def rec(v,p=-1):
    for to in es[v]:
        if to==p: continue
        rec(to,v)
        dp[v][0] *= (dp[to][0] + dp[to][1])
        dp[v][1] *= dp[to][0]
        dp[v][0] %= MOD
        dp[v][1] %= MOD
rec(0)

print(sum(dp[0]) % MOD)
### BUGGY CODE ###

import numpy as np


N = int(input())
A = np.array(list(map(int, input().split())))
ans = []
for x in range(10 ** 5 + 1):
    c = np.sum((A >= (x - 1)) & (A <= (x + 1)))
    ans.append(c)

print(max(ans))

### FIXED CODE ###

from collections import Counter


N = int(input())
A = list(map(int, input().split()))

nc = Counter(A)
C = []
for i in range(max(A) + 1):
    c = nc[i - 1] + nc[i] + nc[i + 1]
    C.append(c)

print(max(C))
### BUGGY CODE ###

K=int(input())
a=7
for i in range(1,K+1):
    if a%K==0:
        print(i)
        exit()
    a=a*10+7
print(-1)

### FIXED CODE ###

K=int(input())
a=7
for i in range(1,K+1):
    if a%K==0:
        print(i)
        exit()
    a=(a*10+7)%K
print(-1)
### BUGGY CODE ###

power = 1
n = int(input())

for i in range(n):
    power = power * (i + 1)

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

### FIXED CODE ###

power = 1
n = int(input())
tmp = 10 ** 9 + 7

for i in range(n):
    power = power * (i + 1) % tmp

print(power)
### BUGGY CODE ###

import fractions
from functools import reduce
m=int(input())
a=list(map(int,input().split()))
a.sort()
def lcm_base(x,y):
    return (x*y)//fractions.gcd(x,y)
def lcm_list(numbers):
    return reduce(lcm_base,numbers,1)
mod=10**9+7
n=lcm_list(a)
ans=0
for i in range(m):
    ans+=(n//a[i])
print(ans%mod)


### FIXED CODE ###

import fractions
from functools import reduce
m=int(input())
a=list(map(int,input().split()))
def lcm_base(x,y):
    return (x*y)//fractions.gcd(x,y)
def lcm_list(numbers):
    return reduce(lcm_base,numbers,1)
mod=10**9+7
n=lcm_list(a)
ans=0
for i in range(m):
    ans+=(n//a[i])
print(ans%mod)
### BUGGY CODE ###

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

def prime_factorize(n: int) -> list:
    ret = []
    for i in range(2, n**2):
        if n%i != 0: continue
        num = 0
        while n%i == 0:
            num += 1
            n /= i
        ret.append([i, num])

    if n != 1:
        ret.append([n, 1])

    return ret

g = fractions.gcd(b, a%b)
pf = prime_factorize(g)
print(len(pf)+1)


### FIXED CODE ###

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

def factorize(n: int) -> int:
    b = 2
    ret = []
    while b*b <= n:
        while n%b == 0:
            n //= b
            ret.append(b)
        b = b + 1

    if n > 1:
        ret.append(n)

    return list(set(ret))

g = fractions.gcd(a, b)
print(len(factorize(g))+1)
### BUGGY CODE ###

import sys, os, math, bisect, itertools, collections, heapq, queue
# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
from decimal import Decimal
from collections import defaultdict, deque

# import fractions

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)
# lcm = lambda x, y: (x * y) // fractions.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N, K = il()
    X = il()

    ret = MAX
    for n in range(N - K + 1):
        C = X[n:n + K]
        ret = min(ret, abs(C[0]) + abs(C[0] - C[K-1]), abs(C[K-1]) + abs(C[0] - C[K-1]))
    print(ret)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import os
import math
import bisect
import collections
import itertools
import heapq
import re
import queue

# import fractions

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)
# lcm = lambda x, y: (x * y) // fractions.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N, K = il()
    X = il()

    ret = MAX
    for n in range(N - K + 1):
        l = abs(X[n]) + abs(X[n]-X[n+K-1])
        r = abs(X[n+K-1]) + abs(X[n+K-1] - X[n])
        ret = min(ret, l, r)
    print(ret)


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

# coding: utf-8

import sys
input = sys.stdin.readline

def f(n, k):
    global a
    mod = int(1e9 + 7)
    dp = [[0] * (k + 1) for _ in range(n + 1)]
    for i in range(n + 1):
        dp[i][0] = 1
    for i in range(1, n + 1):
        csum = [0] + list(dp[i - 1])
        for j in range(k + 1):
            csum[j + 1] += csum[j]
            csum[j + 1] %= mod
        for j in range(1, k + 1):
            dp[i][j] = csum[j + 1] - csum[max(0, j - a[i])]
            if dp[i][j] < 0:
              dp[i][j] += mod
    return(dp[n][k])

n, k = map(int, input().split()) # 1 <= n <= 100, 0 <= k <= 10^5
a = list(map(int, input().split()))
a.insert(0, 0)
print(f(n, k))


### FIXED CODE ###

# coding: utf-8

from itertools import accumulate as accum
import sys
input = sys.stdin.readline

def f(n, k, ai):
    mod = int(1e9 + 7)
    dp = [0] * (k + 1)
    dp[0] = 1
    for a in ai:
        # csum: Cumulative sum
        # dp[j] = dp[0] + dp[1] + ... + dp[j]
        # dp = list(accum(dp, lambda x, y: (x + y) % mod))
        dp = list(accum(dp))
        # j = 0 ～ a[i] までは累積和の結果そのままで a[i] + 1 以降は
        # dp[j] -= dp[j] - dp[j - a[i] - 1]
        dp[a + 1:] = [x - y for x, y in zip(dp[a + 1:], dp)]
        dp = [x % mod for x in dp]
    return(dp[k])

n, k = map(int, input().split()) # 1 <= n <= 100, 0 <= k <= 10^5
a = list(map(int, input().split()))
print(f(n, k, a))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))
for i in range(N-1):
    for j in range(i+1,N):  
        if A[i] == A[j]:
            print("NO")
            sys.exit()
else:
    print("YES")

### FIXED CODE ###

import sys
N = int(input())
A = list(map(int, input().split()))
A2 = sorted(A)
for i in range(N-1): 
        if A2[i] == A2[i+1]: 
            print("NO")
            sys.exit()
else:
    print("YES")
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


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

    for h in range(1, 3501):
        for n in range(1, 3501):
            if 4 * n * h - N * n - N * h == 0:
                continue
            q, r = divmod(N * n * h, 4 * n * h - N * n - N * h)
            if r == 0 and q > 0:
                print(h, n, q)
                return


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


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

    for h in range(1, 3501):
        for n in range(1, 3501):
            if 4 * n * h - N * n - N * h == 0:
                continue
            q, r = divmod(N * n * h, 4 * n * h - N * n - N * h)
            if r == 0 and q > 0:
                print(h, n, q)
                return


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

def main():
    n = int(input())
    s = [""] * n
    ans = 0
    for i in range(n):
        s[i] = SortString(input())
    s.sort()
    for i in range(n - 1):
        for j in range(i + 1, n):
            if s[i] == s[j]:
                ans += 1
            else:
                break
    print(ans)
  
  
def SortString(text):
    return "".join(sorted(list(text)))
  
  
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    n = int(input())
    s = [""] * n
    ans = 0
    for i in range(n):
        s[i] = SortString(input())
    sDictionary = {}
    for i in range(n):
        if sDictionary.get(s[i]):
            ans += sDictionary.get(s[i])
            sDictionary[s[i]] += 1
        else:
            sDictionary[s[i]] = 1
    print(ans)


def SortString(text):
    return "".join(sorted(list(text)))


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

x = int(input())
a = 2
b = 0
A = []
A.append(1 ** 5 - x)

while True:
    if A[-1] > 10 ** 9:
        break
    A.append(a ** 5 - x)
    a = a + 1

while True:
    if b ** 5 in A:
        break
    elif -b ** 5 in A:
        b = -b
        break
    b = b + 1

a = int((x + b ** 5) ** 0.2)

print(a, b)

### FIXED CODE ###

x = int(input())
a = 2
b = 0
A = []
A.append(1 ** 5 - x)

while True:
    if (a + 1) ** 5 - a ** 5 > 10 ** 10:
        break
    A.append(a ** 5 - x)
    a = a + 1

while True:
    if b ** 5 in A:
        break
    elif -b ** 5 in A:
        b = -b
        break
    b = b + 1

a = int((x + b ** 5) ** 0.2)

print(a, b)
### BUGGY CODE ###

import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

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

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

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

def calc(i,j):
    d = defaultdict(lambda:defaultdict(int))
    ret = -float('inf')
    if j==0:
        return 0
    if (N-i+1)//2 < j:
        return ret
    else:
        if i <= N-1:
            if d[i+2][j-1]:
                ret = max(ret,d[i+2][j-1])
            else:
                ret = max(ret,A[i]+calc(i+2,j-1))
        if i+1 <= N-1:
            if d[i+3][j-1]:
                ret = max(ret,d[i+3][j-1])
            else:
                ret = max(ret,A[i+1]+calc(i+3,j-1))
        d[i][j] = ret
        return ret


N = I()
A = LI()


if N%2 == 0:
    print(calc(0,N//2))
else:
    a1 = calc(0,N//2)
    n = 0
    for i in range(2,N,2):
        n += A[i]
    print(max(a1,n))

### FIXED CODE ###

import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

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

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

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

N = I()
A = LI()


if N%2 == 0:
    d = defaultdict(lambda:defaultdict(lambda:-float('inf')))
    d[0][1] = A[0]
    d[1][1] = max(A[0],A[1])
    for i in range(2,N):
        if i%2 == 0:
            for j in [i//2,i//2+1]:
                d[i][j] = max(d[i-2][j-1]+A[i],d[i-1][j])
        else:
            for j in [(i+1)//2]:
                d[i][j] = max(d[i-2][j-1]+A[i],d[i-1][j])
    print(d[N-1][N//2])
else:
    d = defaultdict(lambda:defaultdict(lambda:-float('inf')))
    d[0][1] = A[0]
    d[1][1] = max(A[0],A[1])
    for i in range(2,N):
        if i%2 == 0:
            for j in [i//2,i//2+1]:
                d[i][j] = max(d[i-2][j-1]+A[i],d[i-1][j])
        else:
            for j in [i//2,i//2+1]:
                d[i][j] = max(d[i-2][j-1]+A[i],d[i-1][j])
    a1 = d[N-1][N//2]
    n = 0
    for i in range(2,N,2):
        n += A[i]
    print(max(n,a1))
### BUGGY CODE ###

import sys
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]

def bunkai(x):
    for i in reversed(range(1, int(x**0.5//1)+1)):
        #print(i)
        if x%i == 0:
            return list((i, x//i))
    return list((1, S))


S = ii()
lim = 10**9
'''
#print(bunkai(S))
a, b = bunkai(S)[0], bunkai(S)[1]
if a==b:
    print(0, 0, bunkai(S)[0], 0, 0, bunkai(S)[1])
    exit()
for i in range(1, 10**18-S):
    if bunkai(i)[0]<=lim and bunkai(i)[1]<=lim and bunkai(S+i)[0]<=lim and bunkai(S+i)[1]<=lim:
        print(0, 0, bunkai(i)[0], bunkai(S+1)[1], bunkai(S+1)[0], bunkai(i)[1])
        exit()
'''
a = int(S**0.5)
keta = len(str(a))
b = 10**keta
for i in range(a+1, b+1):
    ii = i**2
    if bunkai(ii)[0]<=lim and bunkai(ii)[1]<=lim and bunkai(ii-S)[0]<=lim and bunkai(ii-S)[1]<=lim:
        print(0, 0, i, bunkai(ii-S)[1], bunkai(ii-S)[0], i)
        exit()

### FIXED CODE ###

import sys
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]

def bunkai(x):
    for i in reversed(range(1, int(x**0.5//1)+1)):
        #print(i)
        if x%i == 0:
            return list((i, x//i))
    return list((1, S))


S = ii()
lim = 10**9
'''
#print(bunkai(S))
a, b = bunkai(S)[0], bunkai(S)[1]
if a==b:
    print(0, 0, bunkai(S)[0], 0, 0, bunkai(S)[1])
    exit()
for i in range(1, 10**18-S):
    if bunkai(i)[0]<=lim and bunkai(i)[1]<=lim and bunkai(S+i)[0]<=lim and bunkai(S+i)[1]<=lim:
        print(0, 0, bunkai(i)[0], bunkai(S+1)[1], bunkai(S+1)[0], bunkai(i)[1])
        exit()
'''
s12 = S**0.5
a = int(s12)
keta = len(str(a))
b = 10**keta
if float(a)==s12:
    print(0, 0, a, 0, 0, a)
    exit()
for i in range(a+1, b+1):
    ii = i**2
    if bunkai(ii)[0]<=lim and bunkai(ii)[1]<=lim and bunkai(ii-S)[0]<=lim and bunkai(ii-S)[1]<=lim:
        print(0, 0, i, bunkai(ii-S)[1], bunkai(ii-S)[0], i)
        exit()
### BUGGY CODE ###

from itertools import combinations

n = int(input())
sticks = list(map(int, input().split()))
com = combinations(sticks, 3)
amount = 0
for m in com:
    if m[0] + m[1] > m[2] and m[0] + m[2] > m[1] and m[2] + m[1] > m[0]:
        amount += 1
print(amount)


### FIXED CODE ###

input()
a = input().split(' ')
b = []
for i in a:
    b.append(int(i))
b.sort()
b.reverse()
out = 0
for i in range(len(b) - 2):
    l = i + 1
    r = len(b) - 1
    while l < r:
        if b[i] < b[l] + b[r]:
            out += r - l
            l += 1
        else:
            r -= 1

print(out)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
q = int(input())
bc = [list(map(int, input().split())) for _ in range(q)]

for i in bc:
    str_a = " ".join(map(str, a))
    str_a = str_a.replace(str(i[0]), str(i[1]))
    a = list(map(int, str_a.split()))
    print(sum(a))

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
q = int(input())
bc = [list(map(int, input().split())) for _ in range(q)]
dic = {}
suma = sum(a)

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

for j in bc:
    dif = j[1] - j[0]
    if j[0] in dic:
        suma += dif * dic[j[0]]
    else:
        print(suma)
        continue
    if j[1] in dic:
        dic[j[1]] += dic.pop(j[0])
    else:
        dic[j[1]] = dic.pop(j[0])
    print(suma)
### BUGGY CODE ###

a,b,k=map(int,input().split())
for i in range(a,b+1):
  if a<=i<=a+k-1 or b-k+1<=i<=b:
    print(i)

### FIXED CODE ###

a,b,k=map(int,input().split())
lst=[]
for i in range(a,min(a+k, b)):
  lst.append(i)
  print(i)
for j in range(max(a, b-k+1),b+1):
  if j not in lst:
    print(j)
### BUGGY CODE ###

N, K = input().split()
n = int(N)
k = int(K)

t = n

if n % k == 0:
  print(0)
else:
  while True:
    n = abs(n - k)
    if n >= t:
      break
    t = n

  print(t)	

### FIXED CODE ###

N, K = input().split()
n = int(N)
k = int(K)

t = n

if n % k == 0:
  print(0)
else:
  if n < k:
    a = abs(n - k)
    b = abs(a-k)
    if a < b:
      print(a)
    else:
      print(b)
  else:
  	x = n % k
  	print(k - x)
### BUGGY CODE ###

import math
from typing import List, Counter, Tuple
from collections import Counter
from itertools import permutations


def read_int() -> int:
    return int(input().strip())


def read_ints() -> List[int]:
    return list(map(int, input().strip().split(' ')))

def lcd(a):
    if len(a) == 1:
        return a[0]
    mid = len(a)//2
    c, d = lcd(a[:mid]), lcd(a[mid:])
    return c*d//math.gcd(c, d)


def solve() -> int:
    modulo = 10**9+7
    N = read_int()
    A = read_ints()
    l = lcd(A)
    return sum((l//a)%modulo for a in A)%modulo


if __name__ == '__main__':
    print(solve())


### FIXED CODE ###

import math
from typing import List, Counter, Tuple
from collections import Counter
from itertools import permutations, zip_longest, groupby


def read_int() -> int:
    return int(input().strip())


def read_ints() -> List[int]:
    return list(map(int, input().strip().split(' ')))

modulo = 10**9+7


def merge(A, start, end, divisors):
    if start == end:
        return Counter(divisors[A[start]])
    mid = start+(end-start)//2
    left = merge(A, start, mid, divisors)
    right = merge(A, mid+1, end, divisors)
    for r in right:
        left[r] = max(left[r], right[r])
    return left

def solve() -> int:
    N = read_int()
    A = read_ints()
    M = 10**6+1
    divisors: List[List[int]] = [[] for _ in range(M)]
    for i in range(2, M):
        if len(divisors[i]) == 0:
            for j in range(i, M, i):
                temp = j
                while temp%i == 0:
                    divisors[j].append(i)
                    temp //= i
    lcd_counter = merge(A, 0, N-1, divisors)
    lcd = 1
    for k in lcd_counter:
        lcd = (lcd*pow(k, lcd_counter[k], modulo))%modulo
    answer = 0
    for a in A:
        answer = (answer+(lcd*pow(a, modulo-2, modulo))%modulo)%modulo
    return answer


if __name__ == '__main__':
    print(solve())
### BUGGY CODE ###

n,m=map(int,input().split())
a=[list(map(int,input().split())) for i in range(m)]
ikeruheya = [[] for i in range(n)]
ans = [0]*(n+1)
check = [0]*n

for i in range(m):
    ikeruheya[a[i][0]-1].append(a[i][1])
    ikeruheya[a[i][1]-1].append(a[i][0])
    
next=[1]
count = 1
while len(next) != 0 and count <= n:
    imaheya = next.pop(0)
    for j in range(len(ikeruheya[imaheya-1])):
        if check[ikeruheya[imaheya-1][j]-1]==0:
            ans[ikeruheya[imaheya-1][j]]= imaheya 
            check[ikeruheya[imaheya-1][j]-1] = 1
            next.append(ikeruheya[imaheya-1][j])
            count += 1
            
print("Yes")
for i in range(2, n+1):
    print(ans[i])

    
    
    


### FIXED CODE ###

from collections import deque
n,m = map(int,input().split())
a=[list(map(int, input().split())) for i in range(m)]
b=[[] for j in range(n)] 

michi=[-1]*(n)
michi[0]=0
heya=[]


for i in range(m):
    b[a[i][0]-1].append(a[i][1])
    b[a[i][1]-1].append(a[i][0])



heya.append(1)


while len(heya):
    now=heya.pop(0)-1
    
    for i in range(len(b[now])):
        if michi[b[now][i]-1] == -1:
            heya.append(b[now][i])
            michi[b[now][i]-1] = now+1
print("Yes")
for i in range(1,n):
    print(michi[i])
### BUGGY CODE ###

from collections import Counter

n = int( input() )
s = []
for i in range(n):
    s.append(str(sorted(list(input()))))

cnt = 0
words = []
for word_cnt in Counter(s).values():
    cnt += word_cnt*(word_cnt-1)//2

print(cnt)

### FIXED CODE ###

from collections import Counter

n = int( input() )
s = []
for i in range(n):
    s.append("".join(sorted(list(input()))))

cnt = 0
words = Counter(s)
for i in words.values():
    cnt += i*(i-1)//2

print(cnt)
### BUGGY CODE ###

import sys
import math

sys.setrecursionlimit(1000000)
input = lambda: sys.stdin.readline().rstrip()

def factorize(x):
    count = {}
    i = 2
    while i * i <= x:
        while x % i == 0:
            x //= i
            count[i] = count.get(i, 0) + 1
        i += 1
    if x > 1:
        count[x] = count.get(x, 0) + 1
    return count


N = int(input())
A = list(map(int, input().split()))

A = list(map(factorize, A))

lcm = {}
for i in A:
    for factor, count in i.items():
        lcm[factor] = max(lcm.get(factor, 0), count)

MOD = 1000000007
ans = 0
for i in A:
    B = 1
    for factor, count in lcm.items():
        B *= pow(factor, count - i.get(factor, 0), MOD)
        B % MOD
    ans = (ans + B) % MOD
print(ans)

### FIXED CODE ###

import sys
import math

sys.setrecursionlimit(1000000)
input = lambda: sys.stdin.readline().rstrip()


def inverse(x, mod):
    return pow(x, mod - 2, mod)


def factorize(x):
    count = {}
    i = 2
    while i * i <= x:
        while x % i == 0:
            x //= i
            count[i] = count.get(i, 0) + 1
        i += 1
    if x > 1:
        count[x] = count.get(x, 0) + 1
    return count


N = int(input())
A = list(map(int, input().split()))

A = list(map(factorize, A))

lcm = {}
for i in A:
    for factor, count in i.items():
        lcm[factor] = max(lcm.get(factor, 0), count)

MOD = 1000000007

lcm_int = 1
for factor, count in lcm.items():
    lcm_int *= pow(factor, count, MOD)
    lcm_int %= MOD

ans = 0
for i in A:
    B = lcm_int
    for factor, count in i.items():
        B *= inverse(pow(factor, count, MOD), MOD)
        B % MOD
    ans = (ans + B) % MOD
print(ans)