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

import numpy as np
k=int(input())
 
from math import gcd
s6=0
for i in range(2,k-1):
    for j in range(i+1,k):
        for jj in range(j+1,k+1):
            s6+=np.gcd(np.gcd(i,j),jj)
 
s3=0
for i in range(2,k):
    for j in range(i+1,k+1):
        s3+=np.gcd(i,j)
 
s1=int((k+1)*k/2)
 
 
print(s1+s3*6+s6*6+(k-1)*6+(k-2)*(k-1)*3)

### FIXED CODE ###


k=int(input())
 
from math import gcd
s6=0
for i in range(2,k-1):
    for j in range(i+1,k):
        for jj in range(j+1,k+1):
            s6+=gcd(gcd(i,j),jj)
 
s3=0
for i in range(2,k):
    for j in range(i+1,k+1):
        s3+=gcd(i,j)
 
s1=int((k+1)*k/2)
 
 
print(s1+s3*6+s6*6+(k-1)*6+(k-2)*(k-1)*3)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
b=set(a)
ans=0
for i in b:
    if a.count(i)-i>=0:
        ans+=a.count(i)-i
    else:
        ans+=a.count(i)
print(ans)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
count = {}
ans = 0
for i in a:
    if i not in count:
        count[i] = 1
    else:
        count[i] += 1
for i,c in count.items():
    if i > c:
        ans += c
    elif i < c:
        ans += c - i
print(ans)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(1000000)

import fractions
from functools import reduce

N=int(input())
A=[int(i) for i in input().split()]

def mygcd(a,b):
    if a==0:
        return b
    elif b==0:
        return a
    else:
        return fractions.gcd(a,b)


def L(n):
    if n==-1:
        return 0
    else:
        return mygcd(L(n-1),A[n])

def R(n):
    if n==N:
        return 0
    else:
        return mygcd(R(n+1),A[n])

ans=1
for i in range(N):
    c=mygcd(L(i-1),R(i+1))
    ans=max(ans,c)

print(ans)

### FIXED CODE ###

import sys

sys.setrecursionlimit(1000000)

import fractions
from functools import reduce

N=int(input())
A=[int(i) for i in input().split()]

def mygcd(a,b):
    if a==0:
        return b
    elif b==0:
        return a
    else:
        return fractions.gcd(a,b)

L=[0]*N
for i in range(1,N):
    L[i]=mygcd(L[i-1],A[i-1])

R=[0]*N
for i in range(N-2,-1,-1):
    R[i]=mygcd(R[i+1],A[i+1])

ans=1
for i in range(N):
    c=mygcd(L[i],R[i])
    ans=max(ans,c)

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

from collections import Counter
S = str(input())
N = len(S)
 
smod = [int(S[i:])%2019 for i in range(N)]
cmod = Counter(smod)
 
ans = 0
for x,y in cmod.items():
    if x == 0:
        y += 1
        ans += y*(y-1)/2
    else:
        ans += y*(y-1)/2
print(int(ans))

### FIXED CODE ###

from collections import Counter
S = str(input())
N = len(S)

#smod = [int(S[i:])%2019 for i in range(N)]
smod = [0]
tmod = 0
keta = 1
for i in range(N):
    temp = tmod + int(S[(N-1)-i])*keta
    #print(temp)
    tmod = temp%2019
    smod.append(tmod)
    keta = keta*10%2019


cmod = Counter(smod)
#print(cmod)

ans = 0
for i in cmod.values():
    ans += i*(i-1)/2
print(int(ans))
### BUGGY CODE ###

def main():
    N = int(input())
    A = input()
    Q = int(input())

    answer = sum(list(map(int, A.split())))
    A = A.replace(" ", "")

    for i in range(Q):
        B, C = input().split()
        numB = A.count(B)

        answer = answer + (int(C) - int(B)) * numB
        print(answer)

        A = A.replace(B, C)

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys

