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

import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa == x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))

n,k = m()

s = [[] for i in range(n)]

sss = [[Max,Max,Max] for i in range(n)]

for i in range(k):
    u,v = m()
    u -= 1
    v -= 1
    if v not in s[u]:
        s[u].append(v)

st,g = m()
st -= 1
g -= 1
co = Max

eee = [[s,0,st,0]]
eee = cl.deque(eee)
def bfs(x,nn,now,coun):
    global eee,sss,g,co
    if min(sss[now][nn],coun) != Max:
        if nn == 0 and g == now:
            co = min(co,coun)
        else:
            sss[now][nn] = coun
            if nn == 2:
                nn = 0
                coun += 1
            else:
                nn += 1
            for i in x[now]:
                eee.append([x,nn,i,coun])
    else:
        if now == g and nn == 0:
            co = min(co,coun)

while eee:
    op = eee.popleft()
    bfs(op[0],op[1],op[2],op[3])

#dfs(s,0,g,0)
if co == Max:
    print(-1)
else:
    print(co)



### FIXED CODE ###

import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa == x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))

n,k = m()

s = [[] for i in range(n)]

sss = [[Max,Max,Max] for i in range(n)]

for i in range(k):
    u,v = m()
    u -= 1
    v -= 1
    if v not in s[u]:
        s[u].append(v)

st,g = m()
st -= 1
g -= 1
co = Max

eee = [[s,0,st,0]]
eee = cl.deque(eee)
def bfs(x,nn,now,coun):
    global eee,sss,g,co
    if sss[now][nn] == Max:
        if nn == 0 and g == now:
            co = min(co,coun)
        else:
            sss[now][nn] = coun
            if nn == 2:
                nn = 0
                coun += 1
            else:
                nn += 1
            for i in x[now]:
                eee.append([x,nn,i,coun])
    else:
        if now == g and nn == 0:
            co = min(co,coun)

while eee:
    op = eee.popleft()
    bfs(op[0],op[1],op[2],op[3])

#dfs(s,0,g,0)
if co == Max:
    print(-1)
else:
    print(co)
### BUGGY CODE ###


N= int(input())
a=[0]
for i in range(N):
    a.append(int(input()))

s = []
v = 1
for i in range(1,N+1):
    if v == 2:
        print(len(s))
        break
    elif v in s or i == N:
        print(-1)
        break
    else:
        s.append(v)
        v = a[v]

        


### FIXED CODE ###


N= int(input())
a=[0]
for i in range(N):
    a.append(int(input()))

s = set()
v = 1
for i in range(1,N+1):
    if v == 2:
        print(len(s))
        break
    elif v in s or i == N:
        print(-1)
        break
    else:
        s.add(v)
        v = a[v]
### BUGGY CODE ###

nk = list(map(int,input().split()))
p = list(map(int,input().split()))

sumseq = [0] * (nk[0] - nk[1] + 1)
for i in range(nk[0]):
    p[i] = (p[i] + 1) / 2 

for i in range(len(sumseq)):
    sumseq[i] = sum(p[i:i + nk[1]])


print(max(sumseq))

### FIXED CODE ###

nk = list(map(int,input().split()))
p = list(map(int,input().split()))
ans = [0] * (nk[0] + nk[1])
 
zeros = [0] * nk[1]
 
seq4search = zeros + p
 
for i in range(nk[1], nk[0] + nk[1]):
    seq4search[i] = (seq4search[i] + 1) / 2
    ans[i] = ans[i-1] + seq4search[i] - seq4search[i - nk[1]] 
 
print(max(ans))
### BUGGY CODE ###

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

P=sorted(list(set(S)))
T=[]
m=S.count(P[0])
T.append(P[0])
for i in range(1,len(P)):
    if S.count(P[i])>m:
        m=S.count(P[i])
        T.clear()
        T.append(P[i])
    elif S.count(P[i])==m:
        T.append(P[i])
for j in range(len(T)):
    print(T[j])




### FIXED CODE ###

from collections import Counter
N=int(input())
S=[input() for _ in range(N)]

C=Counter(S)
A=[]
B=[]
T=[]

for i,j in C.most_common():
    A.append(i)
    B.append(j)
for k in range(len(A)):
    if B[k]==B[0]:
        T.append(A[k])
T=sorted(T)
for m in range(len(T)):
  print(T[m])
### BUGGY CODE ###

import bisect
N = int(input())

