Harryxun/stf_run huggingface dataset:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time


def I(): return int(input())


def S(): return input()


def MI(): return map(int, input().split())


def MS(): return map(str, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


yn = {False: 'No', True: 'Yes'}
YN = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']

show_flg = False
# show_flg = True


def main():
    N = I()
    a = LI()
    dp = [0] * N
    dp[1] = max(a[0], a[1])
    c = a[0]

    for i in range(2, n):
        if i % 2 == 0:
            c += a[i]
            dp[i] = max(dp[i-2] + a[i], dp[i-1])
        else:
            dp[i] = max(dp[i-2] + a[i], c)

    print(dp[-1])


if __name__ == '__main__':
    main()


### FIXED CODE ###

from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time


def I(): return int(input())


def S(): return input()


def MI(): return map(int, input().split())


def MS(): return map(str, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


yn = {False: 'No', True: 'Yes'}
YN = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']

show_flg = False
# show_flg = True


def main():
    N = I()
    a = LI()
    dp = [0] * N
    dp[1] = max(a[0], a[1])
    c = a[0]

    for i in range(2, N):
        if i % 2 == 0:
            c += a[i]
            dp[i] = max(dp[i-2] + a[i], dp[i-1])
        else:
            dp[i] = max(dp[i-2] + a[i], c)

    print(dp[-1])


if __name__ == '__main__':
    main()
from collections import deque

s=input()
s=deque(s)
q=int(input())
ans=''
flg=False
for _ in range(q):
	flg=False
	query=list(map(str,input().split()))
	if query[0]=='1':
		flg=True
	else:
		if flg:
			s.reverse()
		if query[1]=='1':
			s.appendleft(query[2])
		else:
			s.append(query[2])
if flg:
	s=s[::-1]

print(''.join(s))

### FIXED CODE ###

from collections import deque

s=input()
s=deque(s)
q=int(input())
ans=''
flg=0
for _ in range(q):
	query=list(map(str,input().split()))
	if query[0]=='1':
		flg=1-flg
	else:
		if flg:
			if query[1]=='1':
				s.append(query[2])
			else:
				s.appendleft(query[2])
		else:
			if query[1]=='1':
				s.appendleft(query[2])
			else:
				s.append(query[2])
if flg:
	t=[]
	for i in range(len(s)):
		t.append(s.pop())
	print(''.join(t))
else:
    print(''.join(s))
x = int(input())
a = [input() for i in range(x)]
y = int(input())
b = [input() for h in range(y)]

count_max = 0
for j in a:
  if a.count(j) - b.count(j) > count_max:
    a.count(j) - b.count(j) = count_max
print(count_max)

### FIXED CODE ###

x = int(input())
a = [input() for _ in range(x)]
y = int(input())
b = [input() for _ in range(y)]

count_max = 0
for j in a:
  if (a.count(j) - b.count(j)) > count_max:
    count_max = a.count(j) - b.count(j)
print(count_max)
k=int(input())
a,b=map(int,input().split())
for i in range(a,b+1):
  if i%k==0:
    print 'OK'
  
  else:
    print 'NG'

### FIXED CODE ###

k=int(input())
a,b=map(int,input().split())
ans='NG'
if b-a-1>=k:
  ans='OK'
else:
  for i in range(a,b+1):
    if i%k==0:
      ans='OK'
      break
print(ans)
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n = ni()
print(m*(m-1)//2-m//2)

for i in range(n):
    a = n-1-i if n%2 == 0 else n-2-i
    for j in range(i,n):
        if j != a:
            print(i+1,j+1)

### FIXED CODE ###

import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n = ni()
print(n*(n-1)//2-n//2)

for i in range(n):
    a = n-1-i if n%2 == 0 else n-2-i
    for j in range(i+1,n):
        if j != a:
            print(i+1,j+1)
f=0
s=list(input())
for i in range(len(s)):
    if i%2==1:
        if s[i]!=i:
            f=1
            print('No')
            break
    else:
        if s[i]!=h:
            f=1
            print('No')
            break
if f==0:
    print('Yes')

### FIXED CODE ###

f=0
s=list(input())
if len(s)%2==1:
    f=1
else:
    for i in range(len(s)):
        if i%2==1:
            if s[i]!='i':
                f=1
                break
        else:
            if s[i]!='h':
                f=1
                break
if f==0:
    print('Yes')
else:
    print('No')
N , Y= map(int,input().split())

for i in range(N + 1):
    a = N + 1
    b = a - i
    for j in range(b):
        c = b - j
        kingaku += 1000 * c + 5000 * b + 10000 * a
        if kingaku == Y:
            print(a,b,c)
          
            break
    else:
        continue
    break
                   
                
    kingaku = 0

else:
    print(-1,-1,-1)
    

### FIXED CODE ###

N , Y= map(int,input().split())

for a in range(N + 1):
    be = N - a 
    for b in range(be + 1):
        c = N - b - a
        kingaku = 1000 * c + 5000 * b + 10000 * a

        if kingaku == Y:
            print(a,b,c)
          
            break
    else:
        continue
    break
                   

else:
    print(-1,-1,-1)
import sys


sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def main():
    S = input()
    N = len(S)
    dp = [[0] * 13 for _ in range(N)]

    if S[0] == "?":
        for i in range(10):
            dp[0][i] = 1
    else:
        dp[0][int(S[-1])] = 1

    for i in range(1, N):
        if S[N - i - 1] != "?":
            for k in range(13):
                j = int(S[N - i - 1])
                idx = (k + j * (10 ** i)) % 13
                dp[i][idx] += dp[i - 1][k]
                dp[i][idx] %= MOD
        else:
            for j in range(10):
                for k in range(13):
                    idx = (k + j * (10 ** i)) % 13
                    dp[i][idx] += dp[i - 1][k]
                    dp[i][idx] %= MOD

    print(dp[-1][5])


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys


sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def main():
    S = input()
    N = len(S)
    dp = [[0] * 13 for _ in range(N)]

    if S[-1] == "?":
        for i in range(10):
            dp[0][i] = 1
    else:
        dp[0][int(S[-1])] = 1

    tenfactor = 1
    for i in range(1, N):
        tenfactor *= 10
        tenfactor %= 13

        if S[N - i - 1] != "?":
            for k in range(13):
                j = int(S[N - i - 1])
                idx = (k + j * tenfactor) % 13
                dp[i][idx] += dp[i - 1][k]
                dp[i][idx] %= MOD
        else:
            for j in range(10):
                for k in range(13):
                    idx = (k + j * tenfactor) % 13
                    dp[i][idx] += dp[i - 1][k]
                    dp[i][idx] %= MOD

    print(dp[-1][5])


if __name__ == "__main__":
    main()
from sys import setrecursionlimit

def read_key():
    a, _ = map(int, input().split())
    m = 0
    for c in map(int, input().split()):
        m |= 1 << (c - 1)
    return (a, m)

def solve(keys, amount, cm, dp):
  if cm == (1 << N) - 1:
    return amount
  if len(keys) == 0:
    return INF
  a, m = keys[0]
  if dp[cm | m] < amount + a:
    return solve(keys[1:], amount, cm, dp)
  else:
    dp[cm | m] = amount + a
    return min(solve(keys[1:], amount + a, cm | m, dp), solve(keys[1:], amount, cm, dp))

setrecursionlimit(1000000)
INF = float('inf')

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

dp = [INF] * (1 << N)
t = solve(keys, 0, 0, dp)
if t == INF:
  print(-1)
else:
  print(t)


### FIXED CODE ###

from fractions import gcd
from math import sqrt


def prime_factorize(n):
    result = []
    for i in range(2, int(sqrt(n)) + 1):
        if n % i != 0:
            continue
        t = 0
        while n % i == 0:
            n //= i
            t += 1
        result.append((i, t))
        if n == 1:
            break
    if n != 1:
        result.append((n, 1))
    return result


A, B = map(int, input().split())
print(len(prime_factorize(gcd(A, B))) + 1)
r,c=map(int, input().split())
for i in range(c):
    a=list(map(int, input().split()))
    a.append(sum(a))
    print(*a)


### FIXED CODE ###

r,c=map(int, input().split())
total=[0]*(c+1)
for i in range(r):
    a=list(map(int, input().split()))
    a.append(sum(a))
    print(*a)
    for j in range(c+1):
        total[j]+=a[j]
print(*total)
n = int(input())
x = list(map(int, input().split()))
a = []
for i in range(min(x), max(x)+1):
    ans = 0
    for p in x:
        ans += (p - i) ** 2
    a.append(ans)
print(min(a))

### FIXED CODE ###

n,k,q = map(int,input().split())
a = [int(input()) for i in range(q)]
player_point = [q]*n
 
for i in range(q):
    player_point[a[i]-1] -= 1
 
for i in range(n):
    if player_point[i] < k:
        print('Yes')
    else:
        print('No')
N, P = map(int, raw_input().split())
i = 2
res = 1
if N == 1:
    print P
else:
    while i ** N <= P:
        if P % (i ** N) == 0:
            res = i
        i += 1
    print res


### FIXED CODE ###

N = raw_input()
print len([i for i in N if i == '2'])
#!/usr/bin/env python3

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


set_odd = set()
set_even = set()

for i in a:
    if i % 2 == 1:
        set_odd.add(i)
    else:
        set_even.add(i)

if len(set_odd) >= 2:
    print(1)
    exit()
elif len(set_odd) == 1:
    if len(set_even) >= 1:
        print(1)
        exit()
    else:
        print(min(set_odd))

# only even number
min_a = min(set_even)
set_even = list(set_even)

ans = []

for i in range(len(a)):
    ans_tmp = a[i] % min_a
    if ans_tmp != 0:
        ans.append(ans_tmp)
    if min_a-ans_tmp != 0:
        ans.append(min_a-ans_tmp)

print(min(ans))


### FIXED CODE ###

#!/usr/bin/env python3

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


value = a[0]
for i in range(1, n):
    value = fractions.gcd(value, a[i])
print(value)
# E
import math
N = int(input()) 
A = list(map(int, input().split()))

lcm = np.lcm.reduce(A)

ans = 0
for i in A:
    ans += (lcm//i) % (10**9+7)

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

### FIXED CODE ###

# E
from fractions import gcd

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

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

mod = 10**9+7

ans = 0
for i in A:
    ans += value // i

print(ans%mod)
S=input()
for i in range(3):
  if s[i]==s[i+1]:
    print('Bad')
    exit(0)
print('Good')

### FIXED CODE ###

S=input()
for i in range(3):
  if S[i]==S[i+1]:
    print('Bad')
    exit(0)
print('Good')
print('A%sC'%'BR'[id('A')%3])

### FIXED CODE ###

print(*{'ABC','ARC'}-{input()})
a,b=[int(i) for i in input().sprit()]
if b>=a:
  print(a)
else:
  print(a-1)

### FIXED CODE ###

a,b=[int(i) for i in input().split()]
if b>=a:
  print(a)
else:
  print(a-1)
import sys
inputs = sys.stdin.readlines()

n, q = list(map(int, inputs[0].split()))
edges = []
for i in range(n-1):
    edges.append(tuple(map(int, inputs[i+1].split())))
p_x_list = []
for i in range(q):
    p_x_list.append(tuple(map(int, inputs[n+i].split())))
n, q
edges
p_x_list

from collections import deque, defaultdict

def dfs_generator(nodes, start):
    nexts = deque([start])
    while nexts:
        node = nexts.popleft()
        nexts.extend(nodes[node]['childs'])
        yield node

nodes = dict({1: dict({'val': 0, 'parent': 0, 'childs': []})})
for from_, to_ in edges:
    nodes[from_]['childs'].append(to_)
    nodes[to_] = dict({'val': 0, 'parent': from_, 'childs': []})

part_tree_roots = set([p for p, x in p_x_list])

part_tree = defaultdict(list)
for r in part_tree_roots:
    gen = dfs_generator(nodes, r)
    try:
        while True:
            part_tree[r].append(next(gen))
    except StopIteration:
        pass

for p, x in p_x_list:
    for i in part_tree[p]:
        nodes[i]['val'] += x

for i in range(n-1):
    print(str(nodes[i+1]['val']), end=' ')
print(str(nodes[i+2]['val']))


### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N,Q = map(int,readline().split())
ABPX = list(map(int,read().split()))
AB = iter(ABPX[:N+N-2])
PX = iter(ABPX[N+N-2:])

graph = [[] for _ in range(N+1)]
for a,b in zip(AB,AB):
    graph[a].append(b)
    graph[b].append(a)

val = [0] * (N+1)
for p,x in zip(PX,PX):
    val[p] += x

stack = [1]

parent = [0] * (N+1)
while stack:
    x = stack.pop()
    for y in graph[x]:
        if y == parent[x]:
            continue
        parent[y] = x
        stack.append(y)
        val[y] += val[x]

print(' '.join(map(str,val[1:])))
s=[input() for _ in range(input())]
t=[input() for _ in range(input())]
l=list(set(n))
#s内の重複消去　リストに変更
print(max(0,max(n.count(l[i])-m.count(l[i]) for i in range(len(l)))))

### FIXED CODE ###

N=int(input())
s=[input() for _ in range(N)]
M=int(input())
t=[input() for _ in range(M)]
def ans1(x):
    return s.count(x)-t.count(x)
ans2=0
ans_1=0
for S in s:
    if ans1(S)>0 and ans1(S)>ans2:
            ans2=ans1(S)
if ans2>=0:
    print(ans2)
else:
    print("0")
n=int(input());A=[int(input()) for _ in range(n)];A.sort();if n%2==1:print(max(2*sum(x[n-n//2:])-sum(x[n-n//2-2:n-n//2])-2*sum(x[:n-n//2-2]),-2*sum(x[:n//2])+sum(x[n//2:n//2+2])+2*sum(x[n//2+2:])));else:print(-2*sum(A[:(n-2)//2])-A[(n-2)//2]+A[(n-2)//2+1]+2*sum(A[(n-2)//2+2:]))

### FIXED CODE ###

n = int(input())
A = [int(input()) for _ in range(n)]
A.sort()
if n%2==1:print(max(2*sum(A[n-n//2:])-sum(A[n-n//2-2:n-n//2])-2*sum(A[:n-n//2-2]),-2*sum(A[:n//2])+sum(A[n//2:n//2+2])+2*sum(A[n//2+2:])))
else:print(-2*sum(A[:(n-2)//2])-A[(n-2)//2]+A[(n-2)//2+1]+2*sum(A[(n-2)//2+2:]))
tmp = list(map(int, input().split()))
n = tmp[0]
d = tmp[1]

x = [[0] * d for i in range(n)]
for i in range(n):
  tmp = list(map(int, input().split()))
  for j in range(d):
    x[i][j] = tmp[j]

cnt = 0
for i in range(n):
  for j in range(i+1, n):
    len = 0
    for k in range(d):
      len += (x[i][k] - x[j][k]) ** 2
    len = math.sqrt(len)
#    print('I=' + str(i) + ' J=' + str(j) + ' LEN=' + str(len))
    if len.is_integer():
      cnt += 1

print (cnt)

### FIXED CODE ###

import math

tmp = list(map(int, input().split()))
n = tmp[0]
d = tmp[1]

x = [[0] * d for i in range(n)]
for i in range(n):
  tmp = list(map(int, input().split()))
  for j in range(d):
    x[i][j] = tmp[j]

cnt = 0
for i in range(n):
  for j in range(i+1, n):
    len = 0
    for k in range(d):
      len += (x[i][k] - x[j][k]) ** 2
    len = math.sqrt(len)
#    print('I=' + str(i) + ' J=' + str(j) + ' LEN=' + str(len))
    if len.is_integer():
      cnt += 1

print (cnt)
a,b,k=map(int, input().split())

l = list(range(a,b+1))

x = list()
for i in range(0, min([k,len(l)])):
  x.append(l[i])
  x.append(l[-i-1])

for xx in sorted(set(x)):
  print(xx)


### FIXED CODE ###

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

x = list()
for i in range(a, a+min([k,b+1-a])):
  #print(i)
  x.append(i)
#print('---')
for i in range(b-min([k,b+1-a])+1, b+1):
  #print(i)
  x.append(i)
#print('---')

for xx in sorted(set(x)):
  print(xx)
A = int(input())
B = int(input())

temp = list(A,B)

for i in range(1,4):
  if i not in temp:
    print(i)

### FIXED CODE ###

import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

A,B = map(int, read().split())
temp = [A,B]
 
for i in range(1,4):
  if i not in temp:
    print(i)
if c=="X" or c!=c0:
    return 0
  else:
    return 0
    A[y][x]="X"
    for i,j in [[0,-1],[0,1],[-1,0],[1,0]]:
      f(y+i,x+j,c0)
    return 1

while 1:
  H,W=map(int,raw_input().split())
  if H==W==0: break
  A=[["X" for _ in range(W+2)] for _ in range(H+2)]
  for i in range(H):
    s=raw_input()
    for j in range(W): A[i+1][j+1]=s[j]
  c=0
  for i in range(1,H+1):
    for j in range(1,W+1):
      c+=f(i,j,A[i][j])
  print c

### FIXED CODE ###

def f(y,x,a):
  M.append([y,x])
  while M:
    y,x=M.pop()
    if A[y][x]==a:
      A[y][x]=' '
      for i,j in [[0,-1],[-1,0],[0,1],[1,0]]: M.append([y+i,x+j])
  return 1

M=[]
while 1:
  H,W=map(int,raw_input().split())
  if H==W==0: break
  A=[list(' '*(W+2)) for _ in range(H+2)]
  for i in range(H): A[i+1][1:W+1]=list(raw_input())
  c=0
  for i in range(1,H+1):
    for j in range(1,W+1):
      a=A[i][j]
      if a!=' ': c+=f(i,j,a)
  print c
n = int(input())
a_list = list(map(int,input().split()))

a_set = set(a_slit)
if len(a_list) == len(set):
    print('YES')
else:
    print('NO')

### FIXED CODE ###

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

a_set = set(a_list)
if len(a_list) == len(a_set):
    print('YES')
else:
    print('NO')
s=str(input())
if s='Sunny':
    print('Cloudy')
elif s='Cloudy':
    print('Rainy')
else:
    print('Sunny')

### FIXED CODE ###

s=str(input())
if s=='Sunny':
    print('Cloudy')
elif s=='Cloudy':
    print('Rainy')
else:
    print('Sunny')
x,y,z = map(int,input())
if(x+y+z>=22):
    print("bust")
else:
  print("win")

### FIXED CODE ###

x,y,z = map(int,input().split())
if(x+y+z>=22):
    print("bust")
else:
  print("win")
S = input(), T = input()
A,B = map(int,input().split())	
U = input()

if S == U:
    A -= 1
    print(A,B)
else:
    B -= 1
    print(A,B)

### FIXED CODE ###

li = input().split()
A,B = map(int,input().split())	
U = input()

if li[1] == U:
    B -= 1
    print(A,B)
else:
    A -= 1
    print(A,B)
from math import gcd

def lcm(a,b):
    return a*b//gcd(a,b)

A,B,C,D = [int(zz) for zz in input().split()]

bc = B//C
ac = (A-1)//C
bd = B//D
ad = (A-1)//D
bcd = B//lcm(C,D)
acd = (A-1)//lcm(C,D)

print(B-A-bc+ac-bd+ad+bcd-acd+1)


### FIXED CODE ###

A,B,C,D = [int(i) for i in input().split()]

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

def lcm(a,b):
    return a*b//gcd(a,b)

E = lcm(C,D)

p = B-A+1

ac = p//C
if A%C+p%C >= C+1:
    ac += 1

ad = p//D
if A%D+p%D >= D+1:
    ad += 1

ae = p//E
if A%E+p%E >= E+1:
    ae += 1

print(p-(ac+ad-ae))
N = int(input())
L = [0] * (N + 1)
L[0] = 2
L[1] = 1

if N ==1:
    print(L[1])
for i in range(2, N + 1):
    L[i] = L[i - 2] + L[i - 1]

print(L[i])

### FIXED CODE ###

N = int(input())
L = [0] * (N + 1)
L[0] = 2
L[1] = 1

if N ==1:
    print(L[1])
    exit()
for i in range(2, N + 1):
    L[i] = L[i - 2] + L[i - 1]

print(L[i])
n,a,b = map(int,input().split())

MOD = 10**9 + 7
m = 2*10**5
mm = 2** m

ans = 1
for _ in range(n // m):
  ans = (ans * mm) % MOD

ans = (ans * 2**(n % m)) % MOD  
    
ans = (ans - 1) % MOD

ans = (ans - cmb(n,a,MOD))%MOD
ans = (ans - cmb(n,b,MOD))%MOD

print(ans)

### FIXED CODE ###

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

MOD = 10**9+7

def cmb(n,r,mod):        
    ret=1
    div = min(r,n-r)
    for i in range(div):        
        ret=ret*(n-i)*pow(div-i,mod-2,mod)%mod
        
    return ret % mod

ans = 1
ans = ans * pow(2,n,MOD)
ans = (ans - 1) % MOD

ans = (ans - cmb(n,a,MOD))%MOD
ans = (ans - cmb(n,b,MOD))%MOD

print(ans)
import math
a=int(input())
b=int(input())
x=int(input())
print(math.ceil(x/(max(a,b)))

### FIXED CODE ###

import math
a=int(input())
b=int(input())
x=int(input())
print(math.ceil(x/max(a,b)))
m=int(input())
n=int(input())
print(round((n/m)+0.4))

### FIXED CODE ###

import math
A, B = input().split()
A = int(A)
B = int(B)
n = math.ceil((B-1)/(A-1))
print(n)
import math

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

mod = 10 ** 9 + 7

lcm = a[0]
for i in range(1, n):
  lcm = lcm * a[i] // math.gcd(lcm, a[i])

answer = 0
for x in a:
  answer = (answer + lcm // x) % mod
print(answer)


### FIXED CODE ###

# import math
# import fractions

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

mod = 10 ** 9 + 7


def prime_factorize(n):
    a = {}
    while n % 2 == 0:
        if 2 not in a:
          a[2] = 0
        a[2] += 1
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            if f not in a:
              a[f] = 0
            a[f] += 1
            n //= f
        else:
            f += 2
    if n != 1:
      if n not in a:
        a[n] = 0
      a[n] += 1
    return a


# 最小公倍数を素因数分解した形で持つ
l = prime_factorize(a[0])
# print(l)
# xs = {}
# xs[a[0]] = prime_factorize(a[0])
for i in range(1, n):
  ps = prime_factorize(a[i])
  # print(ps)
  # xs[a[i]] = ps
  for k, v in ps.items():
    if k in l:
      l[k] = max(v, l[k])
    else:
      l[k] = v

# print(l)
# print(xs)

L = 1
for k, v in l.items():
  L = L * pow(k, v, mod) % mod

answer = 0
for x in a:
  answer = (answer + L * pow(x, mod - 2, mod)) % mod
print(answer)
n = int(input())
dp = [None] * (1 << n)
dp[0] = 1
now = [0]
for _ in range(n):
    A = list(map(int, input().split()))
    next = []
    for i in range(n):
        if not A[i]:
            continue
        for U in now:
            if (U >> i) & 1:
                continue
            nU = U | 1 << i
            if dp[nU] is None:
                dp[nU] = dp[U]
                next.append(nU)
            else:
                dp[nU] += dp[U]
                if dp[nU] >= MOD:
                    dp[nU] -= MOD
    now = next

res = dp[-1]
if res is None:
    res = 0
print(res)

### FIXED CODE ###

import sys
sys.setrecursionlimit(2147483647)
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
input = lambda:sys.stdin.readline().rstrip()
def resolve():
    n = int(input())
    popcount_to_state = [[] for _ in range(n + 1)]
    for U in range(1 << n):
        popcount_to_state[bin(U).count('1')].append(U)

    dp = [0] * (1 << n)
    dp[0] = 1
    for i in range(n):
        A = tuple(map(int, input().split()))
        for j in range(n):
            if not A[j]:
                continue
            for U in popcount_to_state[i]:
                if (U >> j) & 1:
                    continue
                nU = U | 1 << j
                dp[nU] += dp[U]
                if dp[nU] >= MOD:
                    dp[nU] -= MOD
    print(dp[-1])
resolve()
N, K = [int(x) for x in input().split(" ")]
lst = [int(x) for x in input().split(" ")]

dic= {}
cnt = 0 
swap = 0
prep = len(set(lst))-K

for i in range(1,N+1):
	dic["{}".format(i)] = 0
	dic["{}".format(lst[i-1])] += 1

sorted_dic = sorted(dic.items(), key = lambda x : x[1])
    
for i in range(0,N):
  swap += sorted_dic[i][1]
  if sorted_dic[i][1] != 0:
    cnt +=1
  if cnt >= prep:
    break
      
print(swap)

### FIXED CODE ###

N, K = [int(x) for x in input().split(" ")]
lst = [int(x) for x in input().split(" ")]

dic= {}
cnt = 0 
swap = 0
prep = len(set(lst))-K

for i in range(1,N+1):
	dic["{}".format(i)] = 0

for i in range(0,N):
	dic["{}".format(lst[i])] += 1

sorted_dic = sorted(dic.items(), key = lambda x : x[1])
    
for i in range(0,N):
  swap += sorted_dic[i][1]
  if sorted_dic[i][1] != 0:
    cnt +=1
  if cnt >= prep:
    break
      
print(swap)
x, n = map(int, input().split())
p = [int(_) for _ in input().split()]

not_in_p = [i for i in range(0, 102) if i not in p]
nip_temp = list(map(lambda s: abs(x - s), not_in_p))

address = nip_temp.index(min(nip_temp))
print(p[address])


### FIXED CODE ###

x, n = map(int, input().split())
p = [int(_) for _ in input().split()]

not_in_p = [i for i in range(0, 102) if i not in p]
nip_temp = list(map(lambda s: abs(x - s), not_in_p))

address = nip_temp.index(min(nip_temp))
print(not_in_p[address])