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

'''
自宅用PCでの解答
'''
import math
#import numpy as np
import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7
alp = "abcdefghijklmnopqrstuvwxyz"

def main():
    n,q = map(int,ipt().split())
#    n = 5*10**5
#    q = 5*10**5
#    c = [int(i)+1 for i in range(n)]
    c = [int(i) for i in ipt().split()]
    qi = []
    for i in range(q):
        l,r = map(int,ipt().split())
        qi.append(r*10**14+l*10**7+i)

    qi.sort()

    ans = [-1]*q
    ln = [-1]*(n+1)
    bq_al = [0]*(n+1)

    #Bit_Indexed_Tree
    #A1 ... AnのBIT(1-indexed)
    BIT = [0]*(n+1)

    #A1 ~ Aiまでの和 O(logN)
    def BIT_query(idx):
        res_sum = 0
        while idx > 0:
            res_sum += BIT[idx]
            idx -= idx&(-idx)
        return res_sum

    #Ai += x O(logN)
    def BIT_update(idx,x):
        while idx <= n:
            BIT[idx] += x
            idx += idx&(-idx)
        return

    pr = 0
    for ist in qi:
        i = ist%10**7
        l = (ist//10**7)%10**7
        r = ist//10**14
        for j in range(pr,r):
            cj = c[j]
            ij = ln[cj]
            if ij != -1:
                BIT_update(ij,-1)
            ln[cj] = j+1
            BIT_update(j+1,1)
        pr = r

        ans[i] = BIT_query(r)-BIT_query(l-1)

    for i in ans:
        print(i)

    return None

if __name__ == '__main__':
    main()


### FIXED CODE ###

'''
自宅用PCでの解答
'''
import math
#import numpy as np
import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7
alp = "abcdefghijklmnopqrstuvwxyz"

def main():
    n,q = map(int,ipt().split())
#    n = 5*10**5
#    q = 5*10**5
#    c = [int(i)+1 for i in range(n)]
    c = [int(i) for i in ipt().split()]
    qi = []
    for i in range(q):
        l,r = map(int,ipt().split())
        qi.append(r*((10**6+1)**2)+l*(10**6+1)+i)

    qi.sort()

    ans = [0]*q
    ln = [-1]*(n+1)
    bq_al = [0]*(n+1)

    #Bit_Indexed_Tree
    #A1 ... AnのBIT(1-indexed)
    BIT = [0]*(n+1)

    #A1 ~ Aiまでの和 O(logN)
    def BIT_query(idx):
        res_sum = 0
        while idx > 0:
            res_sum += BIT[idx]
            idx -= idx&(-idx)
        return res_sum

    #Ai += x O(logN)
    def BIT_update(idx,x):
        while idx <= n:
            BIT[idx] += x
            idx += idx&(-idx)
        return

    pr = 0
    for ist in qi:
        i = ist%(10**6+1)
        l = (ist//(10**6+1))%(10**6+1)
        r = ist//(10**6+1)**2
        for j in range(pr,r):
            cj = c[j]
            ij = ln[cj]
            if ij != -1:
                BIT_update(ij,-1)
            ln[cj] = j+1
            BIT_update(j+1,1)
        pr = r

        ans[i] = BIT_query(r)-BIT_query(l-1)


    for i in ans:
        print(i)

    return None

if __name__ == '__main__':

    main()
### BUGGY CODE ###

import bisect

Q=int(input())

b=0
a=[]
min=0
tmp=0
j=0
for i in range(Q):
    que=list(map(int,input().split()))
    if que[0]==1:
        j+=1
        b+=que[2]
        a.insert(  bisect.bisect_left(a,que[1]), que[1] )

        p= bisect.bisect_left(a,tmp)
        if p>j-p:
            min+=abs(que[1]-tmp)-abs(a[p-1]-tmp) 
            tmp=a[p-1]
        elif p==j-p:
            min+=abs(que[1]-tmp)
            tmp=a[p-1]
        else:
            q= bisect.bisect_right(a,tmp)
            if q<j-q:
                min+=abs(que[1]-tmp)-abs(a[q]-tmp) 
                tmp=a[q]
            else:min+=abs(que[1]-tmp)

    elif que[0]==2:
        print(tmp,min+b)

### FIXED CODE ###

import bisect
import heapq 

Q=int(input())

que=list(map(int,input().split()))
b=que[2]
l,r=[-que[1]],[que[1]]
heapq.heapify(l)
heapq.heapify(r)
a=0
tmp=que[1]
j=1
for i in range(Q-1):
    que=list(map(int,input().split()))
    if que[0]==1:
        j+=1
        b+=que[2]
        q1=que[1]
        if j%2==0:
            if q1<-l[0]:
                heapq.heappushpop(l,-q1)
            else:
                heapq.heappushpop(r,q1)

        else:
            if q1<-l[0]:
                heapq.heappush(l,-q1)
                heapq.heappush(r,-l[0])
            else:
                heapq.heappush(r,q1)
                heapq.heappush(l,-r[0])
        

        if -l[0]!=r[0]: a+=abs(tmp-q1)
        else: a+=abs(tmp-q1)-abs(-l[0]-tmp)
        tmp=-l[0]

    elif que[0]==2:
        print(tmp,a+b)
### BUGGY CODE ###

from collections import deque

N=int(input())
E={i:set() for i in range(1,N+1)}
F=[0]*(N+1)

H=[0]*(N-1)
J={}
for s in range(N-1):
    a,b=map(int,input().split())
    E[a].add(b)
    E[b].add(a)
    F[a]+=1
    F[b]+=1
    H[s]=(a,b)
    J[(a,b)]=s

C=[0]*(N-1)
G=[set() for _ in range(N+1)]

T={i:False for i in range(1,N+1)}
T[2]=True
Q=deque([2])
while Q:
    v=Q.popleft()
    for w in E[v]:
        if not T[w]:
            T[w]=True
            Q.append(w)

            p,q=min(v,w),max(v,w)
            c=1
            while c in G[p] or c in G[q]:
                c+=1
            C[J[(p,q)]]=c
            G[p].add(c)
            G[q].add(c)

print(max(C))
print("\n".join(map(str,C)))



### FIXED CODE ###

from collections import deque

N=int(input())
E={i:set() for i in range(1,N+1)}
F=[0]*(N+1)

H=[0]*(N-1)
J={}
for s in range(N-1):
    a,b=map(int,input().split())
    E[a].add(b)
    E[b].add(a)
    F[a]+=1
    F[b]+=1
    H[s]=(a,b)
    J[(a,b)]=s

M=max(F)

C=[0]*(N-1)
G=[set() for _ in range(N+1)]
A=[-1]*(N+1)

T={i:False for i in range(1,N+1)}
T[1]=True
Q=deque([1])
while Q:
    v=Q.popleft()
    y=1
    for w in E[v]:
        if not T[w]:
            T[w]=True
            Q.append(w)
            
            p,q=min(v,w),max(v,w)

            c=(A[v]+y)%M
            
            A[w]=c
            C[J[(p,q)]]=c
            G[p].add(c)
            G[q].add(c)
            y+=1

print(max(C)+1)
print("\n".join(map(lambda x:str(x+1),C)))
### BUGGY CODE ###

import sys

input = sys.stdin.readline

N = int(input())

Graph = [[] for _ in range(N)]
edges = []

for _ in range(N - 1):
  a, b = [int(x) - 1 for x in input().split()]
  edges.append((a, b))
  
for a, b in edges:
  Graph[a].append(b)
  Graph[b].append(a)
  
k = max(len(edges) for edges in Graph)

colors = {color for color in range(1, k + 1)}
usedcolor = [None for _ in range(N)]
colored = {}

for v in range(N):
  unused_colors = colors - { usedcolor[v] }
  for edge in Graph[v]:
    # 未着色
    if (v, edge) not in colored and (edge, v) not in colored:
      color = unused_colors.pop()
      colored[(v, edge)] = colored[(edge, v)] = color
      usedcolor[edge] = color

print(k)

for a, b in edges:
  print(colored[(a, b)])
  

### FIXED CODE ###

import sys

input = sys.stdin.readline

N = int(input())

Graph = [[] for _ in range(N)]
edges = []

for _ in range(N - 1):
  a, b = [int(x) - 1 for x in input().split()]
  edges.append((a, b))
  
for a, b in edges:
  Graph[a].append(b)
  Graph[b].append(a)
  
k = max(len(edges) for edges in Graph)

colors = [color for color in range(1, k + 1)]
usedcolor = [None for _ in range(N)]
colored = {}

def colors_except(x):
  for c in colors:
    if c == x:
      continue
    yield c

for v in range(N):
  unused_colors = colors_except(usedcolor[v])
  for edge in Graph[v]:
    # 未着色
    if (v, edge) not in colored and (edge, v) not in colored:
      color = next(unused_colors)
      colored[(v, edge)] = colored[(edge, v)] = color
      usedcolor[edge] = color

print(k)

for a, b in edges:
  print(colored[(a, b)])
### BUGGY CODE ###

S = input()

map_ = [-1] * 2019
map_[0] = 0
ans = 0

for i in range(1, len(S) + 1):
    temp = int(S[len(S) - i:])
    map_[temp % 2019] += 1
    ans += map_[temp % 2019]

print(ans)


### FIXED CODE ###

S = input()
N = len(S)

map_ = [-1] * 2019
map_[0] = 0
ans = 0
now = 0
for i in range(0, N):
    now = (now + int(S[N - i - 1]) * pow(10, i, 2019)) % 2019
    map_[now] += 1
    ans += map_[now]

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

def LI():
    return list(map(int, input().split()))


Q = int(input())
n = 10**5
sosu = set(range(2, n+1))
for i in range(2, int(n**0.5+1)):
    sosu.difference_update(range(i*2, n+1, i))
sosu = list(sosu)
for _ in range(Q):
    ans = 0
    L, R = LI()
    for i in range(L, R+1, 2):
        if i in sosu:
            if (i+1)//2 in sosu:
                ans += 1
    print(ans)


### FIXED CODE ###

from itertools import accumulate


def LI():
    return list(map(int, input().split()))


Q = int(input())
n = 10**5
sosu = set(range(2, n+1))
for i in range(2, int(n**0.5+1)):
    sosu.difference_update(range(i*2, n+1, i))
xlist = [0]*(10**5+1)
for i in range(1, 10**5+1, 2):
    if i in sosu:
        if (i+1)//2 in sosu:
            xlist[i] = 1
Xsum = list(accumulate(xlist))
for _ in range(Q):
    L, R = LI()
    ans = Xsum[R]-Xsum[L-1]
    print(ans)
### BUGGY CODE ###

import numpy as np
N = int(input().strip())
As = np.array(input().strip().split(" ")).astype(np.int32)
for i in range(1,N+1):
    indices = [j for j,val in enumerate(As) if val==i]
    print(len(indices))

### FIXED CODE ###

a=[0]*int(input())
for i in input().split(): a[int(i)-1]+=1
for i in range(len(a)): print(f'{a[i]}')
### BUGGY CODE ###

n = int(input())
s = input()
R = s.count("R")
G = s.count("G")
B = s.count("B")
cnt = 0
for i in range(n-1):
    for j in range(i+1,n):
        if 2*j - i <= n - 1:
            k = 2*j - i
            if len(set([s[i],s[j],s[k]])) == 3:
                cnt += 1
print(R*G*B - cnt)

### FIXED CODE ###

n = int(input())
s = input()
R = s.count("R")
G = s.count("G")
B = s.count("B")
cnt = 0
for i in range(n-1):
    for j in range(i+1,n):
        if j - i <= n - 1 - j:
            if s[i] != s[j] and s[j] != s[2*j - i] and s[i] != s[2*j - i]:
                cnt += 1
print(R*G*B - cnt)
### BUGGY CODE ###


import sys
sys.setrecursionlimit(10000000)
from collections import defaultdict
N,Q = map(int,input().split())

tree = defaultdict(list)
for i in range(N-1):
    a,b = map(int,input().split())
    tree[a].append(b)
    tree[b].append(a)

adds = {}
ans = {}
for i in range(1,N+1):
    adds[i] = 0
    ans[i] = 0
for q in range(Q):
    p,x = map(int,input().split())
    adds[p] += x

checked = [False for _ in range(N+1)]
def dig(i,tmp):
    tmp += adds[i]
    ans[i] = tmp
    checked[i] = True
    for v in tree[i]:
	    if not checked[v]: dig(v,tmp)

tmp = 0
dig(1,tmp)

print(' '.join(str(ans[i]) for i in range(1,N+1)))

### FIXED CODE ###

from queue import deque
N,Q = map(int,input().split())
tree = [[] for i in range(N+1)]
for i in range(N-1):
    a,b = map(int,input().split())
    tree[a].append(b)
    tree[b].append(a)

ans = {i+1:0 for i in range(N)}
for i in range(Q):
    p,x = map(int,input().split())
    ans[p] += x

checked = [False for i in range(N+1)]
myq = deque()
myq.append(1)

while myq:
    v = myq.pop()
    checked[v] = True
    for n in tree[v]:
        if not checked[n]:
            ans[n] += ans[v]
            myq.append(n)
print(' '.join(str(ans[i]) for i in range(1,N+1)))
### BUGGY CODE ###

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

ans = 0
for i in range(n - 1):
    ans += a[i] * sum(a[i + 1:])
    
ans %= 10**9 + 7
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
a = [i % (10**9 + 7) for i in a]
val = sum(a[1:])
l = [val]
for i in range(1, n):
    val -= a[i]
    l.append(val)
ans = 0
for i in range(n - 1):
    ans += a[i]*l[i]
    ans %= 10**9 + 7
print(ans)
### BUGGY CODE ###

class UnionFind:
  def __init__(self, size):
    self.parents = [x for x in range(size)]
    self.sizes = [1] * size
  
  def unite(self, a, b):
    if self.find(a) == self.find(b):
      return
    
    if self.size_of(a) > self.size_of(b):
      self.sizes[self.find(a)] += self.size_of(b)
      self.parents[self.find(b)] = self.find(a)
    else:
      self.sizes[self.find(b)] += self.size_of(a)
      self.parents[self.find(a)] = self.find(b)
  
  def is_same(self, a, b):
    return self.find(a) == self.find(b)
  
  def size_of(self, a):
    return self.sizes[self.find(a)]
  
  def find(self, a):
    if a == self.parents[a]:
      return a
    else:
      return self.find(self.parents[a])


N, M, K = map(int, input().split())

u = UnionFind(N)

# 自分自身・友達・ブロック関係のいずれかの場合はフラグ立つ
relations = [1 << i for i in range(N)]

for _ in range(M):
  a, b = map(int, input().split())
  a, b = a - 1, b - 1
  relations[a] |= 1 << b
  relations[b] |= 1 << a
  u.unite(a, b)
  
for _ in range(K):
  c, d = map(int, input().split())
  c, d = c - 1, d - 1
  
  # 同じ連結成分に含まれないブロック関係は無視してok
  if u.is_same(c, d):
    relations[c] |= 1 << d
    relations[d] |= 1 << c

candidates = []

for i in range(N):
  candidates.append(u.size_of(i) - bin(relations[i]).count('1'))
    
print(' '.join(str(x) for x in candidates))

### FIXED CODE ###

import sys
sys.setrecursionlimit(2 ** 30)
N, M, K = map(int, input().split())

groups = [None] * N
visited = set()

# 連結成分を求める
def dfs(group, i):
  if i in visited:
    return
  
  visited.add(i)
  group.add(i)
  groups[i] = group
  # 他のノード
  for c in graph[i]:
    if not c in visited:
      dfs(group, c)
  

graph = [set() for _ in range(N)]

friends_count = [0] * N
block_count = [0] * N

for _ in range(M):
  a, b = map(int, input().split())
  a, b = a - 1, b - 1
  friends_count[a] += 1
  friends_count[b] += 1
  graph[a].add(b)
  graph[b].add(a)
  
for i in range(N):
  dfs(set(), i)
      
for _ in range(K):
  c, d = map(int, input().split())
  c, d = c - 1, d - 1
  
  # 同じ連結成分に含まれないブロック関係は無視してok
  if d in groups[c]:
    block_count[c] += 1
    block_count[d] += 1

candidates = []

for i in range(N): 
  candidates.append(
    len(groups[i]) - friends_count[i] - block_count[i] - 1
  )
    
print(' '.join(str(x) for x in candidates))
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
s = sum(A)
ans = 0
for i in range(N):
    s = sum(A[i:N])
    s -= A[i]
    ans += A[i]*s
    
print(ans%((10**9)+7))

### FIXED CODE ###

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

ans = 0
s = sum(A)
for i in range(N-1):
    s -= A[i]
    ans += A[i]*s
    
print(ans%((10**9)+7))
### BUGGY CODE ###

n, k = map(int, input().split())
alist = list(map(int, input().split()))
alist.sort()

inf = int(1e+18) + 1
l = -inf
r = inf

while l + 1 < r:
    x = (l + r) // 2
    total = 0
    for i in range(n):
        if alist[i] < 0:
            ll = -1
            rr = n
            while ll + 1 < rr:
                xx = (ll + rr) // 2
                if alist[i] * alist[xx] < x:
                    rr = xx
                else:
                    ll = xx
            total += n - rr
        else:
            ll = -1
            rr = n
            while ll + 1 < rr:
                xx = (ll + rr) // 2
                if alist[i] * alist[xx] < x:
                    ll = xx
                else:
                    rr = xx
            total += rr
        if alist[i] * alist[i] < x:
            total -= 1
    total /= 2
    if total < k:
        l = x
    else:
        r = x

print(l)

### FIXED CODE ###

import numpy as np

n, k = map(int, input().split())
a = np.array(input().split(), np.int64)

a = np.sort(a)
zero = a[a == 0]
pos = a[a > 0]
neg = a[a < 0]

def f(x):
    """count the number of products , <= x"""
    cnt_tpl = 0
    # zero and ...
    if x >= 0:
        cnt_tpl += len(zero) * n
    # positive and ...
    cnt_tpl += np.searchsorted(a, x // pos, side='right').sum()
    # negative and ...
    cnt_tpl += (n - np.searchsorted(a, (-x - 1) // (-neg), side='right')).sum()
    # a^2
    cnt_tpl -= np.count_nonzero(a * a <= x)
    assert cnt_tpl % 2 == 0
    return cnt_tpl // 2

left = -10 ** 18
right = 10 ** 18
while left + 1 < right:
    x = (left + right) // 2
    if f(x) >= k:
        right = x
    else:
        left = x

print(right)
### BUGGY CODE ###

from collections import deque

H, W = map(int, input().split())
grid = [input() for i in range(H)]

# 初期の黒('#')の位置からの距離
dist = [[-1]*W for _ in range(H)]

# '#'の位置をキューに追加（＝今回はこれが複数あるので、複数スタートとなる）
black_cells = deque()
for h in range(H):
    for w in range(W):
        if grid[h][w] == '#':
            black_cells.append((h, w))
            dist[h][w] = 0

def bfs(black_cells, dist):
    """
    BFSを用いて、全マス目を黒くする回数を求める

    Args:
        black_cells: 「開始時の黒マス」の座標が入ったキュー（複数座標あり）
        dist: 「開始時の黒マス」からの距離の入ったリスト  [[-1, -1, 0], ...]
        　　　（白マスの初期値は0）

    Returns:
        g: 操作を繰り返した数
    """
    d = 0
    while black_cells:
        # キューとして使うのでpop()ではなくpopleft()
        h, w = black_cells.popleft()
        d = dist[h][w]
        for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
            new_h = h + dy
            new_w = w + dx
            if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
                continue
            if dist[new_h][new_w] == -1:  # セルが白('.')であるのと同義
                dist[new_h][new_w] = d+1
                black_cells.append((new_h, new_w))
    return d

d = bfs(black_cells, dist)
print(d)

### FIXED CODE ###

from subprocess import call
call(('pypy3','-c',"""
H,W=map(int,input().split())
A=[list(input()) for i in range(H)]
dy=[0,0,1,-1]
dx=[1,-1,0,0]
m=[[-1]*W for i in range(H)]

from collections import deque
q=deque()
for y in range(H):
  for x in range(W):
    if A[y][x]=='#':
      q.append((y,x))
      m[y][x]=0      
      
def bfs(q,m):
  d=0
  while q:
    y,x=q.popleft()
    d=m[y][x]
    for i in range(4):
      ny=y+dy[i]
      nx=x+dx[i]
      if 0<=ny<H and 0<=nx<W and m[ny][nx]==-1 and A[ny][nx]!='#':
        q.append((ny,nx))
        m[ny][nx]=m[y][x]+1            
bfs(q,m)
ans=0
for i in range(H):
  for j in range(W):
    ans=max(ans,m[i][j])    
print(ans)     
"""))
### BUGGY CODE ###

N, K = map(int, input().split())
h = list(map(int, input().split()))
 
dp = [1000000000] * N
dp[0] = 0
 
for i in range(N - 1):
    for j in range(1, K + 1):
        if i + j < N:
            if dp[i + j] > abs(h[i + j] - h[i]) + dp[i]:
                dp[i + j] = abs(h[i + j] - h[i]) + dp[i]
        else:
            break
 
print(dp[N - 1])

### FIXED CODE ###

N,K = map(int,input().split())
h = list(map(int,input().split()))
dp = [10**15+1 for i in range(N)]
dp[0] = 0
for i in range(N):
    for j in range(1,K+1):
        if i+j<N:
            dp[i+j] = min(dp[i+j],dp[i]+abs(h[i]-h[i+j]))
        
print(dp[-1])
### BUGGY CODE ###

n, m = map(int, input().split())
vote = n * [0]
for i in range(m):
    l, r = map(int, input().split())
    for j in range(l - 1, r):
        vote[j] += 1
print(vote.count(m))


### FIXED CODE ###

n, m = map(int, input().split())
max_value = 10 ** 5
min_value = 1
for i in range(m):
    l, r = map(int, input().split())
    min_value = max(min_value, l)
    max_value = min(max_value, r)

ans = max_value - min_value + 1
if ans < 0:
    ans = 0
print(ans)
### BUGGY CODE ###

S = list(input())
N = len(S)
count = 0
for i in range(N):
    for j in range(i + 3, N):
        if int("".join(S[i : j+1])) % 2019 == 0:
            count += 1

print(count)

### FIXED CODE ###

from collections import Counter
s = input()

n = len(s)
dp = [0] * (n + 1)

for i in range(n - 1, -1, -1):
    dp[i] = (dp[i + 1] + pow(10, (n - i - 1), 2019) * int(s[i])) % 2019

c = Counter(dp)

ans = 0
for i in c.values():
    ans += i * (i - 1) // 2

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

s = input()
K = int(input())
st = set()

for i in range(len(s)):
    for j in range(i,len(s)):
        st.add(s[i:j+1])
print(sorted(list(st))[K-1])

### FIXED CODE ###

s = input()
K = int(input())
ls = []

for i in range(1,K+1):
    for j in range(len(s)):
        ls.append(s[j:j+i])
print(sorted(set(ls))[K-1])
### BUGGY CODE ###

import fractions

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

def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]

import copy
N = int(input())
Ps = list(map(int,input().split(" ")))
org_Ps = copy.deepcopy(Ps)
prime_nums = primes(10 ** 5)

Ps.sort()
mul = 1
used = False
for p in prime_nums:
    used = False
    for i in range(len(Ps)):
        if Ps[i] %p == 0:
            Ps[i]//=p
            if not used:
                used = True
                mul *= p

MOD = 10 ** 9 + 7
g = 1

for p in Ps:
    g = g* p // fractions.gcd(g, p)
g *= mul
ans = 0

for p in org_Ps:
    ans += g//p
    ans %= MOD
ans %= MOD

print(ans)





### FIXED CODE ###

from fractions import gcd

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

N = int(input())
Ps = list(map(int,input().split(" ")))
MOD = 10 ** 9 + 7
g = 1
for p in Ps:
    g = lcm(g,p)
ans = 0

print(sum([g // p for p in Ps]) % (10 ** 9 + 7))
### BUGGY CODE ###

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

accurate = []
correct = 0
wrong = [0] * n
penalty = 0

for i in range(m):
    p,s = input().split()
    num = int(p) - 1 
    if s == 'AC' and num not in accurate:
        accurate.append(num)
        correct += 1
        penalty += wrong[num]
    elif s == 'WA' and num not in accurate:
        wrong[num] += 1 
    else:
        continue

print('{} {}'.format(correct,penalty))

### FIXED CODE ###

n, m = map(int, input().split())
ac = 0
wa = 0
 
ac_tf = [0] * n
wa_num = [0] * n
 
for i in range(m):
    p, s = input().split()
    p = int(p) - 1
    if s == "AC":
        if ac_tf[p] == 0:
            ac += 1
            wa += wa_num[p]
            ac_tf[p] = 1
    else:
        wa_num[p] += 1
            
print(ac, wa)
### BUGGY CODE ###

h,w = map(int,input().split())
#0が進めるところ、1は無理
#lis = [[1 if l == '#' else 0 for l in list(input())] for _ in range(h)]

road_count = 0
lis = [list('#'*(w+2))]
for _ in range(h):
    li = input()
    for i in li:
        if i == '.':
            road_count += 1
    li = '#' + li + '#'
    lis.append(list(li))
lis.append(list('#'*(w+2)))

#print(lis)
dp = [[0]*(w+2) for _ in range(h+2)]

#(開始x,開始y,移動回数)
step = [[1,1]]
while len(step)>0:
    x,y = step.pop(0)

    if x == h and y == w:
        print(road_count-dp[x][y]-1)
        exit()

    #探索済みのところは、#にする
    lis[x][y] = '#'


    if lis[x-1][y] != '#':
        step.append([x-1,y])
        dp[x-1][y] = dp[x][y]+1
    if lis[x+1][y] != '#':
        step.append([x+1,y])
        dp[x+1][y] = dp[x][y]+1
    if lis[x][y-1] != '#':
        step.append([x,y-1])
        dp[x][y-1] = dp[x][y]+1
    if lis[x][y+1] != '#':
        step.append([x,y+1])
        dp[x][y+1] = dp[x][y]+1
print(-1)


### FIXED CODE ###

h,w = (int(x) for x in input().split())
ab = []
count = 0
for _ in range(h):
    a = input()
    a = a+'#'
    ab.append(list(a))
    for i in a:
        if i == '.':
            count += 1
ab.append(list('#'*w))
dp = [[0 for i in range(w)] for j in range(h)]
 
step = [[0, 0]]
dp[0][0] = 1
 
while len(step) > 0:
    y, x = step.pop(0)
    if y == h-1 and x == w-1:
        print(count-dp[y][x])
        exit()
    if ab[y+1][x] == '.' and dp[y+1][x] == 0 :
        step.append([y+1, x])
        dp[y+1][x] = dp[y][x] + 1
    if ab[y][x+1] == '.' and dp[y][x+1] == 0 :
        step.append([y, x+1])
        dp[y][x+1] = dp[y][x] + 1
    if ab[y-1][x] == '.' and dp[y-1][x] == 0 :
        step.append([y-1, x])
        dp[y-1][x] = dp[y][x] + 1
    if ab[y][x-1] == '.' and dp[y][x-1] == 0 :
        step.append([y, x-1])
        dp[y][x-1] = dp[y][x] + 1
 
 
print(-1)
### BUGGY CODE ###

S = input()
ans = 0
for i in range(len(S)):
    for j in range(i+4,len(S)):
        if int(S[i:j+1]) % 2019 == 0:

            ans += 1
print(ans)
#3*673


### FIXED CODE ###

S = input()
mod = 2019

array = []
for i in range(len(S)):
    x = (int(S[len(S)-1-i])*pow(10,i,mod))%mod
    array.append(x)
array2 = [0]
y = 0
for i in range(len(S)):
    y = (y+array[i])%mod
    array2.append(y)
array3 = [0] * 2019
ans = 0
for i in range(len(array2)):
    z = array2[i]
    ans += array3[z]
    array3[z] += 1
print(ans)
#3*673