Harryxun/stf_run huggingface dataset:
n,m=map(int, input().split())
e=[[] for _ in range(n)]
e_rev=[[] for _ in range(n)]
for i in range(m):
    ai,bi=map(int, input().split())
    e[ai].append(bi)
    e_rev[bi].append(ai)

p_ord=[]
used=[0]*n
def dfs(v):
    used[v]=1
    for u in e[v]:
        if not used[u]:
            dfs(u)
    p_ord.append(v)
for i in range(n):
    if not used[i]:
        dfs(i)
compo = [0]*n
used=[0]*n
def dfs_rev(v,c):
    compo[v]=c
    used[v]=1
    for u in e_rev[v]:
        if not used[u]:
            dfs_rev(u,c)
cnt=0
for i in reversed(p_ord):
    if not used[i]:
        dfs_rev(i,cnt)
        cnt+=1
cc=[[] for _ in range(cnt)]
for i in range(n):
    cc[compo[i]].append(i)
print(len(cc))
for cci in cc:
    print(len(cci),*cci)

### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)
n,m=map(int, input().split())
e=[[] for _ in range(n)]
e_rev=[[] for _ in range(n)]
for i in range(m):
    ai,bi=map(int, input().split())
    e[ai].append(bi)
    e_rev[bi].append(ai)

p_ord=[]
used=[0]*n
def dfs(v):
    used[v]=1
    for u in e[v]:
        if not used[u]:
            dfs(u)
    p_ord.append(v)
for i in range(n):
    if not used[i]:
        dfs(i)
compo = [0]*n
used=[0]*n
def dfs_rev(v,c):
    compo[v]=c
    used[v]=1
    for u in e_rev[v]:
        if not used[u]:
            dfs_rev(u,c)
cnt=0
for i in reversed(p_ord):
    if not used[i]:
        dfs_rev(i,cnt)
        cnt+=1
cc=[[] for _ in range(cnt+1)]
for i in range(n):
    cc[compo[i]].append(i)

print(len([cci for cci in cc if cci]))
for cci in cc:
    if cci:
        print(len(cci),*cci)
n = int(input())
A_list = list(map(int, input().split()))
for i in range(n):
    A_list[i] -= i
A_list.sort()
A_cum = [0] * n
for i in range(n):
    if i == 0:
        A_cum[0] = A_list[0]
    else:
        A_cum[i] = A_cum[i-1] + A_list[i]
def findinfindex(sortedlist, key, l, r):
    if r - l <= 0:
        return l
    m = (l+r+1)//2
    if sortedlist[m] > key:
        return findinfindex(sortedlist, key, l, m-1)
    else:
        return findinfindex(sortedlist, key, m, r)
