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

N, M = map(int, input().split())
NG = []
a = 10**9+7
for i in range(M):
  NG.append(int(input()))
ans = [0 for _ in range(N + 2)]
ans[0] = 1
for i in range(N):
  if not i + 1 in NG:
    ans[i + 1] = (ans[i + 1] + ans[i])%a
  if not i + 2 in NG:
    ans[i + 2] = (ans[i + 2] + ans[i])%a
print(ans[N])

### FIXED CODE ###

N, M = map(int, input().split())
NG = []
a = 10**9+7
NG = [True for _ in range(N + 2)]
for i in range(M):
  NG[int(input())] = False
ans = [0 for _ in range(N + 2)]
ans[0] = 1
for i in range(N):
  if NG[i + 1]:
    ans[i + 1] = (ans[i + 1] + ans[i])%a
  if NG[i + 2]:
    ans[i + 2] = (ans[i + 2] + ans[i])%a
print(ans[N])
### BUGGY CODE ###

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

l = []
for i in range(n):
    num = a[i]
    del a[i]
    ac = a.count(num)
    l.append((ac*(ac - 1) - ac*(ac + 1))//2)
    a.insert(0, num)

a.sort()
ans = 0
i = 0
while True:
    cnt = 0
    while a[i + cnt] == a[i]:
        cnt += 1
        if i + cnt == n:
            break
    ans += cnt*(cnt - 1)//2
    i += cnt
    if i == n:
        break

for i in l:
    print(ans + i)

### FIXED CODE ###

from collections import Counter
n = int(input())
a = list(map(int, input().split()))

d = Counter(a)
key = d.keys()
ans = 0
for i in key:
    ans += (d[i]*(d[i]  - 1))//2

for i in a:
    print(ans - d[i] + 1)
### BUGGY CODE ###

N, K= map(int, input().split())
h = list(map(int, input().split()))
import numpy as np
dp = np.zeros(N+1, dtype=int)
for i in range(1, N):
    dp[i+1] = min(
        [
            abs(h[i]-h[i-k]) + dp[i+1-k]
            for k in range(1, min(K, i)+1)
        ]
    )
print(dp[N])

### FIXED CODE ###

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

n=int(input())
ans={}
visited=[]
for _ in range(n):
    s="".join(sorted(list(input())))
    if s in visited:
      ans[s]+=1
    else:
      ans[s]=1
      visited.append(s)

count=0
for i in ans:
  count+=((ans[i]*(ans[i]-1))//2)
print(count)

### FIXED CODE ###

from collections import Counter
n=int(input())
s=[]
for _ in range(n):
    temp=sorted(list(input()))
    s.append("".join(temp))
s_count=Counter(s)
ans=0
for i in s_count:
    ans+=((s_count[i])*(s_count[i]-1))//2
print(ans)
### BUGGY CODE ###

r,g,b,n = map(int,input().split())
counter = 0
sorts = sorted([r,g,b],reverse=True)
a = (n // sorts[0])+1
c = (n// sorts[1])+1

for i in range(a):
    for j in range(c):
        left = n - (sorts[0]*i) - (sorts[1]*j)
        if left >= 0 and   left % sorts[2] == 0:
            counter += 1
            
print(counter)

### FIXED CODE ###

r,g,b,n = map(int,input().split())
counter = 0
sorts = sorted([r,g,b],reverse=True)
a = (n // sorts[0])+1

for i in range(a):
    test = n
    test = test-(sorts[0]*i)
    c = (test//sorts[1])+1
    for j in range(c):
        left = test - (sorts[1]*j)
        if left >= 0 and   left % sorts[2] == 0:
            counter += 1
            
print(counter)
### BUGGY CODE ###

MOD = 10**9 + 7


def ketadp3(a, b):
    L = len(str(a))

    dp = [[[0]*b for j in range(2)] for k in range(L + 1)]
    dp[0][0][0] = 1
    for i in range(L):
        D = int(str(a)[i]) 
        for j in range(2):
            for k in range(b):
                for d in range(10 if j else D+1):
                    dp[i + 1][j or (d < D)][((k + d) % b)] += dp[i][j][k]
                    dp[i + 1][j or (d < D)][((k + d) % b)] %= MOD

    return (dp[L][0][0] + dp[L][1][0] - 1) % MOD


def main():
    n = int(input())
    d = int(input())
    print(ketadp3(n, d))


if __name__ == '__main__':
    main()


### FIXED CODE ###

MOD = 10**9 + 7
def ketadp3(a, b):
    L = len(a)

    dp = [[[0 for i in range(2)] for j in range(b)] for k in range(L + 1)]
    dp[0][0][0] = 1
    for i in range(L):
        D = int(a[i])
        for k in range(b):
            for j in range(2):
                for d in range(10 if j else D+1):
                    dp[i + 1][(k + d) % b][j or (d < D)] += dp[i][k][j]
                    dp[i + 1][(k + d) % b][j or (d < D)] %= MOD

    print((dp[L][0][0] + dp[L][0][1] - 1) % MOD)


def main():
    n = input()
    d = int(input())
    ketadp3(n, d)


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

n,k=(input().split())
a=list(map(int,input().split()))
pdt=a
p=1
for i in range(int(n)):
  p*=a[i]
  pdt[i]=p
j=0  
for i in range(int(k),int(n)):
  a[i]=pdt[i]/a[j]
  #print(a[i],a[j],a[i-1])
  j+=1
  if(a[i]>a[i-1]):
    print("Yes")
  else:
    print("No")  



### FIXED CODE ###

n,k=(input().split())
a=list(map(int,input().split()))
#pdt=a
#p=1
j=0  
for i in range(int(k),int(n)):
  if(a[i]>a[j]):
    print("Yes")
  else:
    print("No")  
  j+=1
### BUGGY CODE ###

import numpy as np

def main():
    n = int(input())
    a = np.zeros([n], dtype=int)
    # box = np.array(range(1,n+1))
    a = list(map(int, input().split(" ")))
    b = np.zeros_like(a)

    for i in range(n//2, n):
        if a[i] == 1:
            b[i] = 1

    for i in range(1,n+1)[::-1]:
        if np.sum(b[i-1::i])%2 != a[i-1]:
            b[i-1] = 1

    ball = np.where(b==1)[0]
    print(len(ball))
    for i in ball:
        print(i+1, end=" ")
        
if __name__ == "__main__":
    main()

### FIXED CODE ###

import numpy as np

def main():
    n = int(input())
    a = np.zeros([n], dtype=int)
    # box = np.array(range(1,n+1))
    a = list(map(int, input().split(" ")))
    b = np.zeros_like(a)

    for i in range(n//2, n):
        if a[i] == 1:
            b[i] = 1

    for i in range(1,n//2+1)[::-1]:
        if np.sum(b[i-1::i])%2 != a[i-1]:
            b[i-1] = 1

    ball = np.where(b==1)[0]
    print(len(ball))
    for i in ball:
        print(i+1, end=" ")
        
if __name__ == "__main__":
    main()
### BUGGY CODE ###

a,aa=map(int,input().split())
b=list(map(int,input().split()))
c=[1000000007 for i in range(a)]
c[0]=0
for i in range(1,a):
  for j in range(1,aa+1):
    if i-j<0:
      break
    else:
      c[i]=min(c[i-j]+abs(b[i]-b[i-j]),c[i])
  
print(c[-1])

### FIXED CODE ###

def solve():
  a,aa=map(int,input().split())
  b=list(map(int,input().split()))
  c=[0]*a
  c[0]=0
  for i in range(1,a):
    c[i] = min(c[j] + abs(b[i] - b[j]) for j in range(max(0,i-aa),i))
  print(c[-1])
  
solve()
### BUGGY CODE ###

import sys
from sys import stdin
input = stdin.readline

def solve(N, A, x):
    x.append(0)
    x.sort()
    W=sum(x)
    dp=[[[0]*(W+1) for _ in range(N+1)] for _ in range(N+1)]
    for j in range(N+1):
        dp[j][0][0]=1
    for j in range(1,N+1):
        xj=x[j]
        for k in range(1, N+1):
            for s in range(1, W+1):
                if s<xj:
                    dp[j][k][s]=dp[j-1][k][s]
                else:
                    dp[j][k][s]=dp[j-1][k][s]+dp[j-1][k-1][s-xj]

    ans=0
    for k in range(1,N+1):
        if k*A<=W:
            ans+=dp[N][k][k*A]
        else:
            break
    return ans


def main(args):
    N,A=map(int, input().split())
    x=[int(x) for x in input().split()]
    print(solve(N, A, x))

if __name__ == '__main__':
    main(sys.argv[1:])


### FIXED CODE ###

import sys
from sys import stdin
input = stdin.readline

def solve(N, A, x):
    W=sum(x)
    dp=[[[0]*(W+1) for _ in range(N+1)] for _ in range(N+1)]
    for j in range(N+1):
        dp[j][0][0]=1
    for j in range(1,N+1):
        xj=x[j-1]
        for k in range(1, N+1):
            for s in range(1, W+1):
                if s<xj:
                    dp[j][k][s]=dp[j-1][k][s]
                else:
                    dp[j][k][s]=dp[j-1][k][s]+dp[j-1][k-1][s-xj]

    ans=0
    for k in range(1,N+1):
        if k*A<=W:
            ans+=dp[N][k][k*A]
        else:
            break
    return ans


def main(args):
    N,A=map(int, input().split())
    x=[int(x) for x in input().split()]
    ans=solve(N,A,x)
    print(ans)

if __name__ == '__main__':
    main(sys.argv[1:])
### BUGGY CODE ###

h,w = map(int, input().split())
maze = [input() for i in range(h)]
route = [[0] * w for i in range(h)]
 
black_list = []
for i in range(h):
    for j in range(w):
        if maze[i][j] == '#':
            black_list.append([i+1,j+1])
 
class MyStack:
    def __init__(self):
        self.stack = []
    def push(self, item_1, item_2):
        self.stack.append([item_1,item_2])
    def pop(self):
        result = self.stack.pop(0)
        return result[0],result[1]

 
ans = 0
stack = MyStack()
for black in black_list:
        stack.push(black[0],black[1])
while stack.stack:
    y,x = stack.pop()
    route_num = route[y-1][x-1] + 1
    if y != h:
        if maze[y][x-1] == '.' and route[y][x-1] == 0:
            stack.push(y+1,x)
            route[y][x-1] = route_num
            ans = max(ans,route[y][x-1])
            
    if y != 1:
        if maze[y-2][x-1] == '.' and route[y-2][x-1] == 0:
            stack.push(y-1,x)
            route[y-2][x-1] = route_num
            ans = max(ans,route[y-2][x-1])
            
    if x != w:
        if maze[y-1][x] == '.' and route[y-1][x] == 0:
            stack.push(y,x+1)
            route[y-1][x] = route_num
            ans = max(ans,route[y-1][x])

    if x != 1:
        if maze[y-1][x-2] == '.' and route[y-1][x-2] == 0:
            stack.push(y,x-1)
            route[y-1][x-2] = route_num
            ans = max(ans,route[y-1][x-2])
            

print(ans)

### FIXED CODE ###

from subprocess import call
call (('pypy3', '-c', """
from collections import deque
 
def main():
    h, w = map(int, input().split())
    A = [list(input()) for _ in range(h)]
    d = [[10**9] * w for _ in range(h)]
    que = deque([])
    
    for i in range(h):
        for j in range(w):
           if A[i][j] == "#":
               que.append([i, j])
               d[i][j] = 0
           else:
               d[i][j] = 10 ** 9
            
    while que:
        x, y = que.popleft()
        dx = [1, 0, -1, 0]
        dy = [0, 1, 0, -1]
        for i in range(4): 
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < h and 0 <= ny < w and d[nx][ny] == 10**9:
                d[nx][ny] = d[x][y] + 1
                que.append([nx, ny])
    ans = 0
    for i in range(h):
        for j in range(w):
            ans = max(ans, d[i][j])
    print(ans)
    
    return
    
main()
 
"""))
### BUGGY CODE ###

N, K = map(int, input().split())
lis = list(map(int, input().split()))
p = 10**9+7
fac_lis = [[0] for i in range(N)]
fac_lis[0] = 1
max_ans = 0
min_ans = 0

for i in range(1,N):
  fac_lis[i] = fac_lis[i-1]*(i+1)

def combi(n,k):
  if n == k:
    return 1
  else:
  	return fac_lis[n-1]*pow(fac_lis[k-1], p-2, p)*pow(fac_lis[n-k-1], p-2, p) % p

lis.sort()
for i in range(K-1,N):
  max_ans += lis[i]*combi(i, K-1) % p
  
for i in range(N-K+1):
  min_ans += lis[i]*combi(N-(i+1), K-1) % p

ans = (max_ans - min_ans) % p
print(ans)

### FIXED CODE ###

# フェルマーの小定理
N, K = map(int, input().split())
A = list(map(int, input().split()))
 
m = 1000000007
 
fac = [0] * (N + 1)
fac[0] = 1
for i in range(N):
    fac[i + 1] = fac[i] * (i + 1) % m
 
 
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], m - 2, m) * pow(fac[k], m - 2, m) % m
 
 
A.sort(reverse=True)
maxX = 0
for i in range(N - K + 1):
    maxX += A[i] * mcomb(N - (i + 1), K - 1)
    maxX %= m

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

print((maxX - minX) % m)
### BUGGY CODE ###

from collections import deque
N = int(input())
K = list(sorted(map(int, input().split()), reverse=True))

max1 = K[0]
max2 = K[1]
if N == 2:
    print(max1)
else:
    max3 = K[2]
    count = max1 + max2
    cands = [(max1, max2), (max2, max3)]
    for k in K[3:]:
        max_cand = (0, 0)
        max_i = -1
        for i, cand in enumerate(cands):
            if min(cand) > min(max_cand):
                max_cand = cand
                max_i = i
        hi, lo = max_cand
        count += lo
        cands.pop(max_i)
        cands.append((hi, k))
        cands.append((lo, k))
    print(count)


### FIXED CODE ###

from collections import deque
N = int(input())
K = list(sorted(map(int, input().split()), reverse=True))

max1 = K[0]
max2 = K[1]
if N == 2:
    print(max1)
else:
    max3 = K[2]
    count = max1 + max2
    cands = deque([max2, max3, max3])
    for k in K[3:]:
        cand = cands.popleft()
        count += cand
        cands.append(k)
        cands.append(k)
    print(count)
### BUGGY CODE ###

n,q=map(int,input().split())
s=input()
l=[]
for i in range(q):
  l.append(tuple(map(int,input().split())))
for j in range(q):
  x,y=l[j]
  counting=0
  a=s[x-1:y]
  for i in range(y-x):
    if a[i:i+2]=='AC':
      counting+=1
  print(counting)

### FIXED CODE ###

import bisect
n,q=map(int,input().split())
s=input()
slst=[]
cnt=[]
for i in range(n-1):
  slst.append(s[i:i+2])
for a,b in enumerate(slst):
  if b=='AC':
    cnt.append(a)
l=[]
for i in range(q):
  x,y=map(int,input().split())
  M=bisect.bisect_left(cnt,x-1)
  N=bisect.bisect_right(cnt,y-2)
  print(N-M)
### BUGGY CODE ###

import queue

d={}
q=queue.Queue()
n=int(input())
nums=list(map(int,input().split()))
for a in nums:    
    if not a in d:
        d[a]=1
    else:
        d[a]+=1
    q.put(a)

while not q.empty():
    answer=0
    p=q.get()
    for num,count in d.items():
        if p==num:
            answer+=int((count-1)*(count-2)/2)
        else:
            answer+=int(count*(count-1)/2)
    print(answer)

### FIXED CODE ###

d={}
s=[]

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

for a in nums:    
    if not a in d:
        d[a]=1
    else:
        d[a]+=1
    s.append(a)
    
allcount=0

for count in d.values():
    allcount+=int(count*(count-1)/2)

for num in s:
    print(allcount-d[num]+1)
### BUGGY CODE ###

import numpy as np
import math
import sys
sys.setrecursionlimit(10000000)
from bisect import bisect_left, bisect_right

def main():
    N = int(input())
    L = [int(c) for c in input().split()]
    L = sorted(L)
    num = 0
    for ai in range(N):
        for bi in range(ai+1, N):
            if bi - ai == 1:
                continue
            a = L[ai]
            b = L[bi]
            ci_left = bisect_right(L, abs(L[ai] - L[bi]))
            ci_right = bisect_left(L, L[ai] + L[bi])
            if ci_left == ci_right:
                continue
            else:
                ci_left = max(ci_left, ai + 1)
                ci_right = min(ci_right, bi)
            # print(a, b, ci_left, min(ci_right, bi) - max(ci_left, ai) - 1)
            # num += min(ci_right, bi) - max(ci_left, ai) - 1
                num += ci_right - ci_left
            # print(a, b, ci_right, ci_left, num)

    print(num)


if __name__ == '__main__':
    main()

### FIXED CODE ###

import bisect

def main():
    N = int(input())
    L = [int(i) for i in input().split()]
    L.sort()
    count = 0
    for i in range(N-2):
        for j in range(i+1, N-1):
            k = bisect.bisect_left(L, L[i] + L[j])
            k -= 1
            count += k - j
    print(count)


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

# Bugged

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

import numpy as np

ss = sorted(s ,reverse=True)
l  = len(s)
f = 2**l-1
for i in range(2**l):
    ff = list(map(int,list(format(f,'b').zfill(3))))
    a = np.sum(np.array(ff)*np.array(ss))
    if ( a%10!=0 or a==0):
        print(a)
        break
    f-=1

### FIXED CODE ###

# Bugged

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

a = []
for ss in s:
    if ( ss%10!=0 ):
        a.append(ss)
ssum = sum(s)
if ( ssum%10!=0 ):
    print(ssum)
else:
    if ( len(a)==0 ):
        print(0)
    else:
        print(ssum-min(a))
### BUGGY CODE ###

def Prime(x):
   if x == 2:
      return 1
   elif (x<2) or (x%2==0):
      return 0
   else:
      i = 3
      while i <= x**0.5:
         if x%i == 0:
            return 0
         i = i + 2
      return 1

Q = int(input())
l_r = []
for i in range(Q):
   l_r.append(list(map(int, input().split())))

like_Number = []

X_mem = []
X_mem_non = []
for l_r in l_r:
   l = l_r[0]
   r = l_r[1]
   count = 0
   for x in range(l, r+1):
      if x%2 == 1: # 奇数だけ
         if x in X_mem:
            count = count + 1
         elif (x in X_mem_non) == False:
            if Prime(x) == 1:
               if Prime((x+1)/2) == 1:
                  X_mem.append(x)
                  count = count + 1
               else:
                  X_mem_non.append(x)
            else:
               X_mem_non.append(x)

   like_Number.append(count)

for i in range(Q):
   print(like_Number[i])
         


### FIXED CODE ###

def main():
    Q = int(input())
    L = [0 for _ in range(Q)]
    R = [0 for _ in range(Q)]
    for i in range(Q):
        L[i], R[i] = map(int, input().split())

    N = 100000
    sosu = [1 for _ in range(N)]
    sosu[0] = 0
    for i in range(1,int(N**0.5)):
        k = i+1
        if sosu[i] == 1:
            j = k + k
            while j <= N:
                sosu[j-1] = 0
                j = j+k
    like = [0 for _ in range(N)]
    for i in range(2, N, 2):
        if sosu[i]==1 and sosu[(i+2)//2-1]==1:
            like[i] = 1
    like_wa = [0 for _ in range(N+1)]
    for i in range(N):
        like_wa[i+1] = like_wa[i] + like[i]

    for i in range(Q):
        print(like_wa[R[i]] - like_wa[L[i]-1])

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

A,B,C,K = map(int,input().split())
ans = 0
for i in range(A):
    if K == 0:
        break
    ans += 1
    K -= 1

for j in range(B):
    if K == 0:
        break
    K -= 1

for k in range(C):
    if K == 0:
        break
    ans -= 1
    K -= 1        
print(ans)

### FIXED CODE ###

A,B,C,K = map(int,input().split())

if K <= A:
    print(K)
elif K <= A + B:
    print(A)
else:
    print(2*A+B-K)
### BUGGY CODE ###

def main():
  _map = map
  _range = range
  _len = len
  _max = max
  _input = input
  _int = int
  n, m = _map(_int, _input().split())
  d1 = [None] * (m + 1)
  for _ in _range(n):
    a, b = _map(_int, _input().split())
    if a > m:
      continue
    if d1[a] is None:
      d1[a] = [b]
    else:
      d1[a].append(b)
  result = 0
  d2 = {}
  maxb = -1
  for i in _range(1, m + 1):
    if d1[i] is None:
      if _len(d2) == 0:
        continue
    else:
      for j in d1[i]:
        if j not in d2:
          d2[j] = 1
        else:
          d2[j] += 1
        if j > maxb:
          maxb = j
    result += maxb
    d2[maxb] -= 1
    if d2[maxb] == 0:
      del d2[maxb]
      if _len(d2) == 0:
        maxb = -1
      else:
        maxb = _max(d2.keys())
  print(result)
main()

### FIXED CODE ###

n, m = map(int, input().split())
d1 = {}
for _ in range(n):
  a, b = map(int, input().split())
  if a in d1:
    d1[a].append(b)
  else:
    d1[a] = [b]
result = 0
d2 = {}
maxb = -1
for i in range(1, m + 1):
  if i in d1:
    for j in d1[i]:
      if j not in d2:
        d2[j] = 0
      d2[j] += 1
      if j > maxb:
        maxb = j
  else:
    if len(d2) == 0:
      continue
  result += maxb
  if d2[maxb] == 1:
    del d2[maxb]
    if len(d2) == 0:
      maxb = 0
    else:
      maxb = max(d2.keys())
  else:
    d2[maxb] -= 1
print(result)
### BUGGY CODE ###

# E - Flatten

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

modulus = 10 ** 9 + 7
MAX = 10 ** 6

primefact = [0 for i in range(MAX + 1)]

def sieve():
    # cf. https://www.geeksforgeeks.org/lcm-of-n-numbers-modulo-m/
    for i in range(2, MAX + 1):
        if primefact[i] == 0:
            for j in range(i, MAX + 1, i):
                if primefact[j] == 0:
                    primefact[j] = i

def factorize(x):
    if primefact[2] == 0:
        sieve()

    vec = {}
    while x >= 2:
        d = primefact[x]
        if d not in vec:
            vec[d] = 0
        vec[d] += 1
        x //= d
    return vec

def lcm(x, y):
    vec = {i: x[i] for i in x}
    for i in y:
        vec[i] = max(x[i] if i in x else 0, y[i])
    return vec

def div(x, y):
    vec = {i: x[i] for i in x}
    for i in y:
        vec[i] -= y[i]
    return vec

def value(x):
    p = 1
    for i in x:
        p *= (i ** x[i]) % modulus
    return p

fact = [factorize(x) for x in a]

l = {}
for f in fact:
    l = lcm(l, f)

s = sum(value(div(l, f)) for f in fact) % modulus
print(s)


### FIXED CODE ###

# E - Flatten

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

modulus = 10 ** 9 + 7
binmod = (bin(modulus - 2))[2:]  # modulus - 2 in binary

MAX = 10 ** 6

primefact = [0 for i in range(MAX + 1)]

def sieve():
    # cf. https://www.geeksforgeeks.org/lcm-of-n-numbers-modulo-m/
    for i in range(2, MAX + 1):
        if primefact[i] == 0:
            for j in range(i, MAX + 1, i):
                if primefact[j] == 0:
                    primefact[j] = i

def factorize(x):
    if primefact[2] == 0:
        sieve()

    vec = {}
    while x >= 2:
        d = primefact[x]
        if d not in vec:
            vec[d] = 0
        vec[d] += 1
        x //= d
    return vec

def value(x):
    p = 1
    for i in x:
        p = (p * (i ** x[i])) % modulus
    return p

def inverse(x):
    p = 1
    for b in binmod:
        p = p * p % modulus
        if b == '1':
            p = p * x % modulus
    return p

def div(n, d):
    return n * inverse(d) % modulus

fact = [factorize(x) for x in a]

fset = set()
for f in fact:
    fset.update(f.keys())

l = {k: 0 for k in fset}
for f in fact:
    for k in f:
        l[k] = max(l[k], f[k])
lcm = value(l)

s = sum(div(lcm, x) for x in a) % modulus
print(s)
### BUGGY CODE ###

N,K = map(int,input().split( ))
A = list(map(int,input().split( )))
start = 1
for i in A[:K]:
    start *= i
for tail,head in zip(A,A[K:]):
    if start < start/tail*head:
        print('Yes')
    else:
        print('No')
    start = start/tail*head

### FIXED CODE ###

N,K = map(int,input().split( ))
A = list(map(int,input().split( )))
for tail,head in zip(A,A[K:]):
    if tail < head:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

n = int(input())
s = [''.join(sorted(input())) for _ in range(n)]
ans = map(lambda x: s.count(x)-1, set(s))
ans = sum(map(lambda x: int(x*(x+1)/2), ans))

print(ans)

### FIXED CODE ###

n = int(input())
s = [''.join(sorted(input())) for _ in range(n)]
t = {}

for i in range(n):
    if s[i] in t:
        t[s[i]] += 1
    else:
        t[s[i]] = 1
ans = sum((i * (i - 1)) // 2 for i in t.values())

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

import sys

sys.setrecursionlimit(10 ** 7)

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

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

K = min(K, 100)

for _ in range(K):
    imos = [0] * (N + 1)

    for i in range(N):
        a = A[i]
        s = max(0, i - a)
        e = min(N, i + a + 1)
        imos[s] += 1
        imos[e] -= 1

    nxt = [0] * N
    t = 0
    for i in range(N):
        t += imos[i]
        nxt[i] = t

    A = nxt

print(" ".join(map(str, A)))


### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 7)

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

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

K = min(K, 100)

for _ in range(K):
    imos = [0] * (N + 1)

    for i in range(N):
        a = A[i]
        s = max(0, i - a)
        e = min(N, i + a + 1)
        imos[s] += 1
        imos[e] -= 1

    nxt = [0] * N
    t = 0
    for i in range(N):
        t += imos[i]
        nxt[i] = t

    A = nxt

print(" ".join(map(str, A)))