L = [int(input())]
for _ in range(N - 1):
    a = int(input())
    if a <= L[0]:
        L.insert(0, a)
        continue

    i = bisect.bisect_left(L, a)
    L[i - 1] = a

print(len(L))

### FIXED CODE ###

import bisect
import sys
input = sys.stdin.readline

N = int(input())
L = [-1 * int(input())]
for _ in range(N - 1):
    a = -1 * int(input())
    if a >= L[-1]:
        L.append(a)
        continue

    i = bisect.bisect_right(L, a)
    L[i] = a

print(len(L))
### BUGGY CODE ###

from fractions import gcd

K = int(input())

res = 0
for i in range(1,K+1):
    for j in range(1,K+1):
        for k in range(1,K+1):
            res += gcd(gcd(i,j),k)
print(res)

### FIXED CODE ###

from math import gcd

K = int(input())

res = 0
for i in range(1,K+1):
    for j in range(1,K+1):
        tmp = gcd(i,j)
        for k in range(1,K+1):
            res += gcd(tmp,k)
print(res)
### BUGGY CODE ###

n = int(input())
L = list(map(int, input().split()))
L.sort()
count = 0
for i, l1 in enumerate(L):
    for k, l2 in enumerate(L[i+1:]):
        num = i + k + 2
        for l3 in L[num:]:
            if l1 + l2 < l3:
                break
            if l1 < l2 + l3 and l2 < l1 + l3 and l3 < l2 + l1:
                count += 1
            else:
                break

print(count)


### FIXED CODE ###

import bisect

