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

s = str(input())
K = int(input())
lt = []
for start in range(len(s)):
	for end in range(start + 1, len(s) + 1):
		lt.append(s[start:end])
lt = list(set(lt))
lt.sort()
print(lt[K-1])

### FIXED CODE ###

s = str(input())
K = int(input())

def find(str):
	lt = []
	for start in range(len(str)):
		for end in range(start + 1, len(str) + 1):
			lt.append(str[start:end])
	lt = list(set(lt))
	lt.sort()

	return lt

s_pt = list(set(list(s)))
s_pt.sort()
ans = []
for i in range(min(5, len(s_pt))):
	ind = [ix for ix, x in enumerate(s) if x == s_pt[i]]
	for j in ind:
		ans += find(s[j:min(j+5, len(s))])
	ans = list(set(ans))
	if len(ans) >= 5:
		break
ans = list(set(ans))
ans.sort()
print(ans[K-1])
### BUGGY CODE ###

# coding: utf-8
#import math
#import numpy
#N = int(input())
import sys
input = sys.stdin.readline
N, K = map(int,input().split())
A = list(map(int,input().split()))
#K =int(input())
ANS = []
a = 1
for i in range(K):
    a *= A[K-i-1]
ANS.append(a)
for i in range(K,N):
    a *=A[i]
    a //= A[i-K]
    ANS.append(a)
#print(ANS)
for i in range(N-K):
    if ANS[i+1] > ANS[i]:
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

# coding: utf-8
#import math
#import numpy
#N = int(input())
def main():
    import sys
    input = sys.stdin.readline
    N, K = map(int,input().split())
    A = list(map(int,input().split()))
    #K =int(input())
    ANS = []
    
    #ANS.append(a)
    for i in range(K,N):
        if A[i-K] < A[i]:
            print("Yes")
        else:
            print("No")
        
        
        #ANS.append(a)
    #print(ANS)
    

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

from scipy.sparse.csgraph import dijkstra, csgraph_from_dense, floyd_warshall
xs,ys,xg,yg = map(int, input().split())
N = int(input())
xyr = [(xs,ys,0)]
xyr.extend([list(map(int, input().split())) for i in range(N)])
xyr.append((xg,yg,0))
graph = [[0] * (N+2) for _ in range(N+2)]

max_val = 10**9

for i in range(N+2):
    graph[i][i] = max_val

for i in range(N+2):
    for j in range(i+1,N+2):
        x1,y1,r1 = xyr[i]
        x2,y2,r2 = xyr[j]
        d = max(0, ((x1-x2)**2 + (y1-y2)**2) ** 0.5 - r1 - r2)
        graph[i][j] = graph[j][i] = d


g = csgraph_from_dense(graph,null_value=max_val)

dij = dijkstra(g)
flo = floyd_warshall(g)
print(dij[0][-1])

### FIXED CODE ###

from scipy.sparse.csgraph import dijkstra, csgraph_from_dense
xs,ys,xg,yg = map(int, input().split())
N = int(input())
xyr = [(xs,ys,0)]
xyr.extend([list(map(int, input().split())) for i in range(N)])
xyr.append((xg,yg,0))
graph = [[0] * (N+2) for _ in range(N+2)]

max_val = 10**9

for i in range(N+2):
    graph[i][i] = max_val

for i in range(N+2):
    for j in range(i+1,N+2):
        x1,y1,r1 = xyr[i]
        x2,y2,r2 = xyr[j]
        d = max(0, ((x1-x2)**2 + (y1-y2)**2) ** 0.5 - r1 - r2)
        graph[i][j] = graph[j][i] = d

g = csgraph_from_dense(graph,null_value=max_val)
print(dijkstra(g,indices=0)[-1])
### BUGGY CODE ###

def main():
    N, K, C, = map(int,input().split())
    S = list(input())
    ans = []

    def solve(index, K):
        i = 0
        cnt = 0
        while i < N:
            if S[i] == 'o' and i != index:
                cnt += 1
                i += C + 1
            else:
                i += 1
        return cnt < K

    if not (solve(-1, K+1)):
        pass
    else:
        index = 0
        while index < N:
            if S[index] == 'x':
                index += 1
            elif solve(index, K):
                ans.append(index + 1)
                index += C + 1
            else:
                index += 1

        for i in ans:
            print(i)
        
