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

import sys
import numpy as np

N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))
Q = int(sys.stdin.readline())
replace_map = [list(map(int, sys.stdin.readline().split())) for _ in range(Q)]

nums = {}
for a in A:
    nums[a] = nums[a] + 1 if a in nums else 1

for search, replace in replace_map:
    if search in nums:
        nums[replace] = nums[replace] + nums[search] if replace in nums else nums[search]
        del nums[search]
    print(np.dot(list(nums.keys()), list(nums.values())))


### FIXED CODE ###

import sys
import numpy as np

_ = sys.stdin.readline()
A = list(map(int, sys.stdin.readline().split()))
Q = int(sys.stdin.readline())
replace_map = [list(map(int, sys.stdin.readline().split())) for _ in range(Q)]

nums = {}
for a in A:
    nums[a] = nums[a] + 1 if a in nums else 1

previous_sum = 0
for search, replace in replace_map:
    replaced_count = 0
    if search in nums:
        replaced_count = nums[search]
        nums[replace] = nums[replace] + replaced_count if replace in nums else replaced_count
        del nums[search]
    if previous_sum == 0:
        previous_sum = np.dot(list(nums.keys()), list(nums.values()))
    else:
        previous_sum += replaced_count * (replace - search)
    print(previous_sum)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

n, w = map(int, input().split())
item = [list(map(int, input().split())) for _ in range(n)]
dp = [[0] + [0]*w] + [[0] + [-float("inf")]*w for _ in range(n)]
wei, val = 0, 1

for i in range(n):
    for j in range(w+1):
        if item[i][wei] <= j:
            dp[i+1][j] = max(dp[i][j], dp[i][j-item[i][wei]] + item[i][val])
        else:
            dp[i+1][j] = dp[i][j]

print(dp[n][w])


### FIXED CODE ###

import sys
input = sys.stdin.readline

n, w = map(int, input().split())
item = [list(map(int, input().split())) for _ in range(n)]
dp = [[0] + [0]*w] + [[0] + [-float("inf")]*w for _ in range(n)]
wei, val = 0, 1

for i in range(n):
    for j in range(w+1):
        if item[i][wei] <= j:
            dp[i+1][j] = max(dp[i][j], dp[i][j-item[i][wei]] + item[i][val])
        else:
            dp[i+1][j] = dp[i][j]

print(dp[n][w])
### BUGGY CODE ###

import numpy as np

#入力部
H, W = [int(i) for i in input().split()]
#mapの入力
mymap = [] #mapの配列
for i in range(H):
    mymap.append(list(input()))
Lmap = list(list(-1 for a in range(W)) for b in range(H)) #列探索配列
Rmap = list(list(-1 for a in range(W)) for b in range(H)) #列探索配列（逆順）
Umap = list(list(-1 for a in range(W)) for b in range(H)) #行探索配列
Dmap = list(list(-1 for a in range(W)) for b in range(H)) #行探索配列（逆順）

#Lmap
for i in range(H):
  mycnt = 1
  for j in range(W):
    if mymap[i][j] == '#':
      Lmap[i][j] = 0
      mycnt = 1
    else: 
      Lmap[i][j] = mycnt
      mycnt += 1
      
#Rmap
for i in range(H):
  mycnt = 1
  for j in reversed(range(W)):
    if mymap[i][j] == '#':
      Rmap[i][j] = 0
      mycnt = 1
    else: 
      Rmap[i][j] = mycnt
      mycnt += 1

#Dmap & 最大値の探索
for i in range(W):
  mycnt = 1
  for j in reversed(range(H)):
    if mymap[j][i] == '#':
      Dmap[j][i] = 0
      mycnt = 1
    else: 
      Dmap[j][i] = mycnt
      mycnt += 1

#Umap
for i in range(W):
  mycnt = 1
  for j in range(H):
    if mymap[j][i] == '#':
      Umap[j][i] = 0
      mycnt = 1
    else: 
      Umap[j][i] = mycnt
      mycnt += 1
