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

N,Q=map(int,input().split())
S=input()
s_cnt=[]
cnt=0
for i in range(N-1):
    if S[i]=="A" and S[i+1]=="C":
        s_cnt.append(1)
    else:
        s_cnt.append(0)
for i in range(Q):
    l,r=map(int,input().split())
    print(sum(s_cnt[l-1:r-1]))

### FIXED CODE ###

N,Q=map(int,input().split())
S=input()
s_cnt=[]
cnt=0
for i in range(N-1):
    if S[i]=="A" and S[i+1]=="C":
        cnt+=1
        s_cnt.append(cnt)
    else:
        s_cnt.append(cnt)
for i in range(Q):
    l,r=map(int,input().split())
    l-=2
    r-=2
    if l<0:
        print(s_cnt[r])
    else:    
        print(s_cnt[r] - s_cnt[l])
### BUGGY CODE ###

s=input()
t=input()
n=len(s)
m=len(t)
dp=[["" for _ in range(n+1)] for _ in range(m+1)]
for i in range(m):
    for j in range(n):
        if t[i] == s[j]:
            dp[i+1][j+1] = dp[i][j] + t[i]
        else:
            if len(dp[i+1][j]) >= len(dp[i][j+1]):
                dp[i+1][j+1] = dp[i+1][j]
            else:
                dp[i+1][j+1] = dp[i][j+1]
        dp[i][j]=0
    dp[i][n]=0
print(dp[-1][-1])

### FIXED CODE ###


s=input()
t=input()
n=len(s)
m=len(t)
dp=[[0 for _ in range(n+1)] for _ in range(m+1)]
for i in range(m):
    for j in range(n):
        if t[i] == s[j]:
            dp[i+1][j+1] = dp[i][j] + 1
        else:
            dp[i+1][j+1] = max(dp[i+1][j],dp[i][j+1])
r=m
c=n
ans=[]
while r !=0 and c!=0:
    #print(r,c,dp[r][c],dp[r-1][c])
    if dp[r][c] != dp[r-1][c]:
        if dp[r][c] != dp[r][c-1]:
            ans.append(s[c-1])
            r-=1
            c-=1
        else:
            c-=1
    else:
        r-=1
print("".join(ans[::-1]))
### BUGGY CODE ###

import sys

while 1:
  n=input()
  if n==0:break
  A=[raw_input() for i in range(n)]
  B=[]
  c=0
  for i in range(n):
    if c==0 and '1' in A[i]: c=1
    B.append(int(A[i].replace('.','1').replace('*','0'),2))
  C=B[:]
  for i in range(1,n):
    for j in range(n-i):
      B[j]&=B[j+1]
      if '1'*(i+1) in format(B[j],'b'): c=i+1
  print c

### FIXED CODE ###

import sys

while 1:
  n = input() + 1
  if n==1: break
  N = range(n)
  M = [0] * n
  y = [0] * n
  for i in N[1:]:
    x = [0] * n
    A = ' ' + raw_input()
    for j in N[1:]:
      if A[j] == '.': x[j] = min(y[j-1],y[j],x[j-1]) + 1
    M[i]=max(x)
    y = x
  print max(M)
### BUGGY CODE ###

import math

N = int(input())
s = 0

def devisor(x):
    count = 0
    for i in range(1,math.floor(math.sqrt(x))+1):
        if (x % i) == 0:
            count += 2
            if i**2 == x:
                count -= 1
    return count

for i in range(1, N+1):
    s += i * devisor(i)

print(s)

### FIXED CODE ###

import math

N = int(input())
s = 0

# def devisor(x):
#     count = 0
#     for i in range(1,math.floor(math.sqrt(x))+1):
#         if (x % i) == 0:
#             count += 2
#             if i**2 == x:
#                 count -= 1
#     return count

# for i in range(1, N+1):
#     s += i * devisor(i)

for i in range(1,N+1):
    y = math.floor(N/i)
    s += y*(y+1)*i//2