def main():
    N = int(input())
    A = list(map(int, input().split()))
    Q = int(input())

    answer = sum(A)
    setA = set(A)
    numNumberList = [0] * 100001

    for Ai in A:
        numNumberList[Ai] = numNumberList[Ai] + 1    

    for i in range(Q):
        B, C = list(map(int, sys.stdin.readline().split()))
        answer = answer + (int(C) - int(B)) * numNumberList[B]

        numNumberList[C] = numNumberList[C] + numNumberList[B]
        numNumberList[B] = 0

        print(answer)

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

import os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def solve(bi, ei, bs):
    mid = (bi+ei)//2
    print(mid, flush=True)
    s = input()
    if s=='Vacant':
        exit(0)
    elif (s==bs)^((mid-bi)%2):
        solve(mid, ei, s)
    else:
        solve(bi, mid, bs)

n = int(input())
print(0, flush=True)
s = input()
if s=='Vacant':
    exit(0)
solve(0, n, s)

### FIXED CODE ###

def solve(bi, ei, bs):
    mid = (bi+ei)//2
    print(mid, flush=True)
    s = input()
    if s=='Vacant':
        exit(0)
    elif (s==bs)^((mid-bi)%2):
        solve(mid, ei, s)
    else:
        solve(bi, mid, bs)

n = int(input())
print(0, flush=True)
s = input()
if s=='Vacant':
    exit(0)
solve(0, n, s)
### BUGGY CODE ###

N = int(input())
S = input()
s = set()
res = 0
for i in range(N):
  for j in range(i, N):
    if j - i + 1 > N // 2:
      break
    p = S[i: j + 1]
    if p in s:
      res = max(res, len(p))
    else:
      s.add(p)
print(res)

### FIXED CODE ###

N = int(input())
S = list(input())
#LCSRe i番目とj番目でそれぞれ終わるような共通文字列の長さ
#i < j であるi文字目とj文字目が等しいならLCSRe[i + 1][j + 1] = LCSRe[i][j] + 1
#res_lengthよりLCSReの更新した値が大なら、その時のindexをiへ、res_lengthも更新

def longestRepeatedSubstring(s): 
  n = len(s) 
  LCSRe = [[0 for _ in range(n + 1)] for _ in range(n + 1)] 
  res = "" 
  res_length = 0
  index = 0
  for i in range(1, n + 1): 
    for j in range(i + 1, n + 1): 
      if s[i - 1] == s[j - 1] and LCSRe[i - 1][j - 1] < j - i: 
        LCSRe[i][j] = LCSRe[i - 1][j - 1] + 1
        if LCSRe[i][j] > res_length: 
          res_length = LCSRe[i][j] 
          index = max(i, index) 
      else: 
        LCSRe[i][j] = 0
  #print(LCSRe)
  if res_length > 0: 
    for i in range(index - res_length + 1, index + 1): 
      res = res + s[i - 1] 
  return res_length
print(longestRepeatedSubstring(S))
### BUGGY CODE ###

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

if K > 0:
    count = 0

    for a in range(1, N+1):
        for b in range(K+1, a):
            if a%b >= K:
                count = count + 1
    
    count = count + int((N+1-K)*(N-K)/2)

    print(count)
else:
    print(N*N)

### FIXED CODE ###

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

if K > 0:
    count = 0

    for b in range(K+1, N+1):
        p = N // b
        r = N % b
        count = count + p*(b-K)
        if r >= K:
            count = count + r-K+1
    
    print(count)
else:
    print(N*N)
### BUGGY CODE ###

N=int(input())
josi = list(map(int,input().split()))
n=1
m=0
count=0
while n<=N:
  while m<N-1:
    if josi[m]==n:
      count = count+1
    m=m+1
  print(count)
  n=n+1
  m=0
  count=0

      

### FIXED CODE ###

N=int(input())
josi = list(map(int,input().split()))
count=[0]*N
n=0
while n<N-1:
  count[josi[n]-1] =count[josi[n]-1]+1
  n=n+1
n=0
while n<N:
  print(count[n])
  n=n+1
### BUGGY CODE ###


import math

K = int(input())