#なぜか最後だけnparray       
print(np.max(np.array(Lmap)+np.array(Rmap)+np.array(Umap)+np.array(Dmap)) -3)



### FIXED CODE ###

import numpy as np
 
H, W = map(int, input().split())
#mapの入力
mymap = [] 
for i in range(H):
    mymap.append(list(input()))

#探索可能性をブーリアン表記
mymap = (np.array(mymap) == ".")
  
L = np.zeros((H, W), dtype=int) #左側から探索した場合の配列
R = np.zeros((H, W), dtype=int) #右側から探索した場合の配列
U = np.zeros((H, W), dtype=int) #上側から探索した場合の配列
D = np.zeros((H, W), dtype=int) #下側から探索した場合の配列

#列ごとに左から
for j in range(W):
  if j == 0: #左端
    L[:, j] = mymap[:, j] #true = 1, false = 0
  else:
    L[:, j] = (L[:, j - 1] + 1) * mymap[:, j] #trueの場合は1つ左の列の値を加算しながら

#列ごとに右から
for j in range(W - 1, -1, -1): #(引数：開始数，終了数，加算数）
  if j >= W - 1: #右端
    R[:, j] = mymap[:, j]
  else:
    R[:, j] = (R[:, j + 1] + 1) * mymap[:, j] 

#行ごとに上から
for i in range(H):
  if i <= 0: #上端
    U[i, :] = mymap[i, :]
  else:
    U[i, :] = (U[i - 1, :] + 1) * mymap[i, :]

#行ごとに下から
for i in range(H - 1, -1, -1):
  if i >= H - 1: #下端
    D[i, :] = mymap[i, :]
  else:
    D[i, :] = (D[i + 1, :] + 1) * mymap[i, :]

#総和から重複分(=3)の差をとって，最大値を出力
print(np.max(L + R + U + D - 3))
### BUGGY CODE ###

from collections import deque

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

stack = deque()

stack.appendleft((0, 1000, 0))
max_money = 1000