print(s)
### BUGGY CODE ###

n,m=map(int,input().split())
A=list(map(int,input().split()))
for i in range(m):
    a=max(A)
    y=A.index(max(A))
    A[y]=a//2
print(sum(A))

### FIXED CODE ###

from heapq import heappop, heappush
n,m=map(int,input().split())
A=list(map(int,input().split()))
B=sorted(map(lambda x: x * -1, A))
for i in range(m):
    a=heappop(B)
    a=-(-a//2)
    heappush(B,a)
print(-sum(B))
### BUGGY CODE ###

K,S = map(int,input().split(" "))
ans = 0
for x in range(K + 1):
  for y in range(K + 1):
    for z in range(K + 1):
      if x + y + z == S:
        ans += 1
print(ans)
      

### FIXED CODE ###

K,S = map(int,input().split(" "))
ans = 0
for x in range(K + 1):
  for y in range(K + 1):
      if  0 <= S - (x + y) <= K:
        ans += 1
print(ans)
### BUGGY CODE ###

N, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(N)]
#品物は0～N-1と考えるので注意！

#合計pwsumの重さ、合計pvsumの価値を入れた状態で、
#depth以降の品物を選ぶ場合の最大価値を返す関数
def calc(depth, pwsum, pvsum):
  nowWei, nowVal = wv[depth] #今選んでる品物のこと
  if pwsum + nowWei > W:
    #入れると重さ超過なので、入れずに次を考える
    if depth >= N-1: return pvsum
      #今の品物が最後なら、そのまま返す
    else:
      #次の品物がある場合、今のを入れずに次へいく
      irenai = calc(depth+1, pwsum, pvsum)
      return irenai
  if pwsum + nowWei <= W:
    #入れても大丈夫な場合
    if depth >= N-1: return pvsum+nowVal
      #今の品物が最後なら、今の品物を入れて返す
    else:
      #次の品物がある場合、今のを入れる入れないの2択
      ireru = calc(depth+1, pwsum+nowWei, pvsum+nowVal)
      irenai = calc(depth+1, pwsum, pvsum)
      return max(ireru, irenai)
    
print(calc(0, 0, 0))

### FIXED CODE ###

N, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(N)]
#品物は0～N-1と考えるので注意！

DP = [0]*(W+1) #0~W
#各iにつき、残り重さがWの時の最大価値をDPに入れる


#i=N-1までいった時のmax(DP)が答え
for i in range(0, N, 1): #0~N-1
  w, v = wv[i]
  #残りwei(W-DPの2個目の添字)がw未満の場合入れられない
  #入れない場合は変えなければいい
  for nw in range(W, w-1, -1):
    iretaV = DP[nw-w] + v
    if iretaV > DP[nw]:
      DP[nw] = iretaV

print(max(DP))
### BUGGY CODE ###

N=int(input())
S=input()
a=300000
for i in range(N):
  t=S[:i].count("W")+S[i+1:].count("E")
  if t<a:
    a=t
print(a)

### FIXED CODE ###

N = int(input())
S = input()

W = [0 for k in range(N)]
E = [0 for k in range(N)]

for k in range(1,N):
    if S[k-1] == "W":
        W[k] = W[k-1] + 1
    else:
        W[k] = W[k-1]

for k in range(1,N):
    if S[N-k] == "E":
        E[N-k-1] = E[N-k] + 1
    else:
        E[N-k-1] = E[N-k]

ans = 10**9
for k in range(N):
    ans = min(W[k]+E[k],ans)

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

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

INF = float('inf')
dp = [[INF] * (n+10) for _ in range(n)]

for i in range(n):
    for k in range(n):
        if k == 0:
            dp[i][k] = a[i]
        else:
            dp[i][k] = min(dp[i][k-1], a[(i-k)%n])

ans = INF

for k in range(n):
    tmp = x * k
    for i in range(n):
        tmp += dp[i][k]
    ans = min(ans, tmp)

print(ans)