n = int(input())
L = list(map(int, 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[j+1:], L[i]+L[j])
        count += k

print(count)
### BUGGY CODE ###

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

h, w = lmi()
s = [input() for i in range(h)]

cnt = [[0 for i in range(w)] for j in range(h)]
for i in range(h):
    j = 0
    while j < w:
        if s[i][j] == '#':
            j += 1
            continue
        l = 0
        while j+l < w:
            if s[i][j+l] == '#':
                break
            l += 1
        for k in range(l):
            cnt[i][j+k] += l
        j += l+1

for i in range(w):
    j = 0
    while j < h:
        if s[j][i] == '#':
            j += 1
            continue
        l = 0
        while j+l < h:
            if s[j+l][i] == '#':
                break
            l += 1
        for k in range(l):
            cnt[j+k][i] += l
        j += l+1


print(max([max([cnt[i][j] for i in range(h)]) for j in range(w)])-1)


### FIXED CODE ###

import sys
from bisect import bisect_left
sys.setrecursionlimit(10**7)
def lmi(): return list(map(int, input().split()))

h, w = lmi()
s = [input() for i in range(h)]

a = [[] for i in range(h)]
al = [[] for i in range(h)]
b = [[] for i in range(w)]
bl = [[] for i in range(w)]
for i in range(h):
    k = 0
    for j in range(w):
        if s[i][j] == '.':
            k += 1
            if j == w-1:
                a[i].append(k)
                al[i].append(j)
        elif j != 0 and s[i][j-1] == '.':
            a[i].append(k)
            al[i].append(j-1)
            k = 0

for i in range(w):
    k = 0
    for j in range(h):
        if s[j][i] == '.':
            k += 1
            if j == h-1:
                b[i].append(k)
                bl[i].append(j)
        elif j != 0 and s[j-1][i] == '.':
            b[i].append(k)
            bl[i].append(j-1)
            k = 0
'''
print(a)
print(al)
print(b)
print(bl)
'''

ans = 0
for i in range(h):
    k = 0
    c = -1
    for j in range(w):
        if s[i][j] == '.':
            c = a[i][k]
            d = b[j][bisect_left(bl[j], i)]
            #print(c,d)
            ans = max(ans, c+d-1)
        elif j != 0 and s[i][j-1] == '.' and c != -1:
                k += 1
print(ans)
### BUGGY CODE ###

N = int(input())
L = map(int, input().split())
SL = sorted(list(L))
A = [0] * (10 ** 3 + 10)

for i in SL:
    A[i] = True
for i in range(len(A)):
    if A[i] == True:
        A[i] = A[i-1] + 1
    else:
        A[i] = A[i-1]

# print(A[4-1] - A[2])

ans = 0
for i in range(N-2):
    for j in range(i+1, N-1):
        for k in range(j+1, N):
            # print(i, j, k)
            a = SL[i]
            b = SL[j]
            c = SL[k]
            if a < b + c and b < c + a and c < a + b:
                ans += 1
print(ans)

### FIXED CODE ###

N = int(input())
L = map(int, input().split())
SL = sorted(list(L))
# print('SL', SL)
import bisect

ans = 0
for i in range(N-2):
    for j in range(i+1, N-1):
        ab = SL[i] + SL[j]
        # print(i, j)
        # print(SL[i], SL[j])
        r = bisect.bisect_left(SL, ab)
        l = j + 1
        # print('r', r)
        # print('l', l)
        # print('---')
        ans += max(0, r - l)

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

a,b = map(int,input().split())
import math
if a==b:
  print(math.factorial(a)**2*2%(10**9+7))
elif abs(a-b)==1:
  print(math.factorial(max(a,b))**2//max(a,b))
else:
  print(0)

### FIXED CODE ###


a,b = map(int,input().split())
import math
if a==b:
  print((math.factorial(a)%(10**9+7))**2*2%(10**9+7))
elif abs(a-b)==1:
  print((math.factorial(max(a,b))%(10**9+7))*(math.factorial(min(a,b))%(10**9+7))%(10**9+7))
else:
  print(0)
### BUGGY CODE ###

import collections as cl
def l(): #intのlist
    return list(map(int,input().split()))
def onem(): #Nとかの取得
    return int(input())
n = onem()

on = []
de = cl.deque()
ppp = [n-1 for i in range(n)]
for i in range(n):
    k = l()
    for j in range(n-1):
        k[j] -= 1
    k.reverse()
    de.append([k[0],i])
    on.append(cl.deque(k))


co = 1
ddd = cl.deque()
de.append([-1,-1])
ppppp = [1 for i in range(n)]
cl = ppppp[:]
while de:
    kkk = de.popleft()
    if kkk[0] == -1 and kkk[1] == -1:
        if sum(cl) == n:
            co = -1
            break
        if len(de) == 0:
            break
        de.append([-1,-1])
        co += 1
        cl = ppppp[:]

    elif ppp[kkk[0]] != 0 and on[kkk[0]][0] == kkk[1] and cl[kkk[0]] and cl[kkk[1]]:
        cl[kkk[0]] = 0
        cl[kkk[1]] = 0
        on[kkk[0]].popleft()
        on[kkk[1]].popleft()
        ppp[kkk[0]] -= 1
        ppp[kkk[1]] -= 1
        if ppp[kkk[1]] != 0 != 0 and ppp[kkk[0]] != 0 and on[kkk[1]][0] == kkk[0] and on[kkk[0]][0] == kkk[1]:
            de.append([on[kkk[1]][0],kkk[1]])
        else:
            if len(on[kkk[1]]) != 0:
                de.append([on[kkk[1]][0],kkk[1]])
            if len(on[kkk[0]]) != 0:
                de.append([on[kkk[0]][0],kkk[0]])


print(co)


### FIXED CODE ###

import collections as cl
def l(): #intのlist
    return list(map(int,input().split()))
def onem(): #Nとかの取得
    return int(input())
n = onem()

on = []
de = cl.deque()
ppp = [n-1 for i in range(n)]
for i in range(n):
    k = l()
    for j in range(n-1):
        k[j] -= 1
    k.reverse()
    de.append([k[0],i])
    on.append(cl.deque(k))


co = 1
ddd = cl.deque()
de.append([-1,-1])
ppppp = [1 for i in range(n)]
cl = ppppp[:]
while de:
    kkk = de.popleft()
    if kkk[0] == -1 and kkk[1] == -1:
        if sum(cl) == n:
            co = -1
            break
        if len(de) == 0:
            break
        de.append([-1,-1])
        co += 1
        cl = ppppp[:]

    elif ppp[kkk[0]] != 0 and on[kkk[0]][0] == kkk[1] and cl[kkk[0]] and cl[kkk[1]]:
        cl[kkk[0]] = 0
        cl[kkk[1]] = 0
        on[kkk[0]].popleft()
        on[kkk[1]].popleft()
        ppp[kkk[0]] -= 1
        ppp[kkk[1]] -= 1
        if ppp[kkk[1]] != 0 != 0 and ppp[kkk[0]] != 0 and on[kkk[1]][0] == kkk[0] and on[kkk[0]][0] == kkk[1]:
            de.append([on[kkk[1]][0],kkk[1]])
        else:
            if len(on[kkk[1]]) != 0:
                de.append([on[kkk[1]][0],kkk[1]])
            if len(on[kkk[0]]) != 0:
                de.append([on[kkk[0]][0],kkk[0]])


print(co)
### BUGGY CODE ###

from itertools import permutations

N, M, K = map(int, input().split())
A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]

l = set(permutations('A'*N+'B'*M, N+M))

cnt_list = []

for i in l:
    time = 0
    cnt = 0
    indA = 0
    indB = 0
    for n in range(N+M):
        if i[n] == 'A':
            time += A[indA]
            indA += 1
        else:
            time += B[indB]
            indB += 1
        if time > K:
            break
        cnt += 1
    cnt_list.append(cnt)

print(max(cnt_list))


### FIXED CODE ###

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

a, b = [0], [0]

for i in range(N):
    a.append(a[i] + A[i])

for i in range(M):
    b.append(b[i] + B[i])

ans, j = 0, M

for i in range(N+1):
    if a[i] > K:
        break
    while b[j] > K - a[i]:
        j -= 1
    ans = max(ans, i+j)
print(ans)
### BUGGY CODE ###

N,M=map(int,input().split())
A=[list(map(int,input().split())) for i in range(M)]
D=[[]for i in range(N)]
for i in range(M):
  D[A[i][0]-1].append(A[i][1]-1)
  D[A[i][1]-1].append(A[i][0]-1)
for i in D[-1]:
  for j in D[0]:
    if i==j:
      print('POSSIBLE')
      exit()
print('IMPOSSIBLE')      

### FIXED CODE ###

N,M=map(int,input().split())
A=[list(map(int,input().split())) for i in range(M)]
D=[[]for i in range(N)]
for i in range(M):
  D[A[i][0]-1].append(A[i][1]-1)
  D[A[i][1]-1].append(A[i][0]-1)
a=len(D[-1])
b=len(D[0])
c=len(set(D[-1]+D[0]))
if a+b==c:
  print('IMPOSSIBLE')
else:
  print('POSSIBLE')
### BUGGY CODE ###

from operator import itemgetter
import numpy as np

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

data = []
for i in range(N):
    data.append([int(i) for i in input().split()])

data.sort(key=itemgetter(0))

dp = [dict() for _ in range(N)]
for i in range(T):
    dp[0][i] = 0

dp[0][T] = data[0][1]
for i in range(1, N):
    time = data[i-1][0]
    value = data[i-1][1]
    add_value = data[i][1]
    for j in range(T):
        if j >= time:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-time] + value)
        else:
            dp[i][j] = dp[i-1][j]
    dp[i][T] = max(dp[i][T-1] + add_value, dp[i-1][T])
