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

def main():
	N, K = map(int, input().split())
	DIV = 10**9+7
	sqrtn = int(N**0.5)
	ans = 1
	s = []
	for i in range(1, sqrtn+1):
		s.append(i)
		if i < N//i:
			s.append(N//i)
	s.sort()

	r = []
	for i in range(len(s)-1):
		left = N//s[i+1]
		right = N//s[i]
		r.append(right-left)
	r.append(1)

	m = len(s)
	mp = {}
	for i in range(m):
		mp[s[i]] = i

	dp = [[0 for _ in range(m)] for _ in range(K+1)]
	dp[0][mp[N]] = 1
	for i in range(K):
		for j in range(m-2, -1, -1):
			dp[i][j] += dp[i][j+1]
			dp[i][j] %= DIV
		for j in range(m):
			nj = mp[N//s[j]]
			dp[i+1][j] += dp[i][nj]*r[j]%DIV
			dp[i+1][j] %= DIV

	ans = 0
	for j in range(m):
		ans += dp[K][j]
		ans %= DIV
	print(ans)


if __name__ == '__main__':
	main()

### FIXED CODE ###

def main():
	N, K = map(int, input().split())
	DIV = 10**9+7
	sqrtn = int(N**0.5)
	ans = 1
	s = []
	for i in range(1, sqrtn+1):
		s.append(i)
		if i < N//i:
			s.append(N//i)
	s.sort()

	r = []
	for i in range(len(s)-1):
		left = N//s[i+1]
		right = N//s[i]
		r.append(right-left)
	r.append(1)

	m = len(s)
	mp = {}
	for i in range(m):
		mp[s[i]] = i

	dp = [[0 for _ in range(m)] for _ in range(K+1)]
	dp[0][mp[N]] = 1
	for i in range(K):
		for j in range(m-2, -1, -1):
			dp[i][j] += dp[i][j+1]
			dp[i][j] %= DIV
		for j in range(m):
			nj = mp[N//s[j]]
			dp[i+1][j] += dp[i][nj]*r[j]%DIV
			dp[i+1][j] %= DIV

	ans = 0
	for j in range(m):
		ans += dp[K][j]
		ans %= DIV
	print(ans)


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

# -*- coding: utf-8 -*-

n = int(input())
s = [ input() for i in range(n)]
count = 0
x = [sorted(i) for i in s]
_x = sorted(x)

for i in range(n-1):
    for j in range(i+1,n):
        if _x[i] == _x[j]:
            count += 1
        else:
            break

print(count)

### FIXED CODE ###

# -*- coding: utf-8 -*-
n = int(raw_input())
d = {}
ans = 0
for i in range(n):
    si = ''.join(sorted(raw_input()))
    if si in d:
        ans += d[si]
        d[si] += 1
    else:
        d[si] = 1
print(ans)
### BUGGY CODE ###

n,k = map(int,input().split())

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

evaluation = 1

for i in range(k):
    evaluation *= a[i]

for i in range(k, n+1):
    if i == n:
        break
    #print(a[i], a[i-k])
    next_evaluation = a[i]*evaluation//a[i-k]
    if evaluation < next_evaluation:
        print('Yes')
    else:
        print('No')
    evaluation = next_evaluation

### FIXED CODE ###

n,k = map(int,input().split())

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


for i in range(k, n+1):
    if i == n:
        break
    #print(a[i], a[i-k])
    if a[i-k] < a[i]:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

s = input()
q = int(input())

sei_or_gyaku = 1
mae = ''
ato = ''

for i in range(q):
    sirei = input()
    if len(sirei) == 1:
        ti = int(sirei)
        sei_or_gyaku *= -1
    else:
        ti, fi, ci = map(str, sirei.split())
        ti, fi = int(ti), int(fi)
        if fi == 1:
            if sei_or_gyaku == 1:
                mae += ci
            else:
                ato += ci
        else:
            if sei_or_gyaku == 1:
                ato += ci
            else:
                mae += ci

mae = mae[::-1]
ans = mae + s + ato
if sei_or_gyaku == 1:
    print(ans)
else:
    print(ans[::-1])

### FIXED CODE ###

s = input()
q = int(input())

sei_or_gyaku = 1
mae = ''
ato = ''

for i in range(q):
    sirei = input()
    if len(sirei) == 1:
        ti = int(sirei)
        sei_or_gyaku *= -1
    else:
        ti, fi, ci = map(str, sirei.split())
        ti, fi = int(ti), int(fi)
        if fi == 1:
            if sei_or_gyaku == 1:
                mae += ci
            else:
                ato += ci
        else:
            if sei_or_gyaku == 1:
                ato += ci
            else:
                mae += ci

mae = mae[::-1]
ans = mae + s + ato
if sei_or_gyaku == 1:
    print(ans)
else:
    print(ans[::-1])
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
a=sorted(a)
ans=a[0]#暫定最小

amari=[ans]
if len(set(a))!=1:
    for _ in range(a[0]):
        for i in range(n):
            if a[i]%ans>0:
                amari+=[a[i]%ans]
            ans=min(amari)

print(ans)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
import fractions as ft


ans=a[0]
for i in a:
    ans=ft.gcd(ans,i)
print(ans)
### BUGGY CODE ###

import sys
input = lambda: sys.stdin.readline().rstrip()
n, k = map(int, input().split())
a = list(map(int, input().split()))

now = 1
for i in range(k):
    now *= a[i]
before = now

for i in range(n - k):
    now *= a[i + k]
    now /= a[i]
    if now > before:
        print('Yes')
    else:
        print('No')
    before = now


### FIXED CODE ###

import sys
input = lambda: sys.stdin.readline().rstrip()
n, k = map(int, input().split())
a = list(map(int, input().split()))

now = 1
# for i in range(k):
#     now *= a[i]
# before = now

for i in range(n - k):
    # now *= a[i + k]
    # now /= a[i]
    if a[i] < a[i + k]:
        print('Yes')
    else:
        print('No')
    # before = now
### BUGGY CODE ###

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

adic = {}
bdic = {}
cdic = {}


setabc = list(sorted(list(set(a) | set(b) | set(c))))

setdict = {}
for i in range(len(setabc)):
    setdict.update({setabc[i]:i})
    

for i in range(len(a)):
    if setdict[a[i]] in adic:
        adic[setdict[a[i]]] =  adic[setdict[a[i]]] + 1 
    else:
        adic.update({setdict[a[i]]:1})

for i in range(len(b)):
    if setdict[b[i]] in bdic:
        bdic[setdict[b[i]]] =  bdic[setdict[b[i]]] + 1 
    else:
        bdic.update({setdict[b[i]]:1})

for i in range(len(c)):
    if setdict[c[i]] in cdic:
        cdic[setdict[c[i]]] =  cdic[setdict[c[i]]] + 1 
    else:
        cdic.update({setdict[c[i]]:1})

ami = min(adic.keys())
ama = max(adic.keys())
bmi= min(bdic.keys())
bma= max(bdic.keys())
cmi= min(cdic.keys())
cma= max(cdic.keys())

        
        
summer = 0
for i in  adic.keys():
    for j in bdic.keys():
        if i < j:
            for k in cdic.keys():
                if j < k:
                    summer = summer + adic[i] * bdic[j] * cdic[k] 
                
print(summer)
                
    
            

### FIXED CODE ###

N = int(input())
a = list(map(int,input().split(" ")))
b = list(map(int,input().split(" ")))
c = list(map(int,input().split(" ")))
#アルゴリズムわからないけどN log N?
a.sort()
b.sort()
c.sort()
 
#O(N)?
i,j,k = 0,0,0
ans = 0
while j < N:
  while i < N and a[i]<b[j] :
    i += 1
  while k < N and c[k]<=b[j]:
    k += 1
  ans += i * (N - k)
  j += 1
 

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

def intlist(x):
    y = []
    for i in range(len(x)):
        y.append(int(x[i]))
    return y
N = int(input())
A = intlist(input().split())
M = 1

for i in range(N):
    M = M * A[i]
if M > 10**18:
    M = -1
        
print(M)

### FIXED CODE ###

def intlist(x):
    y = []
    for i in range(len(x)):
        y.append(int(x[i]))
    return y
N = int(input())
A = intlist(input().split())
M = 1

A.sort()
if A[0] == 0:
    M = 0
else:
    for i in range(N):
        M = M * A[i]
        if M > 10**18:
            M = -1
            break
print(M)
### BUGGY CODE ###

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

dist = []
for i in range(N-K+1):
    max_pos = 0
    min_neg = 0
    tmp = x[i:i+K]
    pos = []
    neg = []
    pos = [tmp[j] for j in range(K) if tmp[j] >= 0]
    neg = [tmp[j] for j in range(K) if tmp[j] < 0]
    if pos:
        max_pos = max(pos)
    if neg:
        min_neg = abs(min(neg))
    dist.append((max_pos + min_neg + min(max_pos, min_neg)))

print(min(dist))

### FIXED CODE ###

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

dist = []
for i in range(N-K+1): 
    l, r = x[i], x[i+K-1]
    t = min(abs(l)+abs(l-r), abs(r)+abs(r-l))
    dist.append(t)

print(min(dist))
### BUGGY CODE ###

from math import *
from collections import deque, defaultdict, Counter
from itertools import product, permutations, combinations, accumulate
from operator import itemgetter
from bisect import bisect_left, bisect_right, bisect
from heapq import heappush, heappop
from copy import copy, deepcopy

N = int(input())
xs = []
for i in range(N):
    x = input()
    xs.append(x)

us = "abcdefghijklmnopqrstuvwxyz"

cs = []
ess = []
for x in xs:
    c = Counter(x)
    es = [0,] * 26
    for i,u in enumerate(us):
        e = c[u]
        es[i] = e
    cs.append(c)
    ess.append(tuple(es))


g = Counter(ess)

re = 0
for k,v in g.items():
    re += v*(v-1)//2
print(re)

### FIXED CODE ###

from math import *
from collections import deque, defaultdict, Counter
from itertools import product, permutations, combinations, accumulate
from operator import itemgetter
from bisect import bisect_left, bisect_right, bisect
from heapq import heappush, heappop
from copy import copy, deepcopy

N = int(input())
xs = []
for i in range(N):
    x = input()
    xs.append(x)

us = "abcdefghijklmnopqrstuvwxyz"

cs = []
ess = []
for x in xs:
    c = Counter(x)
    es = [0,] * 26
    for i,u in enumerate(us):
        e = c[u]
        es[i] = e
    cs.append(c)
    ess.append(tuple(es))


g = Counter(ess)

re = 0
for k,v in g.items():
    re += v*(v-1)//2
print(re)
### BUGGY CODE ###

from collections import deque
n = int(input())
b = list(map(int, input().split()))
q = deque()
q.append([b[::], []])
ans = None
while q:
    now, history = q.popleft()
    if len(now) == 0:
        ans = history
        break
    for i, j in enumerate(now):
        if i+1 == j:
            q.append([now[:i] + now[i+1:], history + [i+1]])
if ans is None:
    print(-1)
else:
    for i in ans[::-1]:
        print(i)

### FIXED CODE ###

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

def check(b):
    for i in range(len(b))[::-1]:
        if i+1 == b[i]:
            return i
    return -1

ans = []
for i in range(n):
    ind = check(b)
    if ind >= 0:
        ans.append(ind+1)
        b = b[:ind] + b[ind+1:]
    else:
        print(-1)
        exit()
for i in ans[::-1]:
    print(i)
### BUGGY CODE ###

n,m=map(int,input().split())
w=[]
for i in range(n):
  w.append(list(map(int,input().split())))

w=sorted(w)
#print(w)

def solve():
  total=0
  for i in range(m,-1,-1):
#  print("i:"+str(i))
    max=0
    max_j=0
    found=False
    for j in range(len(w)):
      if (m-i)<w[j][0]: #残り日数(m-i)よりも大きい
#      print("残り日数:"+str(m-i) + "　仕事日数:"+str(w[j][0]))
        break
      elif max < w[j][1]:
#        print("最大値:"+str(w[j][1]) + " 添え字:"+str(j))
        max=w[j][1]
        max_j=j
        found=True
#  print(str(max) + "の仕事をやる")
    total = total + max
    if found:
#    print(str(max_j)+"番目の仕事を削除")
      w.pop(max_j)
#    print(w)
  return total
      
    
print(solve())

### FIXED CODE ###

n,m=map(int,input().split())
tasks=[None]*n
for i in range(n):
  a,b=map(int,input().split())
  tasks[i]=[a,b]

tasks=sorted(tasks,key=lambda x:x[0])
import heapq
que=[]
ans=0
heapq.heapify(que)
j=0
for i in range(m,-1,-1):
  left=m-i
  while j<len(tasks):
    if tasks[j][0]<=left:
      heapq.heappush(que, tasks[j][1]*(-1))
    else:
      break
    j+=1
  if len(que)>0:
    val=heapq.heappop(que)*(-1)
    ans+=val
      
print(ans)
### BUGGY CODE ###

import bisect

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

a2=[]
for i1 in range(N):
    a2.append(bisect.bisect_left(C,B[i1]+1))
ans=0
for i0 in range(N):
    a1 = bisect.bisect_left(B,A[i0]+1)
    for i1 in range(a1,N):
        ans += N - a2[i1]
print(ans)


### FIXED CODE ###

import bisect

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

a2=[]
for i1 in range(N):
    a2.append(bisect.bisect_left(C,B[i1]+1))

a2c=[0]*(N+1)
for i1 in range(N-1,-1,-1):
    a2c[i1] = a2c[i1+1] + N - a2[i1]

ans=0
for i0 in range(N):
    a1 = bisect.bisect_left(B,A[i0]+1)
    ans += a2c[a1]
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
@author: H_Hoshigi
"""
import math

#def main(N):
def main():
    N = int(input())
    # Nが1のときは答えは0
    if N == 1:
        return 0
    else:
        N_remein = N
        # Nを素因数分解する。
        p_list = []
        p_factor_list = []
        p = 2
        while N_remein >= 2:
        #for p in range(2, math.ceil(math.sqrt(N))+1):
            if N_remein%p == 0:
                counter = 0
                #p_pow_counter = 1
                while True:
                    #p_pow_counter *= p
                    if N_remein%p == 0:
                        N_remein = N_remein//p
                        counter+=1
                    else:
                        p_list.append(p)
                        p_factor_list.append(counter)
                        break
            if p > math.ceil(math.sqrt(N)) and N_remein == N:
                break
            p += 1
        #print(p_list)
        #print(p_factor_list)
        # Nが素数の場合は、答えは1。
        if not p_factor_list:
            return 1
        else:
            answer = 0
            # 各素因数の指数に対して、、
            # 1,2,3,...と正整数を順番に引いていき、
            # 引けた回数を合計する。
            for factor in p_factor_list:
                counter = 1
                while (counter*(counter+1))//2 <= factor:
                    counter += 1
                answer += (counter-1) 
            #return answer, p_list, p_factor_list
            return answer

if __name__ == "__main__":
    print(main())
    #for i in range(1, 100):
    #    print(i, main(i))



### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
@author: H_Hoshigi
"""
import math

#def main(N):
def main():
    N = int(input())
    # Nが1のときは答えは0
    if N == 1:
        return 0
    else:
        N_remein = N
        # Nを素因数分解する。
        p_list = []
        p_factor_list = []
        #p = 2
        #while N_remein >= 2:
        for p in range(2, math.ceil(math.sqrt(N))+1):
            if N_remein%p == 0:
                counter = 0
                #p_pow_counter = 1
                while True:
                    #p_pow_counter *= p
                    if N_remein%p == 0:
                        N_remein = N_remein//p
                        counter+=1
                    else:
                        p_list.append(p)
                        p_factor_list.append(counter)
                        break
        if N_remein != 1:
            p_list.append(N_remein)
            p_factor_list.append(1)
        #print(p_list)
        #print(p_factor_list)
        # Nが素数の場合は、答えは1。
        if not p_factor_list:
            return 1
        else:
            answer = 0
            # 各素因数の指数に対して、、
            # 1,2,3,...と正整数を順番に引いていき、
            # 引けた回数を合計する。
            for factor in p_factor_list:
                counter = 1
                while (counter*(counter+1))//2 <= factor:
                    counter += 1
                answer += (counter-1) 
            #return answer, p_list, p_factor_list
            return answer

if __name__ == "__main__":
    print(main())
    #for i in range(1, 100):
    #    print(i, main(i))
### BUGGY CODE ###

import math
def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]
n = int(input())
a = list(map(int, input().split()))
b = a[0]
for i in range(1, n): b = math.gcd(b, a[i])
if b != 1: print("not coprime")
else:
    data = primes(10**6)
    count = [0]*(len(data))
    for i in range(n):
        for j in range(len(data)):
            if a[i]%data[j] == 0: count[j] += 1
    x = 0
    for i in range(1, len(count)):
        x = max(x, count[i])
    print("setwise coprime") if x > 1 else print("pairwise coprime")

### FIXED CODE ###

from math import gcd, sqrt
def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]
n = int(input())
a = list(map(int, input().split()))
b = a[0]
for i in range(1, n): b = gcd(b, a[i])
if b != 1: print("not coprime")
else:
    data = primes(10**6)
    c = [1]*(10**6+1)
    for i in range(1, 10**6+1):
        for j in range(len(data)):
            if i < data[j]**2: break
            if i%data[j] == 0: c[i] = data[j]; break
        if c[i] == 1: c[i] = i
    d = [0]*(10**6+1)
    for i in range(n):
        while a[i] > 1:
            d[c[a[i]]] += 1
            e = c[a[i]]
            while a[i]%e == 0: a[i] //= e
    print("setwise coprime") if max(d[2:]) > 1 else print("pairwise coprime")
### BUGGY CODE ###

N, W = list(map(int, input().split()))
WV = []
for _ in range(N):
  WV.append(list(map(int, input().split())))

#dp = [[0] * (W+1+max([w for w,v in WV])) for _ in range(N+1)]
dp = [[0] * (W+1) for _ in range(N+1)]

for n in range(1, N+1):
  for w in range(1, W+1):
    if w >= WV[n-1][0]:
      dp[n][w] = max(dp[n-1][w-WV[n-1][0]] + WV[n-1][1], dp[n-1][w])
    else:
      dp[n][w] = dp[n-1][w]

print(max(dp[N]))

### FIXED CODE ###

import sys
input = sys.stdin.readline
 
import numpy as np
 
def main():
  n, W = map(int, input().split())
  dp = np.zeros(W+1, dtype=np.int64)
  for _ in range(n):
    w, v = map(int, input().split())
    # w, vを使うかどうかで更新する
    dp[w:W+1] = np.maximum(dp[:W-w+1]+v, dp[w:W+1])
  print(dp[W])

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

from sys import stdin

N = int(stdin.readline().rstrip())
A = [int(x) for x in stdin.readline().rstrip().split()]
res = 1
for i in range(N):
  res *= A[i]

if res > 10**18:
  res = -1


print(res)

### FIXED CODE ###

from sys import stdin

N = int(stdin.readline().rstrip())
A = [int(x) for x in stdin.readline().rstrip().split()]
A.sort()
res = 1
if 0 in A:
  res = 0
else:
  for i in range(N):
    res *= A[i]
    if res > 10**18:
      res = -1
      break

print(res)
### BUGGY CODE ###

s=str(input())
k=int(input())
ans=[]
for i in range(len(s)):
    for j in range(i+1,len(s)+1):
        ans.append(s[i:j])
#print(ans)
ans=sorted(list(set(ans)))
#print(ans)
print(ans[k-1])


### FIXED CODE ###

s=str(input())
k=int(input())
ans=[]
for i in range(len(s)):
    for j in range(i+1,i+k+1):
        ans.append(s[i:j])
#print(ans)
ans=sorted(list(set(ans)))
#print(ans)
print(ans[k-1])
### BUGGY CODE ###

n, m = map(int, input().split())
li = []
for i in range(m):
  li.append(list(input().split()))
a = []
b = 0
for j in range(m):
  if li[j][1] == "AC":
    a.append(int(li[j][0]))
  elif li[j][1] == "WA" and int(li[j][0]) not in a:
    b += 1
for k in range(m):
  if int(li[k][0]) not in a:
    b -= 1
print(len(set(a)), b)

### FIXED CODE ###

n, m = map(int, input().split())
li = []
for i in range(m):
  li.append(list(input().split()))
li_a = [0 for i in range(n)]
li_b = [0 for i in range(n)]
a = 0
b = 0
for j in range(m):
  if li[j][1] == "WA":
    li_b[int(li[j][0])-1] += 1
  elif li[j][1] == "AC" and li_a[int(li[j][0])-1] == 0:
    a += 1
    b += li_b[int(li[j][0])-1]
    li_a[int(li[j][0])-1] += 1
print(a, b)
### BUGGY CODE ###

from collections import defaultdict
inf = float('inf')

def solve(graph, n, start_node, end_node):
  if start_node == end_node:
    return 0

  costs = [inf for _ in range(n)]
  costs[start_node] = 0
  flgs = [False for _ in range(n)]

  while not all(flgs):
    prv_node = _get_min_idx(flgs,costs)
    flgs[prv_node] = True

    for node, dis in graph[prv_node]:
      if costs[node] > costs[prv_node] + dis:
        costs[node] = costs[prv_node] + dis
  return costs[end_node]
    
    
def _get_min_idx(flgs, costs):
    min_cost = inf
    min_idx = None
    cnt = 0
    for cost, flg in zip(costs, flgs):
      if min_cost > cost and flg is False:
        min_cost = cost
        min_idx = cnt
      cnt += 1
    return min_idx
        

n =int(input())
graph = defaultdict(list)

for _ in range(n-1):
  a,b,c = map(int, input().split())
  graph[a-1].append([b-1,c])
  graph[b-1].append([a-1,c])

q, k = map(int, input().split())
k -= 1
for _ in range(q):
  x, y = map(int, input().split())
  print( solve(graph, n, x-1, k) + solve(graph, n, k, y-1))

### FIXED CODE ###

from collections import defaultdict, deque
inf = float('inf')

def solve(graph, n, start_node, end_node):
  if start_node == end_node:
    return 0

  global costs_dict
  key = str(start_node) + '-' + str(end_node)
  if key in costs_dict:
    return costs_dict[key][end_node]

  costs = [inf for _ in range(n)]
  costs[start_node] = 0
  flgs = [False for _ in range(n)]

  while not all(flgs):
    prv_node = _get_min_idx(flgs,costs)
    flgs[prv_node] = True

    for node, dis in graph[prv_node]:
      if costs[node] > costs[prv_node] + dis:
        costs[node] = costs[prv_node] + dis
  costs_dict[key] = costs  
  return costs[end_node]
    
    
def _get_min_idx(flgs, costs):
    min_cost = inf
    min_idx = None
    cnt = 0
    for cost, flg in zip(costs, flgs):
      if min_cost > cost and flg is False:
        min_cost = cost
        min_idx = cnt
      cnt += 1
    return min_idx
        

n =int(input())
graph = defaultdict(list)
costs_dict = {}

for _ in range(n-1):
  a,b,c = map(int, input().split())
  graph[a-1].append([b-1,c])
  graph[b-1].append([a-1,c])

q, k = map(int, input().split())
k -= 1

l = [0 for _ in range(n)]
queue = deque()
queue.append(k)
while len(queue) > 0:
  a = queue.pop()
  for b, c in graph[a]:
    if l[b] == 0:
      l[b] = l[a] + c
      queue.append(b)

for _ in range(q):
  x, y = map(int, input().split())
  print( l[x-1] + l[y-1])
### BUGGY CODE ###

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

ans = 0
if P == 2 or P == 5:
  for i in range(N):
    if int(S[i])%P == 0:
      ans += i+1
else:
  r = [0] * (N+1)
  for i in range(N):
    r[N-1-i] = int(S[N-1-i:])%P
  # for i in range(N):
  #   for j in range(i,N):
  #     if (r[i]-r[j+1])%P == 0:
  #       ans += 1
  d = {}
  for x in r:
    if x in d:
      d[x] += 1
    else:
      d[x] = 1
  for k,v in d.items():
    ans += v*(v-1)//2
  
print(ans)

### FIXED CODE ###

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

  ans = 0
  if P == 2 or P == 5:
    for i in range(N):
      if int(S[i])%P == 0:
        ans += i+1
  else:
    # r = [0] * (N+1)
    # for i in range(N):
    #   r[N-1-i] = int(S[N-1-i:])%P
    # for i in range(N):
    #   for j in range(i,N):
    #     if (r[i]-r[j+1])%P == 0:
    #       ans += 1
    d = {}
    r = 0
    for i in range(N):
      r = (r+int(S[N-1-i])*pow(10,i,P))%P
      if r in d:
        d[r] += 1
      else:
        d[r] = 1
    if 0 in d:
      d[0] += 1
    for k,v in d.items():
      ans += v*(v-1)//2
  
  print(ans)

if __name__ == '__main__':
  main()