ans = 0
for a in range(1,K+1):
  for b in range(1,K+1):
    for c in range(1,K+1):
      ans += math.gcd(a,math.gcd(b,c))

print(ans)

### FIXED CODE ###

from math import gcd

k = int(input())
ans = 0
for a in range(1,k+1):
  for b in range(1,k+1):
    x = gcd(a,b)
    for c in range(1,k+1):
        ans += gcd(x,c)
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

r, c, k = map(int, input().split())

items = [[0] * (c + 1) for _ in range(r + 1)]
for _ in range(k):
    i, j, v = map(int, input().split())
    items[i][j] = v

# dp[i][j][m] = (i行j列時点で、i行でm個のitemを取得している時の価値の最大値)
dp = [[[0] * 4 for _ in range(c + 1)] for _ in range(r + 1)]

for i in range(1, r + 1):
    for j in range(1, c + 1):
        for m in range(4):
            dp[i][j][m] = max(dp[i][j][m], max(dp[i - 1][j]), dp[i][j - 1][m])
        for m in reversed(range(3)):
            dp[i][j][m + 1] = max(dp[i][j][m + 1], dp[i][j][m] + items[i][j])

print(dp[r][c][3])


### FIXED CODE ###

import sys


def main():
    input = sys.stdin.readline

    r, c, k = map(int, input().split())

    items = [[0] * (c + 1) for _ in range(r + 1)]
    for _ in range(k):
        i, j, v = map(int, input().split())
        items[i][j] = v

    # dp[m][i][j] = (i行j列時点で、i行でm個のitemを取得している時の価値の最大値)
    dp = [[[0] * (c + 1) for _ in range(r + 1)] for _ in range(4)]

    for i in range(1, r + 1):
        for j in range(1, c + 1):
            for m in range(4):
                dp[m][i][j] = max(dp[3][i - 1][j], dp[m][i][j - 1])
            if items[i][j] > 0:
                for m in [2, 1, 0]:
                    dp[m + 1][i][j] = max(dp[m + 1][i][j],
                                          dp[m][i][j] + items[i][j])

    print(dp[3][r][c])


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

import sys
input = sys.stdin.readline

N,M = list(map(int,input().split()))
A = list(map(int,input().split()))
tmp = sorted([list(map(int,input().split())) for i in range(M)],key = lambda x:-x[1])

cnt = 0
t = []
for a,b in tmp:
    t=t+[b]*a
    cnt+= a
    if cnt >=N:
        break

A = A + t
A.sort(reverse = 1)
print(sum(A[:N]))



### FIXED CODE ###

import sys
input = sys.stdin.readline

def sol():
    N,M = list(map(int,input().split()))
    A = list(map(int,input().split()))
    tmp = sorted([list(map(int,input().split())) for _ in range(M)],key = lambda x:-x[1])

    t = []
    for a,b in tmp:
        t+=[b]*a
        
        if len(t) >=N:
            break

    A += t
    A.sort(reverse = 1)
    print(sum(A[:N]))

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

MOD = 1000000007

s = input()
n = len(s) + 1

dp = [[0 for x in range(13)] for c in range(n)]
dp[0][0] = 1

for i, x in enumerate(s):
    if x == '?':
        x = -1
    else:
        x = int(x)

    for j in range(10):
        if (x == -1) or (x == j):
            for ki in range(13):
                dp[i+1][(ki * 10 + j) % 13] += dp[i][ki]
    dp[i+1] = [k % MOD for k in dp[i+1]]

print(dp[len(s)][5])

### FIXED CODE ###

MOD = 1000000007

s = [-1 if x == '?' else int(x) for x in input()]
n = len(s) + 1

dp = [0] * 13
dp[0] = 1

r = [[(j-i)*4%13 for i in range(10)]for j in range(13)]

for i, x in enumerate(s):
    next_dp = [0] * 13
    if x == -1:
        next_dp = [sum(dp[i] for i in j) for j in r]
    else:
        next_dp = [dp[j[x]] for j in r]
    dp = [k % MOD for k in next_dp]