while stack:
    target = stack.popleft()

    day = target[0]
    money = target[1]
    stock = target[2]

    if day + 1 <= N:
        stack.appendleft((day + 1, money + stock * A[day], 0))
        stack.appendleft(
            (day + 1, money - (money // A[day]) * A[day], money // A[day]))
    else:
        if max_money < money:
            max_money = money

print(max_money)


### FIXED CODE ###

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

money = 1000
stock = 0

for i in range(N-1):
    if A[i] <= A[i+1]:
        stock += money // A[i]
        money -= (money // A[i]) * A[i]
    else:
        money += A[i] * stock
        stock = 0

print(money + stock * A[N-1])
### BUGGY CODE ###

import math
from fractions import Fraction
import sys

from fractions import Fraction
import sys
sys.setrecursionlimit(15000)

def fibMul(fn1, fn2):
    a = fn1[0]
    b = fn1[1]
    c = fn2[0]
    d = fn2[1]
    return (a*c + 5*b*d, a*d + b*c)

def fibExp(fn, n):
    if (n == 0):
        return (Fraction(1), Fraction(1));
    if (n % 2 == 0):
        return fibExp(fibMul(fn, fn), n / 2);
    return fibMul(fn, fibExp(fn, n - 1));

def fibMin(fn1, fn2):
    a = fn1[0]
    b = fn1[1]
    c = fn2[0]
    d = fn2[1]
    return (a - c, b - d)

def fibMain(n):
    fibNum1 = (Fraction(1, 2), Fraction( 1, 2))
    fibNum2 = (Fraction(1, 2), Fraction(-1, 2))
    fibNum3 = fibMin(fibExp(fibNum1, n), fibExp(fibNum2, n)) 
    fibNum4 = (Fraction(0, 1), Fraction(1, 5))
    return fibMul(fibNum3, fibNum4)

def fib(n):
    return fibMain(n)[0].numerator



n, m =map(int, input().split())  #複数数値入力
a = [-1]
for i in range(m):
    ai = int(input())
    a.append(ai)
a.append(n+1)

count = 1
root5 = math.sqrt(5)
for i in range(m+1):
    x = a[i+1] - a[i] -1
    if x == 0:
        count = 0
        break
    else:
#         y = 1/root5 *(((1+root5)/2)**x - ((1-root5)/2)**x) 
        count *= fib(x)
print(int(count)%1000000007)

### FIXED CODE ###

import math
from fractions import Fraction
import sys


class multipliable_2x2matrix(object):
    def __init__(self, a, b, c, d):
        self.a = a;
        self.b = b;
        self.c = c;
        self.d = d;
    def mul(self, b):
        return multipliable_2x2matrix(
            self.a * b.a + self.b * b.c,
            self.a * b.b + self.b * b.d,
            self.c * b.a + self.d * b.c,
            self.c * b.b + self.d * b.d)
    
def fib(n):
    if n == 0: return 0
    m = multipliable_2x2matrix(1, 1, 1, 0)
    f = multipliable_2x2matrix(1, 0, 0, 1)
    n = n - 1
    while n > 0:
        if n & 1 == 1:
            f = f.mul(m)
        n = n >> 1
        m = m.mul(m)
    return f.a



n, m =map(int, input().split())  #複数数値入力
a = [-1]
for i in range(m):
    ai = int(input())
    a.append(ai)
a.append(n+1)

count = 1
root5 = math.sqrt(5)
for i in range(m+1):
    x = a[i+1] - a[i] -1
    if x == 0:
        count = 0
        break
    else:
#         y = 1/root5 *(((1+root5)/2)**x - ((1-root5)/2)**x) 
        count *= fib(x)
print(int(count)%1000000007)
### BUGGY CODE ###

# coding: utf-8
# Your code here!
N,K = map(int,input().split())
A = [int(input()) for _ in range(N)]
dp = [[0] * N for _ in range(N)]
dp2 = [0] * N
for i in range(N):
    for j in range(i,N):
        if abs(A[i]-A[j]) <= K:
            dp[i][j] = 1
for i in range(N):
    tmax = 1
    for j in range(i+1):
        if dp[j][i]==1:
            tmax = max(tmax,dp2[j]+1)
    dp2[i] = tmax  

print(max(dp2))



### FIXED CODE ###

# Input Part
N,K = map(int,input().split())
A = [int(input()) for _ in range(N)]

Amax = 3*10**5

# N: 処理する区間の長さ
N0 = 2**(Amax-1).bit_length()
INF = 0
data = [INF]*(2*N0)
# a_k の値を x に更新
def update(k, x):
    k += N0-1
    data[k] = x
    while k >= 0:
        k = (k - 1) // 2
        data[k] = max(data[2*k+1], data[2*k+2])
# 区間[l, r)の最小値
def query(l, r):
    L = l + N0; R = r + N0
    s = INF
    while L < R:
        if R & 1:
            R -= 1
            s = max(s, data[R-1])

        if L & 1:
            s = max(s, data[L-1])
            L += 1
        L >>= 1; R >>= 1
    return s

def main():
    for i in range(N):
        tmin = max(0,A[i]-K)
        tmax = min(Amax,A[i]+K)+1
        update(A[i],query(tmin,tmax)+1)
        #print(data)
    print(data[0])
main()
### BUGGY CODE ###

import sys
import itertools
input = sys.stdin.readline

N = int(input())
S = input()
vv = []
cc = [0] * 1000
for v in itertools.combinations(S[0:-1], 3):
	cc[int(v[0]+v[1]+v[2])]=1
print(sum(cc))

### FIXED CODE ###

import sys
import itertools
input = sys.stdin.readline

N = int(input())
S = input()
cc = [0]*1000
ans = [0]*1000
for j in range(len(S)-1):
	p = int(S[j])
	for i in range(1000):
		if(p==i%10 and cc[i]==2):
			cc[i]+=1
			ans[i]=1
		elif(p==(i//10)%10 and cc[i]==1):
			cc[i]+=1
		elif(p==i//100 and cc[i]==0):
			cc[i]+=1
print(sum(ans))
### BUGGY CODE ###

def luka(i):
    if i==0:
        return 2
    if i==1:
        return 1
    return luka(i-1)+luka(i-2)

N=int(input())
print(luka(N))

### FIXED CODE ###

N=int(input())
lst=[2,1]
for i in range(2,N+1):
    lst.append(lst[i-1]+lst[i-2])
print(lst[N])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**5)

n, m = [int(i) for i in input().split(" ")]

g = [[] for i in range(0, n + 1)]
v = [0] * (n + 1)
v_asn = [False] * (n + 1)
f = True

for i in range(0, m):
    l, r, d = [int(i) for i in input().split(" ")]
    g[l].append([r, d])
    g[r].append([l, -d])

def trav(i):
    global g
    global v
    global v_asn
    global f
    for a in g[i]:
        if not v_asn[a[0]]:
            v_asn[a[0]] = True
            v[a[0]] = v[i] + a[1]
            trav(a[0])
        else:
            if v[a[0]] != v[i] + a[1]:
                f = False
                return

for i in range(1, n + 1):
    if not v_asn[i]:
        v_asn[i] = True
        trav(i)
        if not f:
            break

if f:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

import queue

n, m = [int(i) for i in input().split(" ")]

g = [[] for i in range(0, n + 1)]
v = [0] * (n + 1)
v_asn = [False] * (n + 1)
f = True

for i in range(0, m):
    l, r, d = [int(i) for i in input().split(" ")]
    g[l].append([r, d])
    g[r].append([l, -d])

for i in range(1, n + 1):
    if not v_asn[i]:
        q = queue.Queue()
        v_asn[i] = True
        q.put(i)
        while not q.empty():
            qi = q.get()
            for a in g[qi]:
                if not v_asn[a[0]]:
                    v_asn[a[0]] = True
                    v[a[0]] = v[qi] + a[1]
                    q.put(a[0])
                else:
                    if v[a[0]] != v[qi] + a[1]:
                        f = False
                        break
        if not f:
            break

if f:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

N, X, Y, Z = map(int, input().split())
p = 10 ** 9 + 7
m = 1
m <<= X
m += 1
m <<= Y
m += 1
m <<= Z - 1
L = 2 ** (X + Y + Z - 1)
M = [[0 for _ in range(10)] for _ in range(L)]
for i in range(L):
  for j in range(10):
    k =  i << (j + 1)
    k += 1 << j
    M[i][j] = (k % L) if k & m != m else -1
DP = [[0 for _ in range(L)] for _ in range(N + 1)]
DP[0][0] = 1
for i in range(N):
  for j in range(L):
    if DP[i][j] == 0:
      continue
    DP[i][j] %= p
    for k in range(10):
      l = M[j][k]
      if l < 0:
        continue
      DP[i + 1][l] += DP[i][j]
cnt = 10 ** N % p
print((cnt - sum(DP[N]) % p) % p)

### FIXED CODE ###

N, X, Y, Z = map(int, input().split())
p = 10 ** 9 + 7
m = 1
m <<= X
m += 1
m <<= Y
m += 1
m <<= Z - 1
L = 2 ** (X + Y + Z - 1)
M = [[0 for _ in range(10)] for _ in range(L)]
for i in range(L):
  for j in range(10):
    k =  i << (j + 1)
    k += 1 << j
    M[i][j] = (k % L) if k & m != m else -1
DP = [[0 for _ in range(L)] for _ in range(N + 1)]
DP[0][0] = 1
for i in range(N):
  for j in range(L):
    if DP[i][j] == 0:
      continue
    DP[i][j] %= p
    for k in range(10):
      l = M[j][k]
      if l < 0:
        continue
      DP[i + 1][l] += DP[i][j]
cnt = 10 ** N % p
print((cnt - sum(DP[N]) % p) % p)
### BUGGY CODE ###


def s0():return input()
def s1():return input().split()
def s2(n):return [input() for x in range(n)]
def s3(n):return [input().split() for _ in range(n)]
def s4(n):return [[x for x in s] for s in s2(n)]
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]
def t3(n):return [tuple(int(x) for x in input().split()) for _ in range(n)]
def p0(b,yes="Yes",no="No"): print(yes if b else no)
# from sys import setrecursionlimit
# setrecursionlimit(1000000)
from collections import Counter,deque,defaultdict
import itertools
# import math
# import networkx as nx
# from bisect import bisect_left,bisect_right
# from heapq import heapify,heappush,heappop
n=n0()
s=s0()

c=Counter(s)
d=list(c.values())
MOD=10**9+7

def prod(line):
    r=1
    for i in line:
        r*=i
        r%=MOD
    return r

i=2
ans=sum(d)
while i<=len(d):
    tmp=itertools.combinations(d,i)
    for line in tmp:
        ans+=prod(line)
    i+=1

print(ans%MOD)

### FIXED CODE ###


def s0():return input()
def s1():return input().split()
def s2(n):return [input() for x in range(n)]
def s3(n):return [input().split() for _ in range(n)]
def s4(n):return [[x for x in s] for s in s2(n)]
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]
def t3(n):return [tuple(int(x) for x in input().split()) for _ in range(n)]
def p0(b,yes="Yes",no="No"): print(yes if b else no)
# from sys import setrecursionlimit
# setrecursionlimit(1000000)
from collections import Counter,deque,defaultdict
import itertools
# import math
# import networkx as nx
# from bisect import bisect_left,bisect_right
# from heapq import heapify,heappush,heappop
n=n0()
s=s0()

c=Counter(s)
d=list(c.values())
MOD=10**9+7

def prod(line):
    r=1
    for i in line:
        r*=i
        r%=MOD
    return r


ans=prod([i+1 for i in d])
print((ans-1)%MOD)
### BUGGY CODE ###

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

K=int(input())

ans=0

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

print(ans)

### FIXED CODE ###

import math


K=int(input())

ans=0

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

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

s = list(str(input()))
n = len(s)

from itertools import product

ans = 0

m = s.count('?')

for x in product([0,1,2,3,4,5,6,7,8,9], repeat=m):
    p_x = 0
    s_num = 0
    for i in range(n):
        if s[i] == '?':
            s_num += int(x[p_x])*(10**(n-1-i))
            p_x += 1
        else:
            s_num += int(s[i])*(10**(n-1-i))
    if s_num % 13 == 5:
        ans += 1

print(ans%(10**9+7))


### FIXED CODE ###

s = list(str(input()))

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

for i in range(n):
    prev = dp[:]
    dp = [0]*13

    if s[i] == '?':
        for z in range(10):
            for j in range(13):
                dp[(j*10+z)%13] += prev[j]
                dp[(j*10+z)%13] %= 10**9+7

    else:
       _s = int(s[i])
       for j in range(13):
            dp[(j*10+_s)%13] += prev[j]
            dp[(j*10+_s)%13] %= 10**9+7

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

X,Y,Z,K = map(int,input().split())
A = sorted(list(map(int, input().split())), reverse=True)
B = sorted(list(map(int, input().split())), reverse=True)
C = sorted(list(map(int, input().split())), reverse=True)
xy=[]
for a in A:
    for b in B:
        xy.append(a+b)
xy=sorted(xy,reverse=True)
xy=xy[:K]
xyz=[]
for x in xy[:K]:
    for c in C:
        xyz.append(x+c)
xyz=sorted(xyz,reverse=True)
for i in range(K):
    print(xyz[i])


### FIXED CODE ###

X,Y,Z,K = map(int,input().split())
A = sorted(list(map(int, input().split())), reverse=True)
B = sorted(list(map(int, input().split())), reverse=True)
C = sorted(list(map(int, input().split())), reverse=True)
xy=[]
for a in A:
    for b in B:
        xy.append(a+b)
xy=sorted(xy,reverse=True)
xy=xy[:K]
xyz=[]
for c in C:
    for x in xy:
        xyz.append(x+c)
xyz=sorted(xyz,reverse=True)
for i in range(K):
    print(xyz[i])
### BUGGY CODE ###

N, K, Q = map(int, input().split())
A = [0] * Q
for i in range(Q):
    A[i] = int(input())

for i in range(N):
    if K - Q + A.count(i + 1) > 0:
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

import collections

N, K, Q = map(int, input().split())
A = [0] * N
for i in range(Q):
    A[int(input()) - 1] += 1

for i in range(N):
    if K - Q + A[i] > 0:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

from collections import Counter

h, w, n = map(int, input().split())
a_list = [0 for _ in range((w - 2) * (h - 2))]
for _ in range(n):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    for a_i in range(a - 2, a + 1):
        for b_i in range(b - 2, b + 1):
            if (0 <= a_i < h - 2) & (0 <= b_i < w - 2):
                a_list[(b_i * (h - 2)) + a_i] += 1

k = Counter(a_list)
for i in range(10):
    if i in k.keys():
        print(k[i])
    else:
        print(0)

### FIXED CODE ###

from collections import Counter, defaultdict

ans = defaultdict(lambda: 0)
h, w, n = map(int, input().split())
for _ in range(n):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    for a_i in range(a - 2, a + 1):
        for b_i in range(b - 2, b + 1):
            if (0 <= a_i < h - 2) & (0 <= b_i < w - 2):
                ans[(a_i, b_i)] += 1

k = Counter(ans.values())
print((h - 2) * (w - 2) - sum(k.values()))
for i in range(1, 10):
    if i in k.keys():
        print(k[i])
    else:
        print(0)
### BUGGY CODE ###

s=input()
n=len("s")
q=int(input())
l=[]
m=0
for i in range(q):
    l.append(input())
    if l[i]=="1":
        m += 1

    else:
        due,f,c=l[i].split()
        if (f=="1" and m % 2==0) or (f !="1" and m % 2==1) :
            s = c+s
        else:
            s = s+c
if m % 2 ==1:
    s=s[::-1]

print(s)

### FIXED CODE ###

s=input()
n=len("s")
q=int(input())
l=[]
start=""
end=""
m=0
for i in range(q):
    l.append(input())
    if l[i]=="1":
        m += 1

    else:
        due,f,c=l[i].split()
        if (f=="1" and m % 2==0) or (f !="1" and m % 2==1) :
            start += c
        else:
            end += c
if m % 2 ==0:

    start=start[::-1]
    s = start + s + end

else:
    s = s + end
    s = s[::-1]
    s = s + start

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

N = int(input())
A = [int(input()) for _ in range(N)]

color = []
for i in range(N):
    if i == 0:
        color.append(A[i])
    else:
        for j in range(len(color)):
            if A[i] > color[j]:
                color[j] = A[i]
                break
        else:
            color.append(A[i])

print(len(color))




### FIXED CODE ###

import bisect
import  collections

N = int(input())
A = [int(input()) for _ in range(N)]

x = collections.deque()

for i, a in enumerate(A):
    if i == 0:
        x.append(a)
    else:
        r = bisect.bisect_left(x, a)
        if r == 0:
            x.appendleft(a)
        else:
            x[r - 1] = a

print(len(x))
### BUGGY CODE ###

A, B, C = [int(v) for v in input().strip().split(" ")]
K = int(input().strip())

while K > 0:
    if B <= A:
        B *= 2
        K -= 1
    elif C <= B:
        C *= 2
        K -= 1

if C > B > A:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

A, B, C = [int(v) for v in input().strip().split(" ")]
K = int(input().strip())

while K > 0:
    if B <= A:
        B *= 2
        K -= 1
    elif C <= B:
        C *= 2
        K -= 1
    else:
        break

if C > B > A:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

import sys

if __name__ == '__main__':
    N, K = map(lambda x:int(x), sys.stdin.readline().split())
    S = list(map(lambda x: int(x), list(sys.stdin.readline().rstrip())))
    start, end = 0, 0
    bStart, bEnd = 0, 0
    while True:
        # S[start:end]にある孤立した0がK個以下か
        sub = S[start:end]
        # print(S, start, end)
        # 11001101
        # print(start, end)
        z = 0
        prev = 1
        for i in range(len(sub)):
            if prev == 1 and sub[i] == 0:
                z += 1
            prev = sub[i]
        # print(z)
        # exit()
        # 全員を起立させられるので，広げる
        if z <= K:
            if bEnd - bStart < end - start:
                bStart, bEnd = start, end
                # print(S, start, end)
            
            end += 1
            if end == len(S) + 1:
                break
        # 反転しても逆立ちが残るので，狭める
        else:
            start += 1
    S[bStart:bEnd] = [1 for _ in range(bStart, bEnd)]

    o, maxO = 0, 0
    prev = 1
    for s in S:
        # print(prev, s)
        if prev == 1 and s == 0:
            if o > maxO:
                maxO = o
            o = 0
        elif s == 1:
            o += 1
        prev = s
    else:
        if o > maxO:
            maxO = o

    print(maxO)

### FIXED CODE ###

import sys
from datetime import datetime

if __name__ == '__main__':
    N, K = map(lambda x:int(x), sys.stdin.readline().split())
    S = list(map(lambda x: int(x), list(sys.stdin.readline().rstrip())))
    start, end = 0, 0
    bStart, bEnd = 0, 0
    # 01010110
    #  * *
    # 広げる時:
    #   前回のz=1
    #   前回のs_end=1
    #   今回広がったもの=0
    #   今回のz=2
    # 狭める時:
    #   前回のz=1
    #   前回のs_start=1
    #   今回狭まったもの=0
    #   今回のz=1
    extend = True
    
    z = 0
    # print(S)
    while True:
        # assert start <= end
        # print(start, end, 'z:', z)
        
        # S[start:end]にある孤立した0がK個以下か
        # prev = 1
        # z = 0
        # for i in range(start, end):
        #     if prev == 1 and S[i] == 0:
        #         z += 1
        #     prev = S[i]
        if extend:
            end_back = 1 if end == 0 else S[end-1]
            if end_back == 1 and S[end] == 0:
                z += 1
        else:
            start_back = 1 if start == 0 else S[start-1]
            if start_back == 0 and S[start] == 1:
                z -= 1
        # input()
        # 全員を起立させられるので，広げる
        # print(z)
        if z <= K:
            if bEnd - bStart < end - start:
                bStart, bEnd = start, end
            end += 1
            if end == len(S):
                break
            extend = True
        # 反転しても逆立ちが残るので，狭める
        else:
            start += 1
            if start == len(S)-1:
                break
            extend = False
    bEnd += 1
    S[bStart:bEnd] = [1 for _ in range(bStart, bEnd)]
    # print(S, bStart, bEnd)

    o, maxO = 0, 0
    prev = 1
    for s in S:
        # print(prev, s)
        if prev == 1 and s == 0:
            if o > maxO:
                maxO = o
            o = 0
        elif s == 1:
            o += 1
        prev = s
    else:
        if o > maxO:
            maxO = o

    print(maxO)
### BUGGY CODE ###


s = input()
ans = [0 for i in range(len(s))]
for i in range(len(s)-5, -1, -1):
    for j in range(i+4, len(s)):
        x = int(s[i:j+1])
        if x %2019 == 0:
            ans[i] += 1
            if j+1 < len(s):
              ans[i] += ans[j+1]
            break

print(sum(ans))

### FIXED CODE ###

import collections
S = list(map(int, input()))[::-1]
mod_list = [0 for _ in range(len(S)+1)]
x = 0
d = 0
for i, s in enumerate(S):
    x += s * pow(10, d, 2019)
    d += 1
    mod_list[i] = x%2019
c = collections.Counter(mod_list)
ans = 0
for i in range(2020):
    ans += c[i] * (c[i]-1)//2
print(ans)