if __name__ == '__main__':
    main()

### FIXED CODE ###

N, K, C = map(int,input().split())
S = list(input())

def solve(List):
    ans = []
    i = 0
    while i < N:
        if List[i] == 'o':
            ans.append(i+1)
            i += C
        i += 1
    return ans

n = solve(S)

if len(n) > K:
    pass
else:
    r = solve(S[::-1])
    r = list(map(lambda x: N+1-x, r[::-1]))
    ans = list(set(n) & set(r))
    ans.sort()
    for i in ans:
        print(i)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import math
from functools import lru_cache

#############
# Constants #
#############

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

#############
# Functions #
#############

kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])
    return arr

#############
# Main Code #
#############

N = int(input())
S = list(str(input()))
Q = int(input())

for i in range(Q):
  query = list(map(str,input().split()))
  if query[0] == "1":
    S[int(query[1])-1] = query[2]
  if query[0] == "2":
    print(len(set(S[int(query[1])-1:int(query[2])])))

### FIXED CODE ###

# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

N = int(input())
S = list(input())
Q = int(input())


alphabet = "abcdefghijklmnopqrstuvwxyz"

bag = { l:[] for l in alphabet}

for i in range(N):
  bag[S[i]].append(i+1)


import bisect

for _ in range(Q):
  t,a,b = input().split()
  a = int(a)
  if int(t) == 1:
    if S[a-1]!=b:
      bag[S[a-1]].remove(a)
      S[a-1] = b
      bisect.insort(bag[b],a)
  else:
    count = 0
    b = int(b)
    for l in alphabet:
      if len(bag[l])>0:
        left = bisect.bisect_left(bag[l],a)
        if left != len(bag[l]):
          if bag[l][left] <= b:
            count += 1
    print(count)