print(dp[5])
### BUGGY CODE ###

import sys
from collections import defaultdict
d=defaultdict(int)
N=int(input())
L=[]
input=sys.stdin.readline
for _ in range(N):
 s=input()
 d[s]+=1
for k, v in d.items():
 if v == max(d.values()):
  L.append(k)
L.sort()
for i in L:
 print(i)

### FIXED CODE ###

n=int(input())
arr=[input() for _ in range(n)]
dic={}
for i in range(n): #各単語の出現回数を数える
 if arr[i] not in dic:
   dic[arr[i]]=1
 else:
   dic[arr[i]]+=1
largest=max(dic.values()) #最大の出現回数を求める
ans=[]
for keys in dic.keys():
 if dic[keys]==largest: #出現回数が最も多い単語を集計する
   ans.append(keys)
ans=sorted(ans) #単語を辞書順に並べ替えて出力する
for words in ans:
 print(words)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
ans = []
for i in range(n):
  ans.append(a.index(i+1)+1)
print(*ans)


### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
ans = []
A = []
for i in range(n):
  ans.append((a[i],i+1))
ans.sort()
for i in range(n):
  A.append(ans[i][1])
print(*A)
### BUGGY CODE ###

import random
from collections import defaultdict
from itertools import accumulate
n = int(input())
s = input()
mod = (1<<61)-1
base = 1000+random.randint(0,100)
power = [1]
for i in range(1,n):
	power.append((power[-1]*base)%mod)
hvalue = [0]
for i in range(n):
	hvalue.append((hvalue[-1]+(ord(s[i])*power[i]))%mod)
def rollinghash(l,r):
	return ((hvalue[r]-hvalue[l])*power[n-r])%mod