print(dp[-1][T])


### FIXED CODE ###

from operator import itemgetter
N, T = [int(i) for i in input().split()]

data = []
for i in range(N):
    data.append([int(i) for i in input().split()])

data.sort(key=itemgetter(0))

dp = [[0]*(T) for i in range(N)]
ans = data[0][1]
for i in range(1, N):
    for j in range(T):
        if j >= data[i-1][0]:
            value1 = dp[i-1][j]
            value2 = dp[i-1][j-data[i-1][0]] + data[i-1][1]
            dp[i][j] = max(value1, value2)
        else:
            dp[i][j] = dp[i-1][j]
    value3 = dp[i][T-1] + data[i][1]
    ans = max(value3, ans)
print(ans)
### BUGGY CODE ###

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

#print( N,S )   

passwd = [ [ [False for _ in range(10) ] for _ in range(10) ] for _ in range(10) ]
#print(passwd)

cnt = 0

for i1 in range(N-2):
    for i2 in range(i1+1,N-1):
        for i3 in range(i2+1, N):
            if passwd[int(S[i1])][int(S[i2])][int(S[i3])] == False:
                cnt = cnt + 1
                passwd[int(S[i1])][int(S[i2])][int(S[i3])] = True
            #ppp = S[i1]+S[i2]+S[i3]
            #print(i1,i2,i3, ppp)

#print(passwd)
print(cnt)


### FIXED CODE ###

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

#print( N,S )   

cnt = 0
s_flgs = [[False for _ in range(10) ] for _ in range(3)]