### 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: Cumulative sum
        # csum[j + 1] = dp[i-1][0] + dp[i-1][1] + ... + dp[i-1][j]
        csum = [0] + list(dp[i - 1])
        for j in range(k + 1):
            csum[j + 1] += csum[j]
            csum[j + 1] %= mod
        dpi = dp[i]
        for j in range(1, k + 1):
            l = 0 if j < a[i] else j - a[i]
            dpi[j] = csum[j + 1] - csum[l]
            if dpi[j] < 0:
                dpi[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 ###

N=int(input())
A=[0]*N
for i in range(N):
    A[i]=int(input())

j=0
ans=0
count=[]
while j!=1:
    j=A[j]-1
    count.append(j)
    if count.count(j)==2:
        ans=-1
        break
    ans+=1

print(ans)

### FIXED CODE ###

N=int(input())
A=[0]*N
for i in range(N):
    A[i]=int(input())

j=0
ans=0
count=[0]*N
while j!=1:
    ans+=1
    j=A[j]-1
    count[j]+=1
    if count[j]>=2:
        ans=-1
        break

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

s = int(input())

x1, y1 = 0, 0
x2, y2, x3, y3 = 0, 0, 0, 0

while True:
    for i in range(1, min(int(s**0.5), 10e9) + 1):
        if s % i == 0 and s / i <= 10e9:
            x2 = i
            y3 = s//i
            break

    if x2 == 0 and y3 == 0:
        y2 = -1
        x3 += 1
        s -= x3
        continue
    break

print(x1, y1, x2, y2, x3, y3)

### FIXED CODE ###

s = int(input())

e = 10**9
if s == e**2:
    print(0, 0, e, 1, 0, e)
else:
    y = s//e + 1
    x = y*e - s
    print(0, 0, e, 1, x, y)
### BUGGY CODE ###

h,w,d=map(int,input().split())
D=dict()
for i in range(h):
  A=[int(i) for i in input().split()]
  for j in range(w):
    D[A[j]]=[i+1,j+1]
def Dist(x,y):
  return abs(D[x][0]-D[y][0])+abs(D[x][1]-D[y][1])
q=int(input())
for i in range(q):
  l,r=map(int,input().split())
  ans=0
  rep=(r-l)//d
  for j in range(rep):
    ans+=Dist(l+j*d,l+(j+1)*d)
  print(ans)

### FIXED CODE ###

h,w,d=map(int,input().split())
D=dict()
for i in range(h):
  A=[int(i) for i in input().split()]
  for j in range(w):
    D[A[j]]=[i+1,j+1]
def Dist(x,y):
  return abs(D[x][0]-D[y][0])+abs(D[x][1]-D[y][1])
T=[[0 for _ in range((h*w)//d)] for _ in range(d)]
for i in range(d):
  for j in range((h*w)//d):
    if i+1+d*(j+1)>h*w:
      continue
    elif j==0:
      T[i][j]=Dist(i+1,i+1+d)
    else:  
      T[i][j]=T[i][j-1]+Dist(i+1+d*j,i+1+d*(j+1))
q=int(input())
for i in range(q):
  l,r=map(int,input().split())
  x=l%d
  if r==x:
    print(0)
  elif l==x and x!=0:
    print(T[x-1][(r-x)//d-1])
  elif l==x and x==0:
    print(T[x-1][(r-x)//d-2])
  else:
    ll=(l-x)//d-1
    rr=(r-x)//d-1
    if x==0:
      ll-=1
      rr-=1
    print(T[x-1][rr]-T[x-1][ll])
### BUGGY CODE ###

from itertools import combinations

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

result = 0
for a in combinations(A, K):
    result += max(a) - min(a)
    result %= 1000000007
print(result)


### FIXED CODE ###

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

fac = [0] * (N + 1)
fac[0] = 1
for i in range(N):
    fac[i + 1] = fac[i] * (i + 1) % 1000000007


def mcomb(n, k):
    if n == 0 and k == 0:
        return 1
    if n < k or k < 0:
        return 0
    return fac[n] * pow(fac[n - k], 1000000005, 1000000007) * pow(fac[k], 1000000005, 1000000007) % 1000000007


A.sort(reverse = True)
result = 0
for i in range(N - K + 1):
    result += A[i] * mcomb(N - (i + 1), K - 1)
    result %= 1000000007

A.sort()
t = 0
for i in range(N - K + 1):
    t += A[i] * mcomb(N - (i + 1), K - 1)
    t %= 1000000007

result -= t
result += 1000000007
result %= 1000000007
print(result)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

V, E = list(map(int, input().split()))
weight = []
for i in range(E):
  s, t, w = list(map(int, input().split()))
  weight.append((s,t,w))

weight.sort(key = lambda x: x[2])

parent = [i for i in range(V)]

def find(x):
  if parent[x] == x:
    return x
  else:
    return find(parent[x])

def union(x, y):
  a = find(x)
  b = find(y)
  parent[a] = b
  

sum_weight = 0

while weight:
  a, b, c = weight[0]
  if find(a) != find(b):
    union(a, b)
    sum_weight += c
  weight.pop(0)
  
print(sum_weight)
  


  


### FIXED CODE ###

# -*- coding: utf-8 -*-

V, E = list(map(int, input().split()))
weight = []
for i in range(E):
  s, t, w = list(map(int, input().split()))
  weight.append((s,t,w))

weight.sort(key = lambda x: x[2])

parent = [i for i in range(V)]
rank = [0 for i in range(V)]

def find(x):
  if parent[x] == x:
    return x
  else:
    return find(parent[x])

def union(x, y):
  a = find(x)
  b = find(y)
  if rank[a] < rank[b]:
    parent[a] = b
  else:
    parent[b] = a
    if rank[a] == rank[b]:
      rank[a] += 1
  

sum_weight = 0

for i in range(E):
  a, b, c = weight[i]
  if find(a) != find(b):
    union(a, b)
    sum_weight += c
  else:
    continue
  
print(sum_weight)
### BUGGY CODE ###

n, *a = map(int, open(0).read().split())
ans = 0
mod = 10 ** 9 + 7
for k in range(61):
	m = 1 << k
	c = 0
	for x in a:
		if m & x:
			c += 1
	ans += (c) * (n - c) * m
	ans %= mod
print(ans)


### FIXED CODE ###

n, *a = map(int, open(0).read().split())
ans = 0
mod = 10 ** 9 + 7
for k in range(61):
	m = 1 << k
	c = 0
	for x in a:
		if m & x:
			c += 1
	ans += (c) * (n - c) * m
	ans %= mod
print(ans)
### BUGGY CODE ###

R, C, K = map(int,input().split())
MAP = [[0 for i in range(C)] for j in range(R)]
DP = [[[0 for i in range(4)] for j in range(C+1)] for k in range(R+1)]

for _ in range(K):
    r, c, v = map(int,input().split())
    MAP[r-1][c-1] = v

for i in range(R):
    for j in range(C):
        DP[i+1][j+1][0] = max(DP[i+1][j+1][0], max(DP[i][j+1]))
        for k in range(4):
            DP[i+1][j+1][k] = max(DP[i+1][j+1][k], DP[i+1][j][k])
        if MAP[i][j] == 0:
            continue
        DP[i+1][j+1][1] = max(DP[i+1][j+1][1], max(DP[i][j+1]) + MAP[i][j])
        for k in range(3):
            DP[i+1][j+1][k+1] = max(DP[i+1][j+1][k+1], DP[i+1][j][k] + MAP[i][j])

print(max(DP[R][C]))

### FIXED CODE ###

R, C, K = map(int,input().split())
MAP = [[0 for i in range(C)] for j in range(R)]
DP = [[[0 for i in range(C+1)] for j in range(4)] for k in range(R+1)]
 
for _ in range(K):
    r, c, v = map(int,input().split())
    MAP[r-1][c-1] = v
 
for i in range(R):
    for j in range(4):
        for k in range(C):
            DP[i+1][j][k+1] = max(DP[i][3][k+1], DP[i+1][j][k])
            if j == 0:
                continue
            v = MAP[i][k]
            if v == 0:
                continue
            DP[i+1][j][k+1] = max(DP[i+1][j][k+1], max(DP[i][3][k+1], DP[i+1][j-1][k]) + v)

print(DP[R][3][C])
### BUGGY CODE ###

num =int(input())

val = [int(x) for x in input().split()]

sort_val = sorted(val)
set_val = set(sort_val)

res = True

if len(val) %2 != 0:
    for i in set_val:
        if (i == 0 and sort_val.count(i) != 1) or (i != 0 and sort_val.count(i) %2 != 0):
            res = False
            break
else:
    for i in set_val:
        if sort_val.count(0) != 0 or sort_val.count(i) %2 != 0:
            res = False
            break

cnt = 1
for i in range(0, len(sort_val)//2):
    cnt = cnt*2 % 1000000007

print(0 if res == False else cnt)

### FIXED CODE ###

num =int(input())

val = [int(x) for x in input().split()]

_len = len(val)
sort_val = sorted(val)
res = False

if len(sort_val) %2 == 0:
    tmp = sort_val[1::2]
    tmp2 = sort_val[::2]
    if sorted(tmp) == sorted(tmp2):
        res = True
else:
    if sort_val.count(0) != 1:
        pass
    else:
        del sort_val[0]
        tmp = sort_val[::2]
        tmp2 = sort_val[1::2]
        if sorted(tmp) == sorted(tmp2):
            res = True

cnt = 1
if res:
    for i in range(0, _len//2):
        cnt = cnt*2 % 1000000007

print(0 if not res else cnt)
### BUGGY CODE ###

def main():
    import sys
    input=sys.stdin.readline
    N,Q = map(int,input().split())
    AB = [[x for x in map(int,input().split())] for _ in range(N-1)]
    PX = [[x for x in map(int,input().split())] for _ in range(Q)]

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

    cnt = [0]*N
    for p,x in PX:
        cnt[p-1] += x

    color = ["WHITE"] * (N+1)
    stack = []

    def dfs(u):
        stack.append(u)
        color[u] = "GRAY"

        while len(stack) > 0:
            u = stack[-1]
            if len(G[u]) == 0:
                color[u] = "BLACK"
                stack.pop()
            else:
                u_next = G[u].pop(0)
            if color[u_next] == "WHITE":
                color[u_next] = "GRAY"
                cnt[u_next-1] += cnt[u-1]
                stack.append(u_next)
    dfs(1)
    print(*cnt)


    
if __name__ == '__main__':
    main()

### FIXED CODE ###

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

N,Q = map(int,input().split())
AB = [[int(x) for x in input().split()] for _ in range(N-1)]
PX = [[int(x) for x in input().split()] for _ in range(Q)]

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

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

def dfs(v,parent,add):
    value[v] += add
    for x in graph[v]:
        if x == parent:
            continue
        dfs(x,v,value[v])

dfs(1,0,0)

answer = ' '.join(map(str,value[1:]))
print(answer)
### BUGGY CODE ###

def main():
    height, width, target_count = [int(x) for x in input().split()]
    count_by_height = [0] * height
    count_by_width = [0] * width
    bomb_is = [[False] * width for _ in range(height)]
    for _ in range(target_count):
        bom_h, bom_w = [int(x) - 1 for x in input().split()]
        count_by_height[bom_h] += 1
        count_by_width[bom_w] += 1
        bomb_is[bom_h][bom_w] = True
    max_h, max_w = max(count_by_height), max(count_by_width)
    max_h_is = [i for i, x in enumerate(count_by_height) if x == max_h]
    max_w_is = [i for i, x in enumerate(count_by_width) if x == max_w]
    no_cross = any(not bomb_is[hh][ww] for hh in max_h_is for ww in max_w_is)
    return max_h + max_w - (not no_cross)


if __name__ == '__main__':
    ans = main()
    print(ans)


### FIXED CODE ###

from collections import defaultdict


def main():
    height, width, target_count = [int(x) for x in input().split()]
    count_by_height = defaultdict(int)
    count_by_width = defaultdict(int)
    bomb_is = set()
    for _ in range(target_count):
        bom_h, bom_w = [int(x) - 1 for x in input().split()]
        count_by_height[bom_h] += 1
        count_by_width[bom_w] += 1
        bomb_is.add((bom_h, bom_w))
    max_h = max(v for v in count_by_height.values())
    max_w = max(v for v in count_by_width.values())
    max_h_index = [i for i, x in count_by_height.items() if x == max_h]
    max_w_index = [i for i, x in count_by_width.items() if x == max_w]
    no_cross = any(
        (hh, ww) not in bomb_is for hh in max_h_index for ww in max_w_index)
    return max_h + max_w - (not no_cross)


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

s = input()

ans = 0

z = [[0]*4 for i in range(len(s))]

t = (10**9+7)

for i in range(1,len(s)-1):
    z[i][0] = z[i - 1][0]
    z[i][1] = z[i - 1][1]
    if s[i-1]=='A':
        z[i][0] +=1
    elif s[i-1]=='?':
        z[i][1] += 1

for i in range(1,len(s)-1):
    z[-i-1][2] = z[-i][2]
    z[-i-1][3] = z[-i][3]
    if s[-i]=='C':
        z[-i-1][2] += 1
    elif s[-i] =='?':
        z[-i-1][3] += 1


for i in range(1,len(s)-1):
    if s[i]=='B' or s[i]=='?':
        a1 = 3*z[i][0]+z[i][1]
        a2 = 3**(z[i][1]-1)%t
        c1 = 3*z[i][2]+z[i][3]
        c2 = 3**(z[i][3]-1)%t
        ans += (a1*a2*c1*c2)%t
    ans %=t

print(int(ans))

### FIXED CODE ###

s = input()

ans = 0

rc = [0]
rq = [0]
la = [0]
lq = [0]
q3 = [1]
t = 10**9+7

for i in range(len(s)-1):
    if s[len(s)-i-1]=='C':
        rc.append(rc[-1]+1)
        rq.append(rq[-1])
    elif s[len(s)-i-1]=='?':
        rc.append(rc[-1])
        rq.append(rq[-1]+1)
    else:
        rc.append(rc[-1])
        rq.append(rq[-1])
    if s[i]=='A':
        la.append(la[-1]+1)
        lq.append(lq[-1])
    elif s[i]=='?':
        la.append(la[-1])
        lq.append(lq[-1]+1)
    else:
        la.append(la[-1])
        lq.append(lq[-1])
    q3.append(q3[-1] * 3 % t)
rc.reverse()
rq.reverse()

q3.append(1/3)

for i in range(len(s)):
    if s[i]=='B' or s[i]=='?':
        l = q3[lq[i]-1]
        r = q3[rq[i]-1]
        ans += l*r*(3*la[i]+lq[i])*(3*rc[i]+rq[i]) % t

print(round(ans%t))
### BUGGY CODE ###

from fractions import gcd
import sys, math

def input():
    return sys.stdin.readline()
def main():
    N = int(input())
    A = list(map(int,input().split()))
    MOD = 10**9 + 7
    t = A[0]
    def lcm(a,b):
        return a*b//gcd(a,b)
    for e in A:
        t = lcm(e,t)
    ans = 0
    for e in A:
        ans += t//e
        ans %= MOD
    print(ans)
if __name__ == '__main__':
    main()


### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
MOD = 10**9 + 7
t = A[0]

def gcd(a,b):
    if b == 0:
        return a
    return gcd(b,a%b)
def lcm(a,b):
    return a*b//gcd(a,b)
for e in A:
    t = lcm(e,t)

ans = 0
for e in A:
    ans += t//e

print(ans%MOD)
### BUGGY CODE ###

n,m,q=map(int,input().split())
l=[list(map(int,input().split())) for i in range(q)]

ans=0
for i in range(2**q):
  t_ans=0
  x=[1 for i in range(n)]
  for j in range(q):
    if (i>>j)&1:
      a,b,c,d=l[j]
      a-=1
      b-=1
      t_ans+=d
      if x[b]-x[a]==c:
        pass
      else:
        x[b]=x[a]+c

  check=1
  before=x[0]
  for i in x[1:]:
    if i>=before:
      before=i
    else:
     check=0

  t_ans=0
  for a,b,c,d in l:
    a-=1
    b-=1
    if x[b]-x[a]==c:
      t_ans+=d
  ans=max(ans,t_ans)

print(ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)

n,m,q=map(int,input().split())
l=[list(map(int,input().split())) for i in range(q)]

def dfs(nl):
  if len(nl)==n:
    global ans
    t_ans=0
    for a,b,c,d in l:
      a-=1
      b-=1
      if nl[b]-nl[a]==c:
        t_ans+=d
    ans=max(ans,t_ans)
    return

  for i in range(nl[-1], m+1):
        dfs(nl+[i])

ans=0
for i in range(1,m+1):
  dfs([i])

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

s = str(input())
L = len(s)
dict = {}
for i in range(L):
  amari = (int(s[i:])) % 2019
  if not(amari in dict.keys()):
    dict[amari] = 1
  else:
    dict[amari] += 1
if not(0 in dict.keys()):
    dict[0] = 1
else:
    dict[0] += 1
ans = 0
for key in dict.keys():
  ans += (dict[key]*(dict[key]-1))/2
print(int(ans))

### FIXED CODE ###

s = str(input())
L = len(s)
dict = [0] * 2019
dict[0] += 1
num = 0
for i in range(L-1, (-1), (-1)):
    num += (int(s[i]) * pow(10,(L-i-1), 2019))%2019
    amari = num % 2019
    dict[amari] += 1
ans = 0
for j in range(2019):
    ans += (dict[j]*(dict[j]-1))/2
print(int(ans))
### BUGGY CODE ###

S = str(input())
s = len(S)
cnt = 0
A = [0]*2019
for i in range(s):
  x = int(S[i:])%2019
  A[x] += 1
for i in range(1,2019):
  if A[i] != 0:
    cnt += A[i]*(A[i]-1)//2
cnt += A[0]*(A[0]+1)//2
print(cnt)

### FIXED CODE ###

S = str(input())
s = len(S)
cnt = 0
A = [0]*2019
r = 0
for i in range(s):
  x = (r+pow(10, i, 2019)*int(S[s-i-1]))%2019
  A[x] += 1
  r = x
  
for i in range(1,2019):
  if A[i] >= 2:
    cnt += A[i]*(A[i]-1)//2
cnt += A[0]*(A[0]+1)//2

print(cnt)