### FIXED CODE ###

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

INF = float('inf')
dp = [[INF] * (n+10) for _ in range(n)]

for i in range(n):
    for k in range(n):
        if k == 0:
            dp[i][k] = a[i]
        else:
            dp[i][k] = min(dp[i][k-1], a[(i-k)%n])

ans = INF

for k in range(n):
    tmp = x * k
    for i in range(n):
        tmp += dp[i][k]
    ans = min(ans, tmp)

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

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

from collections import Counter
def factorize(n):
    d = Counter()
    m = 2
    while m*m <= n:
        while n%m == 0:
            n //= m
            d[m] += 1
        m += 1
    if n > 1:
        d[n] += 1
    return d

factors = [None] * N

lcms = Counter()
for i,a in enumerate(A):
    factors[i] = factorize(a)
    for k,v in factors[i].items():
        if k in lcms:
            lcms[k] = max(lcms[k], v)
        else:
            lcms[k] = v

ans = 0
for fs in factors:
    a = 1
    for k,v in lcms.items():
        a *= pow(k, v - fs[k], MOD)
    ans += a
    ans %= MOD
print(ans)

### FIXED CODE ###

from fractions import gcd
N = int(input())
A = list(map(int,input().split()))
MOD = 10**9+7

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

ans = 0
for a in A:
    ans += lcm // a
ans %= MOD
print(ans)
### BUGGY CODE ###

from bisect import bisect_left
n = int(input())
ans = [int(input())]
for i in range(n-1):
    now = int(input())
    j = bisect_left(ans,now)
    if j == 0:
        ans.insert(0,now)
    else:
        ans[j-1] = now

print(len(ans))

### FIXED CODE ###

def bisect_right(a, x, lo=0, hi=None):
    """Return the index where to insert item x in list a, assuming a is sorted.

    The return value i is such that all e in a[:i] have e <= x, and all e in
    a[i:] have e > x.  So if x already appears in the list, a.insert(x) will
    insert just after the rightmost x already there.

    Optional args lo (default 0) and hi (default len(a)) bound the
    slice of a to be searched.
    """

    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if x < a[mid]: hi = mid
        else: lo = mid+1
    return lo

n = int(input())
f = int(input())
ans = [-f]
for i in range(n-1):
    now = -int(input())
    j = bisect_right(ans,now)
    if j == len(ans):
        ans.append(now)
    else:
        ans[j] = now

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

n = int(input())
s = list(input() for _ in range(n))
s.sort()
a = [0]
for i in range(n-1):
  if s[i] != s[i+1]:
    a.append(i+1)
l = int(len(a))
t = 0
b = []
for u in range(l):
  p = s.count(s[a[u]])
  if t<p:
    t=p
    b.clear()
    b.append(a[u])
  elif t==p:
    b.append(a[u])
k = int(len(b))    
for r in range(k):
    print(s[b[r]])

### FIXED CODE ###

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

c = collections.Counter(s)
l=c.most_common()
x=[l[0][0]]
for i in range(1,len(l)):
  if l[i-1][1]==l[i][1]:
    x.append(l[i][0])
  else:
    break
x.sort()    
for i in x:
  print(i)
### BUGGY CODE ###

def solve():
    from sys import stdin
    f_i = stdin
    
    mod = 10 ** 9 + 7
    
    N, K = map(int, f_i.readline().split())
    A = sorted(map(int, f_i.readline().split()))
    
    comb = 1
    ans = A[K-1] - A[N-K]
    for i, j in zip(range(K, N), range(1, N)):
        comb = comb * i // j
        ans += (A[i] - A[N-i-1]) * comb
        ans %= mod
    
    print(ans)

solve()

### FIXED CODE ###

def solve():
    from sys import stdin
    f_i = stdin
    
    mod = 10 ** 9 + 7
    
    N, K = map(int, f_i.readline().split())
    A = sorted(map(int, f_i.readline().split()))
    
    comb = 1
    ans = A[K-1] - A[N-K]
    for i, j in zip(range(K, N), range(1, N)):
        comb = comb * i * pow(j, mod - 2, mod) % mod
        ans += (A[i] - A[N-i-1]) * comb
        ans %= mod
    
    print(ans)