for i1 in range(N-2):
    if s_flgs[0][int(S[i1])] == True:
        continue
    s_flgs[0][int(S[i1])] = True
    s_flgs[1] = [False for _ in range(10) ]
    for i2 in range(i1+1,N-1):
        if s_flgs[1][int(S[i2])] == True:
            continue
        s_flgs[1][int(S[i2])] = True
        s_flgs[2] = [False for _ in range(10) ]
        for i3 in range(i2+1, N):
            if s_flgs[2][int(S[i3])] == True:
                continue
            s_flgs[2][int(S[i3])] = True
            cnt = cnt + 1
            #ppp = S[i1]+S[i2]+S[i3]
            #print(i1,i2,i3, ppp)

print(cnt)
### BUGGY CODE ###

import collections
N, Q = map(int, input().split())
C = list(map(int, input().split()))

D_origin = {}
for i in range(N):
    D_origin.update({C[i]:0})
D = dict(D_origin)
E = [{0:0}] * N
for i in range(N):
    D[C[i]] += 1
    D_other = dict(D)
    E[i] = D_other

ANS = []
for i in range(Q):
    l, r = map(int, input().split())
    if l == 1:
        E_dif = dict(E[r - 1].items() - D_origin.items())
    else:
        E_dif = dict(E[r - 1].items() - E[l - 2].items())
    ans = len(E_dif.values())
    ANS.append(ans)
for i in range(Q):
    print(ANS[i])


### FIXED CODE ###

from collections import defaultdict
import sys
def read():
    return sys.stdin.readline().rstrip()
def main():
    N, Q = map(int, read().split())
    C = list(map(int, read().split()))
    E = defaultdict(list)

    D = [-1] * (N + 1)
    for i in range(N):
        D_i = D[C[i]]
        if D_i != -1:
            E[D_i].append((D_i, i))
        D[C[i]] = i

    F = defaultdict(list)
    for i in range(Q):
        l, r = map(int, input().split())
        F[l-1].append((r - 1, i))



    # Binary Indexed Tree (Fenwick Tree)
    class BIT:
        def __init__(self, n):
            self.n = n
            self.data = [0] * (n + 1)
            self.el = [0] * (n + 1)

        def sum(self, i):
            s = 0
            while i > 0:
                s += self.data[i]
                i -= i & -i
            return s

        def add(self, i, x):
            # assert i > 0
            self.el[i] += x
            while i <= self.n:
                self.data[i] += x
                i += i & -i

        def get(self, i, j=None):
            if j is None:
                return self.el[i]
            return self.sum(j) - self.sum(i)

    ANS = [0] * Q
    d = BIT(N)
    for x in range(N - 1, -1, -1):
        for e in E[x]:
            d.add(e[1], 1)
        for f in F[x]:
            ANS[f[1]] = f[0] - x + 1 - d.sum(f[0])

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

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

from math import *

p = 1000000007
ft = []
ift = []

def make_ft(max):
    x = 1
    ft.append(x)
    # ft[i] == i!
    for i in range(1, max+1):
        x *= i
        x %= p
        ft.append(x)
    return

# i!^-1 == i!^(p+2) (mod p)
def make_ift(max):
    ift.append(1)
    for i in range(1, max+1):
        invf = 1
        x = ft[i]
        for j in range(ceil(log2(p-2))):
            # x == i!^2^j
            if ((p - 2) >> j) & 1:
                invf *= x
                invf %= p
            x *= x
            x %= p
        ift.append(invf)
    return

def combination(a, b):
    res = ft[a] * ift[b] * ift[a-b]
    res %= p
    return res

def main():
    H, W, A, B = list(map(int, input().split()))

    make_ft(H+W)
    make_ift(H+W)
    ans = 0
    for i in range(H-A):
        ans += combination(B+i-1, i) * combination(W-B+H-i-2, H-i-1)
        ans %= p

    print(ans)

if __name__ == '__main__':
    main()


### FIXED CODE ###

H, W, A, B = list(map(int, input().split()))
p = 1000000007

fac = [1] * (H + W + 1)
x = 1
for i in range(1, H + W + 1):
    x *= i
    x %= p
    fac[i] = x

ifac = [1] * (H + W + 1)
x = fac[H + W]
q = p - 2

while q > 0:
    if q & 1:
        ifac[H + W] *= x % p
    x *= x % p
    q >>= 1

for i in range(H + W - 1, 0, -1):
    ifac[i] = ifac[i + 1] * (i + 1) % p

def com(a, b):
    return (fac[a] * ifac[b] * ifac[a-b]) % p

ans = 0

for i in range(H-A):
    ans += com(B+i-1, i) * com(W-B+H-i-2, H-i-1)
    ans %= p

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