sadmin = -1
for b in range(A_list[n//2],A_list[(n+1)//2]+1):
    lastminus = findinfindex(A_list, b, 0, n-1)
    sadness = (2*lastminus - n + 2)*b - 2*A_cum[lastminus] + A_cum[n-1]
    if sadmin == -1:
        sadmin = sadness
    elif sadness < sadmin:
        sadmin = sadness
    else:
        break
print(sadmin)


### FIXED CODE ###

n = int(input())
A_list = list(map(int, input().split()))
for i in range(n):
    A_list[i] -= i
A_list.sort()

def sadness(a, mid):
    sad = 0
    for i in range(mid):
        sad += a[mid] - a[i]
    for i in range(mid+1,len(a)):
        sad += a[i] - a[mid]
    return sad

if n % 2 != 0:
    print(sadness(A_list, n//2))
else:
    print(min(sadness(A_list, n//2), sadness(A_list, n//2+1)))
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n;
    vector<string> s;
    s = {"p","p","h","b","h","h","p","h","p","h"};
    cin >> n;
    int x = n%10;
    cout << s[x] << "on" << endl;
}

### FIXED CODE ###

n = input()
x = int(n[-1])
if x in [2,4,5,7,9]:
    print("hon")
elif x in [0,1,6,8]:
    print("pon")
elif x == 3:
    print("bon")
import numpy as np
N, K = map(int, input().split())

A = []
for i in range(K):
    d = int(input())
    temp = list(map(int, input().split()))
    A = A + temp

hito = np.ones(N)
for i in range(len(A)):
    hito[A[i]] = 0
print(int(np.sum(hito)))

### FIXED CODE ###

import numpy as np

N, K = map(int, input().split())
A = []
for i in range(K):
    d = int(input())
    temp = list(map(int, input().split()))
    A = A + temp
hito = np.ones(N)
for i in range(len(A)):
    hito[A[i]-1] = 0
print(int(np.sum(hito)))
import math
n=int(input())
lst=list(map(int,input().split()))
xlst=list(reversed(lst))
#1~5と6のgcdは1~6のgcd
#i番目の左側と右側のgcdを求める
#left[i-1]はlstのi番目までのgcd
#xright[i]はlstのnからi-
#lstのi+1番目は右から見たらn-i+1番目



left=[lst[0]]
xright=[lst[n-1]]
for i in range(1,len(lst)):
    left.append(math.gcd(left[i-1],lst[i]))

for i in reversed(range(0,len(lst)-1)):

    xright.append(math.gcd(xright[n-i-2],lst[i]))


#i-1番目までの左からのgcdはleft[i-2]
#i＋1番目以上のgcdは right[i+2]
result=1
for i in range(n):
    a=math.gcd(left[i-1],xright[i-1])
    if a>result:
        result=a
print(result)


### FIXED CODE ###

import fractions
n=int(input())
lst=list(map(int,input().split()))
xlst=list(reversed(lst))
#1~5と6のgcdは1~6のgcd
#i番目の左側と右側のgcdを求める
#left[i-1]はlstのi番目までのgcd
#xright[i]はlstのnからi-
#lstのi+1番目は右から見たらn-i+1番目



left=[lst[0]]
xright=[lst[n-1]]
for i in range(1,len(lst)):
    left.append(fractions.gcd(left[i-1],lst[i]))

for i in reversed(range(0,len(lst)-1)):
    xright.append(fractions.gcd(xright[n-i-2],lst[i]))


#i-1番目までの左からのgcdはleft[i-2]
#i＋1番目以上のgcdは right[i+2]
result=1
for i in range(1,n-1):
    a=fractions.gcd(left[i-1],xright[n-i-2])
    if a>result:
        result=a
print(max(result,xright[n-2],left[n-2]))
while True:
    n = int(input())
    if n == 0:
        break
    a = list(map(int, input().split()))
    l = []
    for i in range(1, len(a)):
        for j in range(i+1,len(a)):
            l.append(abs(a[i]-a[j]))
    print(min(l))



### FIXED CODE ###

while True:
    n = int(input())#人数の受け取り
    if n == 0:#０人or何も入力しないなら終了
        break
    a = list(map(int, input().split()))#各人の成績の受け取り
    l = list()#出力の受け取り用
    for i in range(0, n):#成績の比較
        for j in range(0, n):
            if i == j:
                continue
            l.append(abs(a[i]-a[j]))#絶対値を受け取り用のlistに入力
    else:#listが完成したら
        print(min(l))#成績の一番近い生徒の差を出力
X,N = map(int,input().split())
p = [int(i) for i in input().split()]
if N==0:
    print(X)
else:
    pN=[]
    for j in range(N):
        pj = p[j]-X
        pN.append(pj)
    pN.sort()
    p0 = pN[0]-1
    p1 = pN[N-1]+1
    list_p = list(range(p0,p1+1,1))
    result = list(set(list_p)-set(pN))
    k0 = abs(result[0])
    for k in result:
        k1 = abs(k)
        if k1<k0:
            k0 = k1
for l in result:
    if l == (-1)*k0:
        print(X-k0)
        break
else:
    print(X+k0)

### FIXED CODE ###

X,N = map(int,input().split())
p = [int(i) for i in input().split()]
if N==0:
    print(X)
else:
    pN=[]
    for j in range(N):
        pj = p[j]-X
        pN.append(pj)
    pN.sort()
    p0 = pN[0]-1
    p1 = pN[N-1]+1
    list_p = list(range(p0,p1+1,1))
    result = list(set(list_p)-set(pN))
    k0 = abs(result[0])
    for k in result:
        k1 = abs(k)
        if k1<k0:
            k0 = k1
    cnt = 0
    for l in result:
        if l == (-1)*k0:
            cnt+=1
    if cnt==0:
        print(X+k0)
    else:
        print(X-k0)
N, M = map(int, input().split())
A = list(map(int, input().split()))

A.sort(reverse = True)

n = 0
if N > 1:
    while not M == 0:

        while A[0] >= A[1]:
            A[n] //= 2
            M -= 1
            if M == 0:
                break
                
        if M == 0:
            break

        i = 0
        while A[i] < A[i+1]:
            A[i], A[i+1] = A[i+1], A[i]
            i += 1
            if i == N:
                break


else:
    A[0] //= (2**M)


result = sum(A)
print(result)


### FIXED CODE ###

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

for i in range(len(A)):
    A[i] *= -1

import heapq

heapq.heapify(A)


for _ in range(M):
    a = heapq.heappop(A)
    heapq.heappush(A, ((a*(-1))//2)*(-1))


result = -sum(A)
print(result)
import math
import copy

n=int(input())
a=list(map(int,input().split()))
ch5=0
if M in a:
  if M==1:
    ch5+=1
    a.remove(M)
if ch5>0:
  a.append(1)
B=copy.deepcopy(a)


dp=[0 for _ in range(1000000+1)]

sosuu = [2]
A = 1000
for L in range(3, A, 2): # 2 以外の素数は奇数なので
    for L2 in sosuu:
        if L % L2 == 0:
            break # 素数でないことがわかったらそれ以上ループする必要はない
    else: # break で抜けることがなかったら L は素数（Python 特有の制御構文）
        sosuu.append(L)
        

if len(a)>80000:
  g=a[0]
  for h in range(1,n):
    g=math.gcd(g,a[h])
    
  if g==1:
    print('setwise coprime')
    
  else:
    print('not coprime')
  
  

else:
  ch1=0
  ch3=0
  for w in sosuu:
    ch2=0
    for q in range(n):
      if B[q]%w==0:
        ch2+=1
        S=B[q]
        while S%w==0:
          S=S//w
        B[q]=S
    if ch2>1:
      ch3+=1
  d={}
  ch4=0
  for u in B:
      if u>1000:
        if u not in d:
          d[u]=0
        else:
          ch4+=1
  if ch3==0 and ch4==0:
    print('pairwise coprime')
    
      
  
  
    
  else:
    g=a[0]
    for h in range(1,n):
      g=math.gcd(g,a[h])
    
    if g==1:
      print('setwise coprime')
    
    else:
      print('not coprime')
      
     

### FIXED CODE ###

import math

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

dp=[0 for _ in range(1000001)]

for d in a:
  dp[d]+=1
  
ch1=0
for i in  range(2,1000001):
  ch=0
  x=i
  while x<=1000000:
    ch+=dp[x]
    x+=i
  if ch>1:
    ch1+=1
    
if ch1==0:
  print('pairwise coprime')
  
else:
  g=a[0]
  for h in range(1,n):
    g=math.gcd(g,a[h])
    
  if g==1:
    print('setwise coprime')
    
  else:
    print('not coprime')
s = input()
a = int(s[:2])
b = int(s[2:])
if a <= 12 && a > 0:
	if b <=12 and b > 0:
		print('AMBIGUOUS')
	else:
		print('MMYY')
else:
	if b <=12 and b > 0:
		print('YYMM')
	else:
		print('NA')

### FIXED CODE ###

s = input()
a = int(s[:2])
b = int(s[2:])
if a <= 12 and a > 0:
	if b <=12 and b > 0:
		print('AMBIGUOUS')
	else:
		print('MMYY')
else:
	if b <=12 and b > 0:
		print('YYMM')
	else:
		print('NA')
# PROXY

import math
N, M = [int(i) for i in input().split()]
list = i = [int(input()) for i in range(M)]
Nlist = []
counter = 1
while counter < M:
    Diff_id = list[counter] - list[counter - 1]
    Nlist.append(Diff_id - 2 if Diff_id != 1 else -1)
    counter += 1
Nlist.insert(0,list[0] -1 if list[0] - 1 != 0 else 1)
Nlist.insert(M,N - list[M - 1] - 1 if N - list[M - 1] - 1 != 0 else 1)
counter = 0
ANSER = 1
while counter <= M:
    SQ5 = math.sqrt(5)
    P = ((1 + SQ5) / 2)**(Nlist[counter] + 1)
    Q = ((1 - SQ5) / 2)**(Nlist[counter] + 1)
    HowMany = math.floor((P - Q ) / SQ5)
    ANSER *= HowMany
    counter += 1
print(ANSER % (10**9 + 7))

### FIXED CODE ###

import sys

mod = 10**9 + 7

def fibo(n):
    a, b = 0, 1
    if n == 1:
        return 1
    else:
        for i in range(n):
            a0 = a
            a = b
            b = a0 + b
        return b
        
N, M = map(int, input().split())
a = []
 
if M == 0:
    print(fibo(N) % mod)
    sys.exit()
 
for i in range(M):
    a.append(int(input()))
    
for j in range(len(a)-1):
    if a[j+1] - a[j] == 1:
        print(0)
        sys.exit()
    
hole = 0
pattern = 1
 
for i, k in enumerate(a):
    if i == 0:
        pattern *= fibo(k-1)
    else:
        if i > 0:
            pattern *= fibo(a[i]-a[i-1]-2)
        
pattern *= fibo(N-a[-1]-1)
print(pattern % mod)
def back_oturigation(fee, coin_values, coin_nums):
    """
    1. ????????????????????????????????£??????????????????
    2. 1????????????????????????????????????????????????????????????
       ???????????§?????????????????????-> ?°????????????????????¶???????????????????
    3. 2????????????????????°?????????????????????????????????????????????
    """
    # 1.
    oturi = coin_values[0]*coin_nums[0]\
            +coin_values[1]*coin_nums[1]\
            +coin_values[2]*coin_nums[2]\
            +coin_values[3]*coin_nums[3]\
            -fee
    use_coins = [0] * len(coin_values)
    no_use_coins = [0]*len(coin_values)

    # 2.
    for i in range(len(coin_values)-1, -1, -1):
        no_use_coins[i] = int(oturi / coin_values[i])
        oturi = oturi - (coin_values[i] * no_use_coins[i])


    #3.
    result = ""
    for i in range(0, len(use_coins), 1):
        use_coins[i] = coin_nums[i] - no_use_coins[i]
        if use_coins[i] > 0:
            print(str(coin_values[i]) + ' ' + str(use_coins[i]))
            result = result+str(coin_values[i]) + ' ' + str(use_coins[i])+'\n'
    #return result

if __name__ == "__main__":
    total_fee = int(input('total_fee:'))
    while(True):
        if total_fee == 0:break
        coins = input('total_coins:')
        coins = coins.split(' ') #10, 50, 100, 500????????§????????????
        coins = [int(coin) for coin in coins]
        coin_values=[10, 50, 100, 500]
        back_oturigation(total_fee, coin_values, coins)

### FIXED CODE ###

import math
def back_oturigation(fee, coin_values, coin_nums):
    """
    1. ?????????????????????????????????£??????????????????
    2. 1????????????????????????????????????????????????????????????
       ????????????§?????????????????????-> ??°?????????????????????¶???????????????????
    3. 2?????????????????????°?????????????????????????????????????????????
    """
    # 1.
    oturi = coin_values[0] * coin_nums[0] \
            + coin_values[1] * coin_nums[1] \
            + coin_values[2] * coin_nums[2] \
            + coin_values[3] * coin_nums[3] \
            - fee

    use_coins = [0] * len(coin_values)
    no_use_coins = [0] * len(coin_values)
 
    # 2.
    for i in range(len(coin_values) - 1, -1, -1):
        no_use_coins[i] = int(oturi / coin_values[i])
        oturi = oturi - (coin_values[i] * no_use_coins[i])
 
    # 3.
    for i in range(0, len(use_coins), 1):
        use_coins[i] = coin_nums[i] - no_use_coins[i]
        if use_coins[i] > 0:
            print(str(coin_values[i]) + ' ' + str(use_coins[i]))
 
if __name__ == "__main__":
    first = True
    while (True):
        total_fee = int(input(''))
        if total_fee == 0:
            break
        if first:
            first = False
        else:
            print('')
        coins = input('')
        coins = coins.split(' ')  # 10, 50, 100, 500?????????§????????????
        coins = [int(coin) for coin in coins]
        coin_values = [10, 50, 100, 500]
        back_oturigation(total_fee, coin_values, coins)
a,b =map(int(i) for i in input().split())
if a==b:
  print(a*a)
elif a>b:
  print(2*a-1)
else:
  print(b*2-1)
    

### FIXED CODE ###

a,b =(int(i) for i in input().split())
if a==b:
  print(a*2)
elif a>b:
  print(2*a-1)
else:
  print(b*2-1)
from collections import defaultdict
from itertools import combinations
def solve():
    n = int(input())
    XY = [list(map(int, input().split())) for _ in range(n)]
    m = defaultdict(int)
    for i, j in combinations(range(n), 2):
        m[(XY[i][0] - XY[j][0], XY[i][1] - XY[j][1])] += 1
    print(n - max(m.items(), key=lambda x: x[1])[1])
solve()


### FIXED CODE ###

from collections import defaultdict
from itertools import permutations
def solve():
    n = int(input())
    XY = [list(map(int, input().split())) for _ in range(n)]
    if n == 1:
        return 1
    m = defaultdict(int)
    for i, j in permutations(range(n), 2):
        m[(XY[i][0] - XY[j][0], XY[i][1] - XY[j][1])] += 1
    return n - max(m.items(), key=lambda x: x[1])[1]
print(solve())
*D, = open(0)
n = int(D[0])

edge = [[] for _ in range(n+1)]
v_val = [0 for _ in range(n+1)]

dist = {}

for i in range(1, n):
    a, b = map(int, D[i].split())
    edge[a].append(b)
    edge[b].append(a)
c = list(map(int, D[n].split()))
c = sorted(c, reverse=True)

from collections import deque
visited = [False for _ in range(len(edge))]
start = 1
que = deque()
que.append(start)
order.append(start)
visited[start] = True
order = []

while que:
    node = que.popleft()
    for it in edge[node]:
        if not visited[it]:
            order.append(it)
            visited[it] = True
            que.append(it)
# calculate cost
v_val = [0 for _ in range(len(c)+1)]
for i in order:
    v_val[i] = c[i-1]

print(sum(c[1:]))
print(' '.join(map(str, v_val[1:])))

### FIXED CODE ###

*D, = open(0)
n = int(D[0])

edge = [[] for _ in range(n+1)]
v_val = [0 for _ in range(n+1)]

dist = {}

for i in range(1, n):
    a, b = map(int, D[i].split())
    edge[a].append(b)
    edge[b].append(a)
c = list(map(int, D[n].split()))
c = sorted(c, reverse=True)

from collections import deque
visited = [False for _ in range(len(edge))]
start = 1
que = deque()
que.append(start)
order = []
order.append(start)
visited[start] = True

while que:
    node = que.popleft()
    for it in edge[node]:
        if not visited[it]:
            order.append(it)
            visited[it] = True
            que.append(it)
# calculate cost
v_val = [0 for _ in range(len(c)+1)]
for i, it in enumerate(order):
    v_val[it] = c[i]

print(sum(c[1:]))
print(' '.join(map(str, v_val[1:])))
import sys
import heapq
import bisect

mod = 10**9+7
dd = ((-1,0),(1,0),(0,-1),(0,1))

def I(): return(int(sys.stdin.readline()))
def LI(): return([int(x) for x in sys.stdin.readline().split()])
def S(): return(sys.stdin.readline()[:-1])
def IR(n): return([I() for _ in range(n)])

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

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

def main():
    N,Q = LI()
    node=[[] for _ in range(N)]
    flag = [True for _in range(N)]
    for _ in range(N-1):
        a,b = LI()
        node[a-1].append(b-1)
        node[b-1].append(a-1)

    counter = [0] * N
    for _ in range(Q):
        p,x = LI()
        counter[p-1] += x

    cur = [[0,0]]
    while cur:
        nxt = []
        for a,c in cur:
            flag[a]=False
            counter[a]+=c
            for b in node[a]:
                if flag[b]:
                    nxt.append([b,counter[a]])
        cur = [x for x in nxt]

    r = [counter[i] for i in range(N)]

    return(" ".join(map(str,r)))

if __name__ == "__main__":
    print(main())


### FIXED CODE ###

import sys
import heapq
import bisect

mod = 10**9+7
dd = ((-1,0),(1,0),(0,-1),(0,1))

def I(): return(int(sys.stdin.readline()))
def LI(): return([int(x) for x in sys.stdin.readline().split()])
def S(): return(sys.stdin.readline()[:-1])
def IR(n): return([I() for _ in range(n)])

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

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

def main():
    N,Q = LI()
    node=[[] for _ in range(N)]
    flag = [True for _ in range(N)]
    for _ in range(N-1):
        a,b = LI()
        node[a-1].append(b-1)
        node[b-1].append(a-1)

    counter = [0] * N
    for _ in range(Q):
        p,x = LI()
        counter[p-1] += x

    cur = [[0,0]]
    while cur:
        nxt = []
        for a,c in cur:
            flag[a]=False
            counter[a]+=c
            for b in node[a]:
                if flag[b]:
                    nxt.append([b,counter[a]])
        cur = [x for x in nxt]

    r = [counter[i] for i in range(N)]

    return(" ".join(map(str,r)))

if __name__ == "__main__":
    print(main())
N=int(input())
i=0
summ=0

def kakuwa(N):
  while N>10**i:
    i+=1
  for k in range(i+1)[::-1]:
    summ+=N//(10**k)
    N-=(10**k)*(N//(10**k))
  return(summ)

if N%kakuwa(N)==0:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

N=int(input())
def kakuwa(N):
  summ=0
  i=0
  while N>10**i:
    i+=1
  for k in range(i+1)[::-1]:
    summ+=N//(10**k)
    N-=(10**k)*(N//(10**k))
  return(summ)

if N%kakuwa(N)==0:
  print("Yes")
else:
  print("No")
n, m = map(int, input().split())
lst = list(map(int, input().split()))
lst = sorted(lst, key = lambda x:-x)
dic = {1:2, 2:5, 3:5, 4:4, 5:5, 6:6, 7:3, 8:7, 9:6}

s = set()
for i in lst:
    s.add(dic[i])
s = list(sorted(s))

dp = [0] * (n+1)
for i in range(0, n+1):
    a = 0
    max_a = 0
    for j in s:
        if i == j and dp[i-j] == 0:
            a = 1
        elif i - j > 0 and dp[i-j] > 0:
            a = dp[i-j] + 1
        if max_a < a:
            max_a = a
    dp[i] = max_a

def out(dp, dic, n, ans, ans_digit, lst):
    if len(ans) == ans_digit-1:
        for i in lst:
            if n == dic[i]:
                return ans + str(i)
    else:
        for i in lst:
            if n - dic[i] >= 0:
                if dp[n] -1 == dp[n-dic[i]]:
                    ans += str(i)
                    next_n = n - dic[i]
                    break
        return out(dp, dic, next_n, ans, ans_digit, lst)
    
print(out(dp, dic, n, '', dp[n], lst))

### FIXED CODE ###

n, m = map(int, input().split())
lst = list(map(int, input().split()))
lst = sorted(lst, key = lambda x:-x)
dic = {1:2, 2:5, 3:5, 4:4, 5:5, 6:6, 7:3, 8:7, 9:6}

s = set()
for i in lst:
    s.add(dic[i])
s = list(sorted(s))

dp = [0] * (n+1)
for i in range(0, n+1):
    a = 0
    max_a = 0
    for j in s:
        if i-j < 0:
            pass
        elif i == j:
            a = 1
        elif i - j > 0 and dp[i-j] > 0:
            a = dp[i-j] + 1
        if max_a < a:
            max_a = a
    dp[i] = max_a

ans = ''
ans_digit = dp[n]
while len(ans) < ans_digit:
    if len(ans) == ans_digit-1:
        for i in lst:
            if n == dic[i]:
                ans += str(i)
                break
    else:
        for i in lst:
            if n - dic[i] >= 0:
                if dp[n] -1 == dp[n-dic[i]]:
                    ans += str(i)
                    n -= dic[i]
                    break
    
print(ans)
from fractions import gcd

d = int(input())
nums = list(map(int, input().split(' ')))

def lcm_base(x, y):
    return (x * y) // gcd(x, y)

if d == 1:
  print(1)
else:
  lcm_num = nums[0]
  for i in range(len(nums)-1):
    lcm_num = lcm_base(lcm_num, nums[i+1])

min_nums = []
for n in nums:
  min_nums.append(int(lcm_num / n))
ans = sum(min_nums)
print(ans % (10**9 + 7))

### FIXED CODE ###

from fractions import gcd

def lcm_base(x, y):
  return x * y // gcd(x, y)

d = int(input())
nums = list(map(int, input().split(' ')))

lcm_num = 1
for n in nums:
  lcm_num = lcm_base(lcm_num, n)

ans = 0
mod = 10**9 + 7
for n in nums:
  ans += lcm_num//n
print(ans % mod)
A,B = (int(i) for i in input().split())

import math

def lcm(x, y):
    return x * y // math.gcd(x, y)


print(lcm(A,B))

### FIXED CODE ###

A,B = (int(i) for i in input().split())

import fractions

def lcm(a, b):
    #return a * b // math.gcd(a, b)
    return  a*b // fractions.gcd(a, b)

print(lcm(A,B))
n, k, price, special = map(int, input().split())
    result = 0
    for i in range(n):
        if i < k:
            result += price
        else:
            result += special
    
    print(result)

### FIXED CODE ###

def iroha():
    n, k, price, special = [int(input()) for i in range(4)]
    result = 0
    for i in range(n):
        if i < k:
            result += price
        else:
            result += special
    print(result)

if __name__ == "__main__":
    iroha()
x = list(map(int,input().split()))
count=0
for a in range(0,x[1]):
    for b in range(0,x[0]+1):
        for c in range(0,x[0]+1):
            if(a+b+c==x[1]):
                count+=1
print(count)

### FIXED CODE ###

print(input().replace(","," "))
k = int(input)
a = 'ACL'
print(a ** k)

### FIXED CODE ###

k = int(input())
a = "ACL"
print(a * k)
N = int(input())
K = int(input())
L = len(str(N))

def solve(num_str, k, smaller):
    if k == 0 or num_str == None:
        return 1

    elif smaller:
        keta = len(num_str)
        if k == 1:
            return keta * 9
        elif k == 2:
            return keta * (keta-1)//2 * 9 * 9
        else:
            return keta * (keta-1) * (keta -2)//6 * 9 * 9 * 9
    else:   
        num = int(num_str)
        num_str = str(num_str)
        top = int(num_str[0])
        if top:
            zero = solve(num_str[1:], k, True)
            non_zero = solve(num_str[1:], k-1, True) * (top - 1)
            just = solve(num_str[1:], k-1, False)
            return zero + non_zero + just
        else:
            return solve(num_str[1:], k, False)
print(solve(str(N), K, False))

### FIXED CODE ###

N = int(input())
K = int(input())
L = len(str(N))

suu = []
for i in range(L):
    suu.append(int(str(N)[i]))

DP_1 =[[0 for k in range(L+2)] for i in range(L+1)]
DP_2 =[[0 for k in range(L+2)] for i in range(L+1)]
DP_2[0][0] = 1
for i in range(L):
    for k in range(L+1):
        DP_1[i+1][k] = DP_1[i][k] + DP_1[i][k-1] * 9 
        if suu[i]:
            DP_1[i+1][k] += DP_2[i][k] + DP_2[i][k-1] * max(suu[i] - 1, 0)
            DP_2[i+1][k] = DP_2[i][k-1]
        else:
            DP_2[i+1][k] = DP_2[i][k]
print(DP_1[L][K]+ DP_2[L][K])