ans = 0
for i in range(1,n//2+1):
	dc = defaultdict(int)
	for j in range(n-i+1):
		x = rollinghash(j,i+j)
		if dc[x]:
			rg = dc[x]
			if rg<=j:
				ans = max(ans,i)
				break
		else:
			dc[x] = i+j
print(ans)

### FIXED CODE ###

import random
from collections import defaultdict
from itertools import accumulate
import sys
input = sys.stdin.readline
n = int(input())
s = input().rstrip()
mod = (1<<61)-1
base = 1000+random.randint(0,100)
power = [1]
for i in range(1,n):
  power.append((power[-1]*base)%mod)
hvalue = [0]
for i in range(n):
  hvalue.append((hvalue[-1]+(ord(s[i])*power[i]))%mod)
def rollinghash(l,r):
  return ((hvalue[r]-hvalue[l])*power[n-r])%mod
def pun(i):
  dc = defaultdict(int)
  if i>n//2:
    return False
  for j in range(n-i+1):
    x = rollinghash(j,i+j)
    if dc[x]:
      rg =dc[x]
      if rg<=j:
        return True
    else:
      dc[x] = i+j
  return False
l=0
r=n//2+1
while l+1<r:
  mi=(l+r)//2
  if pun(mi):
    l=mi
  else:
    r=mi
print(l)
### BUGGY CODE ###

n = int(input())
l = list(map(int,input().split()))
l.sort() # 昇順にソート

count = 0
for i in range(0,n-2):
    a = l[i]
    for j in range(i+1, n-1):
        ab = a+l[j]
        # バイナリサーチでl[k] < a+b  となる最小のkを探す
        # j+1, ..., k で三角形ができる k-j 個
        left = j+1
        right = n
        while (left < right):
            middle = (left + right) // 2
            #print('left: {} middle:{} right: {}'.format(left, middle, right))
            c = l[middle]
            if (c < ab):
                left = middle+1 #  l[left-1]は三角形が作れる
            elif( ab <= c):
                right = middle  #  l[right] は三角形が作れない
        # left-1 が argmin_k(a+b>l[k])
        count += left-1 - j
print(count)


### FIXED CODE ###

from bisect import bisect_right

n = int(input())
l = list(map(int,input().split()))
l.sort() # 昇順にソート

count = 0
for i in range(0,n-2):
    a = l[i]
    for j in range(i+1, n-1):
        ab = a+l[j]
        # bisect_left(a, x): x を a に挿入できる点を返す
        # cの最大値は a+b-1
        k = bisect_right(l, ab-1, j+1, n)
        count += k-(j+1)
print(count)
### BUGGY CODE ###

n, m = map(int, input().split())
MOD = m
list_size = n+2

f_list = [1] * list_size
f_r_list = [1] * list_size

for i in range(list_size - 1):
	f_list[i + 1] = int((f_list[i] * (i + 1)) % MOD)

f_r_list = [pow(x, MOD-2, MOD) for x in f_list]

def comb(N, r):
	if N < r or r < 0:
		return 0
	else:
		return (((f_list[N] * f_r_list[N - r]) % MOD) * f_r_list[r]) % MOD 

st = [[0 for _ in range(n+1)] for _ in range(n+1)]
st[0][0] = 1
for i in range(1, n+1):
	st[i][0] = 1
	for j in range(1, i+1):
		st[i][j] = (st[i-1][j-1] + (j+1) * st[i-1][j]) % MOD

ans = 0
for i in range(n+1):
	res = (comb(n, i) * pow(2, pow(2, n-i, MOD-1), MOD)) % MOD
	tmp = 0
	for j in range(i+1):
		tmp += st[i][j] * pow(2, (n-i) * j, MOD)
		tmp %= MOD
	res *= tmp
	res %= MOD

	if i%2 == 0:
		ans += res
	else:
		ans -= res
	ans %= MOD

print(ans)

### FIXED CODE ###

n, m = map(int, input().split())
MOD = m
list_size = n+2

f_list = [1] * list_size
f_r_list = [1] * list_size

for i in range(list_size - 1):
	f_list[i + 1] = int((f_list[i] * (i + 1)) % MOD)

f_r_list = [pow(x, MOD-2, MOD) for x in f_list]

def comb(N, r):
	if N < r or r < 0:
		return 0
	else:
		return (((f_list[N] * f_r_list[N - r]) % MOD) * f_r_list[r]) % MOD 

st = [[0 for _ in range(n+1)] for _ in range(n+1)]
st[0][0] = 1
for i in range(1, n+1):
	st[i][0] = 1
	for j in range(1, i+1):
		st[i][j] = (st[i-1][j-1] + (j+1) * st[i-1][j]) % MOD

ans = 0
for i in range(n+1):
	res = (comb(n, i) * pow(2, pow(2, n-i, MOD-1), MOD)) % MOD
	tmp = 0
	for j in range(i+1):
		tmp += st[i][j] * pow(2, (n-i) * j, MOD)
		tmp %= MOD
	res *= tmp
	res %= MOD

	if i%2 == 0:
		ans += res
	else:
		ans -= res
	ans %= MOD

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

import collections

n, m = map(int, input().split())
es = [collections.deque() for _ in range(n)]
for _ in range(m):
    l, r, d = map(int, input().split())
    l -= 1
    r -= 1
    es[l].append((l, r, d))
    es[r].append((r, l, -d))

visited = [False for _ in range(n)]
for i in range(n):
    if not visited[i]:
        visited[i] = True
        if len(es[i]) == 0:
            continue
        distances = [float('inf') for _ in range(n)]
        distances[i] = 0
        q = collections.deque()
        for e in es[i]:
            q.append(e)
        while q:
            j, k, d = q.popleft()
            if visited[k] and distances[k] != distances[j] + d:
                print('No')
                exit()
            distances[k] = distances[j] + d
            visited[k] = True
            while es[k]:
                ee = es[k].popleft()
                if len(es[ee[1]]) > 0:
                    q.append(ee)
print('Yes')

### FIXED CODE ###

import collections
import sys

input = sys.stdin.readline

n, m = map(int, input().split())
es = [collections.deque() for _ in range(n)]
for _ in range(m):
    l, r, d = map(int, input().split())
    l -= 1
    r -= 1
    es[l].append((l, r, d))
    es[r].append((r, l, -d))

visited = [False] * n
for i in range(n):
    if not visited[i]:
        visited[i] = True
        if len(es[i]) == 0:
            continue
        distances = [float('inf')] * n
        distances[i] = 0
        q = collections.deque()
        for e in es[i]:
            q.append(e)
        while q:
            j, k, d = q.popleft()
            if visited[k] and distances[k] != distances[j] + d:
                print('No')
                exit()
            distances[k] = distances[j] + d
            visited[k] = True
            while es[k]:
                ee = es[k].popleft()
                if len(es[ee[1]]) > 0:
                    q.append(ee)
print('Yes')
### BUGGY CODE ###

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

for i in range(1,n+1):
    print(hw.count(i))



### FIXED CODE ###

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

o={}
for i in range(1,n+1):
  o[i]=0
  
for p in m:
  o[p]+=1

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

import numpy as np

n = int(input())

happiness = np.zeros(3)

for i in range(n):
    act = np.array(list(map(int, input().split())))
    happiness = np.maximum(act+np.roll(happiness, 1), act+np.roll(happiness, 2))

print(int(happiness.max()))

### FIXED CODE ###

import numpy as np

n = int(input())

happiness = [0]*3

for i in range(n):
    act = list(map(int, input().split()))
    tmp1 = [happiness[(i+1)%3]+act[i] for i in range(3)]
    tmp2 = [happiness[(i+2)%3]+act[i] for i in range(3)]
    happiness = [max(tmp1[i], tmp2[i]) for i in range(3)]

print(max(happiness))
### BUGGY CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
for i in range(m):
  b, c = map(int, input().split())
  change_number = len(list(filter(lambda x : x < c, a)))
  change_number = change_number if change_number <= b else b
  a = ([c] * change_number) + a[change_number:]
  a.sort()

print(sum(a))

### FIXED CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
cb_list = []
for i in range(m):
  b, c = map(int, input().split())
  cb_list.append((c, b))

cb_list.sort(key=lambda x: x[0], reverse=True)

elim_count = 0
for i in range(m):
  c,b = cb_list[i]
  a.extend([c] * b)
  if len(a) >= 2*n:
    break

a.sort(reverse=True)
print(sum(a[:n]))
### BUGGY CODE ###

import math

MOD = 10**9+7


def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0


def modinv(a):
    g, x, y = xgcd(a, MOD)
    return x % MOD


'''
fact = [1] * 200100
for i in range(1, 100100):
    fact[i] = fact[i-1] * i % MOD
'''


def comb(n, r):
    if n < r or r < 0:
        return 0
    else:
        return math.factorial(n) * modinv(math.factorial(n - r)) * modinv(math.factorial(r)) % MOD


n = int(input())
a = list(map(int, input().split()))
x = sum(a) - n*(n+1)//2

l = 0
while a[l] != x:
    l += 1
r = 0
while a[n - r] != x:
    r += 1
c = n + 1 - l - r - 2

for k in range(1, n + 2):
    ans = comb(n+1, k) - comb(l + r, k - 1)
    if ans < 0:
        ans += MOD
    print(ans)


### FIXED CODE ###

import math

MOD = 10**9+7


def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0


def modinv(a):
    g, x, y = xgcd(a, MOD)
    return x


fact = [1] * 100100
for i in range(1, 100100):
    fact[i] = fact[i-1] * i % MOD


def comb(n, r):
    if n < r or r < 0:
        return 0
    else:
        return fact[n] * modinv(fact[n - r]) * modinv(fact[r]) % MOD


n = int(input())
a = list(map(int, input().split()))
x = sum(a) - n*(n+1)//2

l = 0
while a[l] != x:
    l += 1
r = 0
while a[n - r] != x:
    r += 1
c = n + 1 - l - r - 2

for k in range(1, n + 2):
    ans = comb(n+1, k) - comb(l + r, k - 1)
    if ans < 0:
        ans += MOD
    print(ans)
### BUGGY CODE ###

s = input()
q = int(input())
cnt = 0
for i in range(q):
  query = input()
  if query == '1':
    cnt += 1
  else:
    t, f, c = query.split()
    if (f == '1' and cnt % 2 == 0) or (f == '2' and cnt % 2 == 1):
      s = c + s
    else:
      s = s + c
if cnt % 2 == 0:
  print(s)
else:
  print(s[::-1])

### FIXED CODE ###

from collections import deque
s = deque(input())
q = int(input())
cnt = 0
for i in range(q):
  query = input()
  if query == '1':
    cnt += 1
  else:
    t, f, c = query.split()
    if (f == '1' and cnt % 2 == 0) or (f == '2' and cnt % 2 == 1):
      s.appendleft(c)
    else:
      s.append(c)
if cnt % 2 == 0:
  print(''.join(s))
else:
  s.reverse()
  print(''.join(s))
### BUGGY CODE ###

n, k = map(int, input().split())
s = input()
s2 = [["1", 0, 0]]
zero = 0
one_count = 1
for i, c in enumerate(s):
    if s2[-1][0] == c:
        s2[-1][2] += 1
    else:
        s2.append([c, i, 1])
        zero += (1 - int(c))
        if c == "1":
            one_count += 1
if zero <= k:
    print(n)
    exit()
if s2[-1][0] == "0":
    s2.append(["1", len(s)-1, 0])
    one_count += 1
ans = -1
for i in range(one_count - k):
    a = 0
    for e in s2[i*2:(i+k)*2+1]:
        a += e[2]
    if ans < a:
        ans = a
print(ans)

### FIXED CODE ###

n, k = map(int, input().split())
s = input()
cur = "1"
sum_ = [0]
ans = -1
for i, c in enumerate(s):
    if cur != c:
        sum_.append(i)
        if c == "0":
            if len(sum_) >= 2 + k + k:
                ans = max(ans, sum_[-1] - sum_[-2-k-k])
        cur = c
sum_.append(len(s))
if s[-1] == "0":
    sum_.append(len(s))
if len(sum_) > 2 + k + k:
    ans = max(ans, sum_[-1] - sum_[-2-k-k])
else:
    ans = n
print(ans)
### BUGGY CODE ###

import sys
from operator import itemgetter
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7

def main():
    N, M = map(int, readline().split())
    A = list(map(int, readline().split()))
    A.sort()
    BC = []
    for _ in range(M):
        B, C = map(int, readline().split())
        BC.append((B,C))
    BC.sort(key=itemgetter(1))
    for i in range(M):
        b = BC[i][0]
        c = BC[i][1]
        for j in range(b):
            if A[j]<c:
                A[j]=c
        A.sort()
    print(sum(A))



if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import time
from operator import itemgetter
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7

def main():
    N, M = map(int, readline().split())
    A = list(map(int, readline().split()))
    BC = []
    for _ in range(M):
        B, C = map(int, readline().split())
        BC.append((B,C))
    BC.sort(key=itemgetter(1), reverse=True)
    BC.append((N,-1))
    change = []
    for b,c in BC:
        change += [c]*b
        if len(change) > N:
            break
    A += change
    A.sort()
    answer = sum(A[-N:])
    print(answer)




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

N = int(input())
K = int(input())

ans = 0
for i in range(1,N+1) :
    list_i = [i for i in str(i) if i != "0"]
    if len(list_i) == K :
        ans += 1

print(ans)


### FIXED CODE ###

N = input()
K = int(input())
dp = [[[0]*(2) for _ in range(K+1)] for _ in range(len(N)+1)]
dp[0][0][0] = 1

for i in range(len(N)) :
    for k in range(K+1) :
        for j in range(2) :
            n = int(N[i])
            for d in range(10) :
                nk = k
                nj = j
                if d != 0:
                    nk += 1
                if nk > K:
                    continue
                if j == 0:
                    if d > n:
                        continue
                    if d < n:
                        nj = 1
                dp[i+1][nk][nj] += dp[i][k][j]

ans = dp[len(N)][K][0] + dp[len(N)][K][1]

print(ans)