N,M,K=map(int,input().split())
costA=list(map(int,input().split()))
costB=list(map(int,input().split()))
time=0
count=0
cost=sorted(costA+costB)
while time<=K:
    time+=cost[0]
    count+=1
    del cost[0]
    if len(cost)==0:
        count+=1
        break
print(count-1)

### FIXED CODE ###

N,M,K=map(int,input().split())
costA=list(map(int,input().split()))
costB=list(map(int,input().split()))
costA=[0]+costA
costB=[0]+costB

for i in range(N):
    costA[i+1]+=costA[i]
    
for i in range(M):
    costB[i+1]+=costB[i]

"""print(costA)
print(costB)"""

""

def upper_bound(list1,K):
    low=0
    high=len(list1) #index
    while high-low!=1:
        mid=(high+low)//2
        if list1[mid]>K:
            high=mid
        else:
            low=mid
    return low  #条件を満たす左側の要素数

number=[]
#print(costA)
#print(costB)
for i in range(N+1): #A側の机の本を固定 残りの時間でBを二分探索
    time=K-costA[i]
    if time<0:
        break
    #print(i,upper_bound(costB,time))
    number.append(i+upper_bound(costB,time))

"""print(i)
    print(upper_bound(costB,time))
    print(number)"""
    
print(max(number))



"""
print(cumcost)
#以下二分探索 必要なのはソート済みリストと検索したい値
#upper bound 基準値よりも大きい最初の値を返す
#lower bound 基準値以上の最初の値を返す
#欲しい値はl基準値以下の最大値=upper bound値−１の位置の値
    #冊数は+1なので、求める値はupper_bound
# 検索したい値＝K分を超えない最大の値
low=0
high=len(cumcost)-1
while high-low!=1: #差が１になったら終了
    print(high)
    print(low)
    mid=(high+low)//2 #pythonの//は切り捨て徐算
    if cumcost[mid]>K:  #推測した値が大きすぎた ### 値のダブり注意
        high=mid
    else: # 推測した値小さすぎた#cumcost<=K
        low=mid 
#条件を満たす値の個数 (upper_bound)
    #条件を満たすのが左・・・high
    #条件を満たすのが右・・・len(cumcost)--1-low
upper_bound=high #最終的な値はupper_bound
print(upper_bound)
"""
"""境界線が端っこにあると上手に探索できない
→例外処理で乗り切るか　探索のやり方自体を変更するか　どちらが良いか？"""
### BUGGY CODE ###

import itertools
import sys
import math
import numpy as np
from collections import deque
from itertools import combinations
from functools import reduce
from functools import lru_cache
sys.setrecursionlimit(10**9)

def main():
    N,P=map(int,input().split())
    S = input()

    ans = 0
    if not 10 % P == 0:
        d = [0] * (P+1)
        s = 0

        d[0] = 1
        for i in range(N):
            s += int(S[N-i-1]) * 10**i
            d[s % P] += 1

        for m in range(P):
            if d[m] > 0:
                ans += d[m] * (d[m]-1) // 2

    else:
        target = [0,5] if P == 5 else [0,2,4,6,8]
        for i in range(N):
            if int(S[i]) in target:
                ans += i+1



    print(ans)


if __name__ == "__main__":
  main()


### FIXED CODE ###

import numpy as np
import sys
sys.setrecursionlimit(10**9)


INF=10**20
def solve(N,P,S,fact):
    ans = 0

    if not 10 % P == 0:
        d = [0] * (P+1)
        s = 0
 
        d[0] = 1
        for i in range(N):
            s += S[N-i-1] * fact[i]
            s %= P
            # s = int(s)
            d[s] += 1
            # print(s)
 
        for m in range(P):
            if d[m] > 0:
                ans += d[m] * (d[m]-1) // 2
 
    else:
        for i in range(N):
            if S[i] % P == 0:
                ans += i+1

 
    return ans

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    P = int(next(tokens))  # type: int
    S = list(next(tokens))  # type: str

    fact = [pow(10,i,P) for i in range(N)]

    S = list(map(int,S))
    S = np.array(S)
    print(solve(N, P, S,np.array(fact)))


def cc_export():
    from numba.pycc import CC
    cc = CC('my_module')

    # basic types: https://numba.pydata.org/numba-doc/0.13/types.html
    cc.export('solve', '(i8,i8,i8[:],i8[:],)')(solve)
    cc.compile()

if __name__ == '__main__':
    # cc_export()
    try:
        from my_module import solve
    except:
        cc_export()
        exit()

    main()