solve()
### BUGGY CODE ###

n=int(input())
from math import sqrt
for k in range(1,n+1):

    ans=0
    p=int(sqrt(k))
    for x in range(1,p+1):
        l=k-x**2
        if l<=0:
            break

        for y in range(1,int(sqrt(k-x**2)) + 1 ):
            m=k-x**2 - y**2 -x*y
            if m<=0:
                break
            for z in range(1,int(sqrt(m))+1):
                if z*(z+x+y)==m:
                    ans+=1
    print(ans)


### FIXED CODE ###

n=int(input())

ans=[0]*(n+1)

for x in range(1,101):
    for y in range(1,101):
        for z in range(1,101):
            f= x**2 + y**2 + z**2 + x*y + y*z + z*x
            if f<=n:
                ans[f]+=1

for i in range(1,n+1):
    print(ans[i])
### BUGGY CODE ###





K=int(input())
ans=0
gcd=0

for n in range(1,K+1):
    for m in range(1,K+1):
        for l in range(1,K+1):
            for A in range(1,K+1):
                if n%A==0:
                    if m%A==0:
                        if l%A==0:
                            gcd=A
            ans+=gcd
            
print(ans)


### FIXED CODE ###


import math
K=int(input())
ans=0
A=0

for n in range(1,K+1):
    for m in range(1,K+1):
        x=math.gcd(n,m)
        for l in range(1,K+1):
            A=math.gcd(x,l)    
            ans+=A
            
print(ans)
### BUGGY CODE ###

# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import bisect

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

def LI(): return list(map(int, sys.stdin.readline().split()))

N = int(input())
A = LI()

count_list = [0 for i in range(61)]
def counts(count_list, a):
    for i in range(61):
        count_list[i] += a % 2
        a = a // 2
    return count_list

A.reverse()
ans = 0
for i in range(N-1):
    count_list = counts(count_list, A[i])
    # print(count_list)
    hikaku = counts([0 for i in range(61)], A[i + 1])
    # print(i)
    for j in range(61):
        if hikaku[j] == 1:
            ans += (i+1 - count_list[j]) * 2 ** j % mod
        else:
            ans += count_list[j] * 2 ** j % mod
        ans = ans % mod
print(ans)


### FIXED CODE ###

import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import bisect

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

def LI(): return list(map(int, sys.stdin.readline().split()))

N = int(input())
A = LI()

count_list = [0 for i in range(61)]
def counts(count_list, a):
    for i in range(61):
        if a <= 0:
            break
        count_list[i] += a % 2
        a = a // 2
    return count_list

A.reverse()
ans = 0
ans_list = [0 for i in range(61)]
for i in range(N-1):
    count_list = counts(count_list, A[i])
    hikaku = counts([0 for i in range(61)], A[i + 1])
    for j in range(61):
        if hikaku[j] == 1:
            ans_list[j] += i+1 - count_list[j]
        else:
            ans_list[j] += count_list[j]

for i in range(61):
    ans += ans_list[i] * (2 ** i % mod)
    ans = ans % mod
print(ans)
### BUGGY CODE ###

import numpy as np
N=int(input())
A=np.array(list(map(int,input().split())))

D=np.array([[0]*N for i in range(N)])
for i in range(N):
  for j in range(N):
    if j==i or j==(i+1)%N:
      D[i][j]=1

X=2*np.dot(np.linalg.inv(D),A)
print(" ".join(map(lambda x:str(int(x)),X)))

### FIXED CODE ###

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

X=[]
S=sum(A)
x1=S
for i in range(N//2):
  x1-=2*A[2*i+1]
  
X.append(x1)

for i in range(1,N):
  X.append(2*A[i-1]-X[i-1])
print(" ".join(map(str,X)))
### BUGGY CODE ###

from collections import deque

def isPa(w,k,p):
    tr = 0
    c = 0
    d = deque(w)
    while(d):
        tmp = d.popleft()
        if(tmp > p):
            return False
        
        if( tr + tmp > p):
            tr = tmp
            c += 1
        else:
            tr += tmp
        if c+1>k:
            return False
    return True

def MaxInP(w,k,p):
    maxinp = 0
    tmp = 0
    d = deque(w)
    while(d):
        tmp += d.popleft();
        if(tmp > p):
            if(tmp > maxinp):
                maxinp = tmp
            tmp = 0
    return maxinp

n,k = [int(x) for x in input().split()]
w = deque()
for i in range(n):
    w.append(int(input()))
    
mean = int(sum(w)/k)
maxinp = MaxInP(w,k,mean)

if k == 1:
    print(mean)
else:
    minP = mean
    maxP = maxinp
    while(True):
        m = int ((minP + maxP)/2)
        if ( isPa(w,k,m) ):
            maxP = m
        else:
            minP = m
        if (minP+1 == maxP):
            print(maxP)
            break

### FIXED CODE ###

from collections import deque

def isPa(w,k,p):
    tr = 0
    c = 0
    d = deque(w)
    while(d):
        tmp = d.popleft()
        if(tmp > p):
            return False
        
        if( tr + tmp > p):
            tr = tmp
            c += 1
        else:
            tr += tmp
        if c+1>k:
            return False
    return True

def MaxInP(w,k,p):
    maxinp = 0
    tmp = 0
    d = deque(w)
    while(d):
        tmp += d.popleft();
        if(tmp > p):
            if(tmp > maxinp):
                maxinp = tmp
            tmp = 0
    return maxinp

n,k = [int(x) for x in input().split()]
w = deque()
for i in range(n):
    w.append(int(input()))
    
mean = int(sum(w)/k)
maxinp = MaxInP(w,k,mean)

if k == 1:
    print(mean)
else:
    minP = mean
    maxP = maxinp
    while(True):
        m = int ((minP + maxP)/2)
        if ( isPa(w,k,m) ):
            maxP = m
        else:
            minP = m
        if (minP+1 == maxP or minP == maxP):
            print(maxP)
            break
### BUGGY CODE ###

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

answer = 1
if 0 in A:
    print(0)
else:
    for i in A:
        answer *= i
    if answer > 10**18:
        print(-1)
    else:
        print(answer)

### FIXED CODE ###

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

answer = 1
if 0 in A:
  print(0)
else:
  for i in A:
    answer *= i
    if answer > 10**18:
      answer = -1
      break
  print(answer)
### BUGGY CODE ###

def minus(a):
  return a-1

a = input().split(" ")
mem = [int(a[1])] * int(a[0])
for i in range(int(a[2])):
  mem[int(input())-1] += 1
  mem = list(map(minus, mem))
for i in mem:
  if i < 1:
    print("No")
  else:
    print("Yes")

### FIXED CODE ###

a = input().split(" ")
mem = [0] * int(a[0])
for i in range(int(a[2])):
  mem[int(input())-1] += 1
for i in range(int(a[0])):
  if int(a[1])-int(a[2])+mem[i] < 1:
    print("No")
  else:
    print("Yes")
### BUGGY CODE ###

from collections import defaultdict
import sys
input = sys.stdin.readline
N = int(input())

tree_dict = defaultdict(list)
for i in range(N-1):
    u, v, w = list(map(int, input().split()))
    tree_dict[u].append((v, w))
    tree_dict[v].append((u, w))
# print(tree_dict)


# 探索
for key, value in tree_dict.items():
    if len(value) == 1:
        break
# print(key)
paint_dict = dict()

q = [key]
paint_dict[key] = 0

idx = 0
while len(q) < N:
    k = q[idx]
    #print("k", k, paint_dict[k])
    for to, w in tree_dict[k]:
        if to not in q[:idx]:
            if (w + paint_dict[k]) % 2 == 0:
                paint_dict[to] = 0
            else:
                paint_dict[to] = 1
            #print(paint_dict[to], to, w)
            q.append(to)
    idx += 1
for i in range(N):
    print(paint_dict[i+1])


### FIXED CODE ###

from collections import defaultdict
import sys
input = sys.stdin.readline
N = int(input())

tree_dict = defaultdict(list)
for i in range(N-1):
    u, v, w = list(map(int, input().split()))
    tree_dict[u].append((v, w))
    tree_dict[v].append((u, w))


# 任意の1点を選んで周辺を判定していく
FROM, TO = 0, 1
q = [(TO, FROM)]

paint_dict = defaultdict(int)
# 明示的な代入
paint_dict[TO] = 0

idx = 0
while idx < N:
    # 現在のノード(now)から隣接ノード(to)の白黒を定め，そのノードを探索のqに回す
    now_node, prev_node = q[idx]
    for to_node, w in tree_dict[now_node]:
        if to_node != prev_node:
            if (w + paint_dict[now_node]) % 2 == 0:
                paint_dict[to_node] = 0
            else:
                paint_dict[to_node] = 1
            q.append((to_node, now_node))
    idx += 1
for i in range(N):
    print(paint_dict[i+1])
### BUGGY CODE ###

n,m = map(int,input().split())
a = [list(map(int,input().split())) for i in range(m)]
for i in range(m):
    b = []
    for j in range(m):
        if a[i][0] == a[j][0]:
            b.append(a[j])
    b.sort(key =lambda x: x[1])
    x = str(b.index(a[i])+1)
    p = str(a[i][0])
    while len(x) < 6:
        x = "0"+x
    while len(p) < 6:
        p = "0"+p
    print(p+x)

### FIXED CODE ###

N, M = map(int, input().split())
pairs = [list(map(int,input().split())) for i in range(M)]

p_count = [1] * (N + 1)
for r in sorted(pairs, key=lambda x: x[1]):
    r.append("{:06}{:06}".format(r[0], p_count[r[0]]))
    p_count[r[0]] += 1

print("\n".join((r[2] for r in pairs)))
### BUGGY CODE ###

def main():
    N = int(input())
    from itertools import accumulate
    S = [i for i in accumulate(range(1, N+1))]

    def is_ok(mid):
        if N <= S[mid]:
            return True
        else:
            return False

    def binary_search_meguru():
        left = -1
        right = N
        while right - left > 1:
            mid = left + ((right - left) // 2)
            if is_ok(mid):
                right = mid
            else:
                left = mid
        return right

    ans = binary_search_meguru() + 1
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.buffer.readline
    N = int(input())
    from itertools import accumulate
    S = [i for i in accumulate(range(1, min(N+1, 100000)))]

    def is_ok(mid):
        if N <= S[mid]:
            return True
        else:
            return False

    def binary_search_meguru():
        left = -1
        right = len(S)
        while right - left > 1:
            mid = left + ((right - left) // 2)
            if is_ok(mid):
                right = mid
            else:
                left = mid
        return right

    ans = binary_search_meguru() + 1
    print(ans)


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

import math
import collections
def main():

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

    d = dict()
    def prime_factor(n):
        if n % 2 == 0: d[2] = d.get(2, 0) + 1
        while n % 2 == 0:
            n //= 2

        for i in range(3, int(math.sqrt(n))+1, 2):
            if n % i == 0:
                d[i] = d.get(i, 0) + 1
            while n % i == 0:
                n //= i
        if n > 1:
            d[n] = d.get(n, 0) + 1
        return

    ispair = True
    isset = True

    d = dict()
    for v in A: prime_factor(v)
    # print(d)

    if any(d[p] > 1 for p in d):
        ispair = False
    if any(d[p] == N for p in d):
        isset = False

    if ispair:
        return "pairwise coprime"
    if isset:
        return "setwise coprime"

    return "not coprime"

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

### FIXED CODE ###

import math
import collections
def main():

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

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

    ispair = True
    isset = True

    d = dict()
    for v in A:
        for u in set(prime_factorize(v)):
            d[u] = d.get(u, 0) + 1
    # print(d)

    if any(d[p] > 1 for p in d):
        ispair = False
    if any(d[p] == N for p in d):
        isset = False

    if ispair:
        return "pairwise coprime"
    if isset:
        return "setwise coprime"

    return "not coprime"

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

n=int(input())
ans = 0
for i in range(1, n+1):
    ans += int((int(n/i) * (int(n/i)+1))/2)*i;
print(ans)

### FIXED CODE ###

n=int(input())
ans = 0
for i in range(1, n+1):
    ans += (n//i) * ((n//i)+1)//2*i;
print(ans)
### BUGGY CODE ###

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

count = 0
for i in range(A,B+1):
	if i%C == 0:
		count += 1
	if i%D == 0:
		count += 1
	if i%C == 0 and i%D == 0:
		count -= 1

print(B-A+1-count)

### FIXED CODE ###

import fractions
A,B,C,D = map(int,input().split())

lcm = (C*D) // fractions.gcd(C,D)
Bnondiv = B - (B//C + B//D - B//lcm)
Anondiv = (A-1) - ((A-1)//C + (A-1)//D - (A-1)//lcm)
print(int(Bnondiv-Anondiv))
### BUGGY CODE ###

n = int(input())
A = list(map(int,input().split()))
ans = 0
for i in range(min(A),max(A)+1):
  cnt = A.count(i)
  if i-1 in A:
    cnt += A.count(i-1)
  if i+1 in A:
    cnt += A.count(i+1)
  ans = max(ans,cnt) 
print(ans)
  

### FIXED CODE ###

n = int(input())
cnt = [0] * 100002
a = list(map(int, input().split()))
for v in a:
    cnt[v] += 1
    cnt[v+1] += 1
    cnt[v+2] += 1
    
print(max(cnt))
### BUGGY CODE ###

def comb(n,k,p):
	from math import factorial
	if n<0 or k<0 or n<k: return 0
	if n==0 or k==0: return 1
	a,b,c = factorial(n)%p,factorial(k)%p,factorial(n-k)%p
	return (a*power_func(b,p-2,p)*power_func(c,p-2,p))%p
def power_func(a,b,p):
	if b==0: return 1
	elif b%2==0:
		d = power_func(a,b//2,p)
		return d**2 %p
	elif b%2==1: return (a*power_func(a,b-1,p))%p
from collections import Counter
n = int(input())
a = [int(i) for i in input().split()]
twice = Counter(a).most_common(1)[0][0]
x,y = (i for i,j in enumerate(a) if j == twice)
num,y = 1,n-y
for i in range(1,x+y+2):
	ans = comb(n+1,i,10**9+7)
	for j in range(max(0,i-y-1),min(i,x+1)):
		ans -= comb(x,j,10**9+7)*comb(y,i-j-1,10**9+7)
	print(ans)
for i in range(x+y+2,n+2): print(comb(n+1,i,10**9+7))

### FIXED CODE ###

def comb(n,k):
	if n<k or n==0: return 0
	elif k==0: return 1
	else: return f[n]*p[k]*p[n-k]%(10**9+7)
from collections import Counter
n = int(input())
print(n)
a = [int(i) for i in input().split()]
twice = Counter(a).most_common(1)[0][0]
x,y = (i for i,j in enumerate(a) if j == twice)
num,y,f,p = 1,n-y,[1],[1]
for i in range(1,n+2):
	f.append(f[-1]*i%(10**9+7))
	p.append(pow(f[-1],10**9+5,10**9+7))
for i in range(2,x+y+2): print((comb(n+1,i)-comb(x+y,i-1))%(10**9+7))
for i in range(x+y+2,n+2): print(comb(n+1,i))