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

import sys

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

def main():
	N, K = IL()
	h_i = IL()
	dp = [sys.maxsize for _ in range(N)]
	dp[0] = 0
	for i in range(1, N):
		dp[i] = min([abs(h_i[i] - h_i[i-j]) + dp[i-j] for j in range(1, min(i, K)+1)])
		# for j in range(1, K+1):
		# 	if i+j < N:
		# 		dp[i+j] = min(dp[i+j], abs(h_i[i] - h_i[i+j]) + dp[i])
		
	print(int(dp[-1]))


if __name__ == "__main__":
	main()

### FIXED CODE ###

import sys
import numpy as np

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

def main():
	N, K = LI()
	h_i = np.array(LI())
	dp = np.full(N, 10**10, dtype=int)
	dp[0] = 0
	for i in range(1, N):
		dp[i:i+K] = np.fmin(dp[i:i+K], dp[i-1] + np.abs(h_i[i:i+K] - h_i[i-1]))
		
	return dp[-1]


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

#abc177_C_5_あまりの計算を挟むのは、その計算の対象になるときだけ
int_n = int(input())
list_tmp = list(map(int, input().split()))

int_sum = 0
int_divide = (10**9) + 7
 
for i in range(0, len(list_tmp) - 1):
  for j in range(i + 1, len(list_tmp)):
    if list_tmp[i] >= int_divide:
      list_tmp_i = list_tmp[i]%int_divide
    else:
      list_tmp_i = list_tmp[i]
      
    if list_tmp[j] >= int_divide:
      list_tmp_j = list_tmp[j]%int_divide
    else:
      list_tmp_j = list_tmp[j]    
    
    int_sum = int_sum + (list_tmp_i*list_tmp_j)
    
    if int_sum >= int_divide:
      int_sum = int_sum%int_divide
      
print(int_sum)
    


### FIXED CODE ###

#abc177_C_6_retry_累積和を使用する
int_n = int(input())
list_tmp = list(map(int, input().split()))
 
int_sum = 0
int_divide = (10**9) + 7
int_sum_tmp = sum(list_tmp)

for i in range(0, len(list_tmp) - 1):
  int_sum_tmp = int_sum_tmp - list_tmp[i]
  int_sum = int_sum + (int_sum_tmp * list_tmp[i])
print(int_sum % int_divide)
#  for j in range(i + 1, len(list_tmp)):
#    if list_tmp[i] >= int_divide:
#      list_tmp_i = list_tmp[i]%int_divide
#    else:
#      list_tmp_i = list_tmp[i]
#      
#    if list_tmp[j] >= int_divide:
#      list_tmp_j = list_tmp[j]%int_divide
#    else:
#      list_tmp_j = list_tmp[j]    
#    
#    int_sum = int_sum + (list_tmp_i*list_tmp_j)
#    
#    if int_sum >= int_divide:
#      int_sum = int_sum%int_divide
#      
#print(int_sum)
### BUGGY CODE ###

from bisect import bisect_left, bisect_right
from itertools import accumulate

def solve():
    N, K = map(int, input().split())
    As = list(map(int, input().split()))

    As.sort()
    i = bisect_left(As, K)
    Bs = As[:i]
    M = len(Bs)

    setSums = [{0}]
    setSum = {0}
    for B in Bs:
        for s in list(setSum):
            if s+B < K:
                setSum.add(s+B)
        setSums.append(setSum.copy())
    setSumRevs = [{0}]
    setSum = {0}
    for B in reversed(Bs):
        for s in list(setSum):
            if s+B < K:
                setSum.add(s+B)
        setSumRevs.append(setSum.copy())
    setSumRevs.reverse()

    def isOK(x):
        B = Bs[x]
        numRevs = [0] * K
        for s in setSumRevs[x+1]:
            numRevs[s] = 1
        accNumRevs = list(accumulate([0]+numRevs))
        for s in setSums[x]:
            if accNumRevs[K-s] - accNumRevs[max(0, K-s-B)] > 0:
                return True
        return False

    ng, ok = -1, M
    while abs(ok-ng) > 1:
        mid = (ng+ok) // 2
        if isOK(mid):
            ok = mid
        else:
            ng = mid

    print(ok)


solve()


### FIXED CODE ###

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

As.sort(reverse=True)

minAOK = As[0]+1
sumSubsets = set([0])
for A in As:
    if A >= K:
        minAOK = A
        continue
    for sumSubset in sumSubsets.copy():
        if K - A <= sumSubset:
            minAOK = A
        if sumSubset + A < K:
            sumSubsets.add(sumSubset + A)

ans = len([A for A in As if A < minAOK])
print(ans)
### BUGGY CODE ###

a = int(input())
num = 2
def is_prime(num):
    if num > 1:
        for i in range(2,num):
            if (num % i) == 0:
                return False
                break
        else:
            return True
    else:
        return False
while True:
    if is_prime(num):
        if num >= a:
            print(num)
            break
    num +=1


### FIXED CODE ###

def checkPrime(num):
    isPrime = True
    for i in range(2,(num//2)+1):
        if(num%i == 0):
            isPrime = False
            break
    return isPrime
def nextPrime(num):
    if(checkPrime(num)):
        return num
    n = num-1 if(num%2==0) else num
    while(True):
        n +=2
        if(checkPrime(n)):
            result = n
            break
    return result

num = int(input())
print(nextPrime(num))
### BUGGY CODE ###

from sys import stdin
import numpy as np
import math
from math import factorial
from itertools import combinations

n = int(stdin.readline().rstrip())
li = [stdin.readline().rstrip() for _ in range(n)]

lin = []

for i in range(n):
    if li[i][0] in "MARCH":
        lin.append(li[i][0])

liv = list(combinations(lin, 3))
point = 0
for i in liv:
    if i[0] != i[1] and i[0] != i[2] and i[2] != i[1]:
        point += 1
print(point)

### FIXED CODE ###

from sys import stdin
from itertools import combinations
from math import factorial

n = int(stdin.readline().rstrip())
li = [stdin.readline().rstrip() for _ in range(n)]

lin = [0]*5

for i in range(len(li)):
    if li[i][0] == "M":
        lin[0] += 1
    elif li[i][0] == "A":
        lin[1] += 1
    elif li[i][0] == "R":
        lin[2] += 1
    elif li[i][0] == "C":
        lin[3] += 1
    elif li[i][0] == "H":
        lin[4] += 1
        
lis = list(combinations(lin, 3))

point = 0
for i in lis:
    point += i[0]*i[1]*i[2]

print(point)
### BUGGY CODE ###

import sys
input=sys.stdin.readline
n=int(input())
BIT=[[0]*n for i in range(26)]
w=[ord(x)-ord("a") for x in input()]
for i in range(n):
	k=i+1
	while k<=n:
		BIT[w[i]][k-1]+=1
		k=k+(k&-k)
q=int(input())
for i in range(q):
	a,b,c=input().split()
	if a=="1":
		k=int(b)
		while k<=n:
			BIT[ord(c)-ord("a")][k-1]+=1
			k=k+(k&-k)
		k=int(b)
		while k<=n:
			BIT[w[int(b)-1]][k-1]-=1
			k=k+(k&-k)	
		w[int(b)-1]=ord(c)-ord("a")
	else:
		b=int(b);c=int(c)
		ans=0
		for i in range(26):
			cnt=0
			k=c
			while k!=0:
				cnt+=BIT[i][k-1]
				k=k-(k&-k)
			k=b-1
			while k!=0:
				cnt-=BIT[i][k-1]
				k=k-(k&-k)
			if cnt>0:
				ans+=1
		print(ans)

### FIXED CODE ###

import sys
input=sys.stdin.readline
n=int(input())
BIT=[[0]*n for i in range(26)]
w=[ord(x)-ord("a") for x in input()]
for i in range(n):
	k=i+1
	while k<=n:
		BIT[w[i]][k-1]+=1
		k=k+(k&-k)
q=int(input())
for i in range(q):
	a,b,c=input().split()
	if a=="1":
		k=int(b)
		while k<=n:
			BIT[ord(c)-ord("a")][k-1]+=1
			k=k+(k&-k)
		k=int(b)
		while k<=n:
			BIT[w[int(b)-1]][k-1]-=1
			k=k+(k&-k)	
		w[int(b)-1]=ord(c)-ord("a")
	else:
		b=int(b);c=int(c)
		ans=0
		for i in range(26):
			cnt=0
			k=c
			while k!=0:
				cnt+=BIT[i][k-1]
				k=k-(k&-k)
			k=b-1
			while k!=0:
				cnt-=BIT[i][k-1]
				k=k-(k&-k)
			if cnt>0:
				ans+=1
		print(ans)
### BUGGY CODE ###

import heapq
def SME(start,end):
    A = []
    if end > N : end = N
    count = 0
    for i,x in enumerate(Whole[start:end]):
        heapq.heappush(A,[x,i])
    for j in range(start,end):
        a = heapq.heappop(A)
        for i in range(L):
            idx = a[1] + i
            try :
                if ANS[idx] == 0:
                    ANS[idx] = a[0]
                    count += 1
            except IndexError : continue
        if count > N * 0.9999 - 1000 : break
    for i in range(L):
        if ANS[i] == 0 : ANS[i] = min(Whole[:i+1])
    for i in range(L,N):
        if ANS[i] == 0 : ANS[i] = min(Whole[i+1-L:i+1])
    return ANS

[N,L] = [int(x) for x in input().split()]
Whole = [int(x) for x in input().split()]
ANS = [0]*N
ANS = SME(0, N)
for i in ANS[L-1:-1]:print(i, end=" ")
print(ANS[-1])

### FIXED CODE ###

def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])
### BUGGY CODE ###

import math
n, k = map(int,input().split())
a = list(map(int, input().split()))

asum = sum(a)
gcdmax = int(math.sqrt(asum))
li = [i for i in range(2,gcdmax+1)]
for i in range(gcdmax,0,-1):
    if asum%i==0:
        li.append(asum//i)


ans = 1

for i in li:
    b = [a[ii] % i for ii in range(n)]
    b.sort()
#     print(i,b)
    l = 0
    r = 0
    x = 0
    y = n-1
    while x<=y:
        if r>=l:
            l += b[x]
            x += 1
        else:
            r += i - b[y]
            y -= 1
#         print(l,r)
    if max(l,r) <= k and (l-r)%i==0 :
        ans = i

print(ans)

### FIXED CODE ###

import math
n, k = map(int,input().split())
a = list(map(int, input().split()))

asum = sum(a)
gcdmax = int(math.sqrt(asum))
li = []
for i in range(2,gcdmax+1):
    if asum%i==0:
        li.append(i)
for i in range(gcdmax,0,-1):
    if asum%i==0:
        li.append(asum//i)


ans = 1
# print(li)

for i in li:
    b = [a[ii] % i for ii in range(n)]
    b.sort()
#     print(i,b)
    l = 0
    r = 0
    x = 0
    y = n-1
    while x<=y:
        if r>=l:
            l += b[x]
            x += 1
        else:
            r += i - b[y]
            y -= 1
#         print(l,r)
    if max(l,r) <= k and (l-r)%i==0 :
        ans = i

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

a, b = map(int, input().split())
nums = [x for x in reversed(range(2, min(a, b) + 1)) if a % x == b % x == 0]
res = 1
while nums:
    x = nums.pop()
    res += 1
    nums = [y for y in nums if y % x != 0]
print(res)

### FIXED CODE ###

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

def factorization(n):
    arr = set()
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp % i == 0:
            while temp % i == 0:
                temp //= i
            arr.add(i)

    if temp != 1:
        arr.add(temp)

    if not arr:
        arr.add(n)

    return arr

if a == b == 1:
    print(1)
else:
    fa = factorization(a)
    fb = factorization(b)
    res = 1
    for n in fa:
        if n in fb:
            res += 1
    print(res)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
N, K, Q = map(int, input().split())
score = []
for i in range(N):
    score.append(K)

for i in range(Q):
    answer = int(input()) - 1
    for idx in range(N):
        if idx == answer:
            continue
        score[idx] -= 1

for i in range(N):
    if score[i] <= 0:
        print("No")
    else:
        print("Yes")

### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
input = sys.stdin.readline

N, K, Q = map(int, input().split())
score = [0] * N

for i in range(Q):
    score[int(input()) -1 ] += +  1

for SCORE in score:
    if SCORE <= Q - K:
        print("No")
    else:
        print("Yes")
### BUGGY CODE ###

n = int(input())
A = [int(input()) for i in range(n)]

for i in range(n):
    ans = A[:]
    ans.pop(i)
    print(max(ans))


### FIXED CODE ###

n = int(input())
A = [int(input()) for i in range(n)]
B = A[:]
B.sort()

a_max = B[len(B)-1]
a_next = B[len(B)-2]

for i in range(n):
    if A[i] != a_max:
        print(a_max)
    else:
        print(a_next)
### BUGGY CODE ###

import itertools

n = int(input())
a = [int(s) for s in input().split(' ')]

def gcd(a, b):
    while b > 0:
        a, b = b, a % b
    return a

def ngcd(nums):
    d = 0
    for num in nums:
        d = gcd(d, num)
    return d

max = 1

for comb in itertools.combinations(a, n-1):
    ret = ngcd(comb)
    if ret > max:
        max = ret

print(max)


### FIXED CODE ###

import itertools
import fractions
from functools import reduce

n = int(input())
a = [int(s) for s in input().split(' ')]

L = [0] * n
R = [0] * n

for i in range(len(a)):
    if i == 0:
        L[i] = a[i]
        R[n - 1] = a[n - 1]
    else:
        L[i] = fractions.gcd(L[i - 1], a[i])
        R[n - 1 - i] = fractions.gcd(R[n - i], a[n - 1 - i])

val = 1

for i in range(len(a)):
    ret = 0
    if i == 0:
        ret = R[i + 1]
    elif i == n - 1:
        ret = L[i - 1]
    else:
        ret = fractions.gcd(L[i - 1], R[i + 1])

    if ret > val:
       val = ret
        
print(val)
### BUGGY CODE ###

import bisect
N = int(input())
A = [int(input()) for _ in range(N)]
tmp = [A[0]]
for i in range(1, N):
    index = bisect.bisect_left(tmp, A[i])
    if index == 0:
        tmp.insert(0, A[i])
    else:
        tmp[index-1] = A[i]

print(len(tmp))


### FIXED CODE ###

import bisect
N = int(input())
A = [-int(input()) for _ in range(N)]
tmp = [A[0]]
for i in A[1:N]:
    index = bisect.bisect(tmp, i)
    if index == len(tmp):
        tmp.append(i)
    else:
        tmp[index] = i

print(len(tmp))
### BUGGY CODE ###

# ABC 120 C

import re

S = input()

base = len(S)

l = len(S)

while True:
    tmp = l
    S = re.sub('01', '', S)
    if l != len(S):
        l = len(S)

    S = re.sub('10', '', S)
    if l != len(S):
        l = len(S)

    if tmp == l:
        break

print(base - len(S))


### FIXED CODE ###

# ABC 120 C

import re

S = input()

l0 = 0
l1 = 0

for i in range(len(S)):
    if S[i] == '0':
        l0 += 1
    elif S[i] == '1':
        l1 += 1

print(min(l0, l1) * 2)
### BUGGY CODE ###

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

hop_before = []
hop_to = []

for i in range(M) :
    a, b = map(int, input().split())
    
    if a == 1 :
        hop_to.append(b)
    if b == N :
        hop_before.append(a)
        
contains = False
for i in hop_to :
    if i in hop_before :
        contains = True
        break

if contains == True :
    print("POSSIBLE")
else :
    print("IMPOSSIBLE")

### FIXED CODE ###

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

hop_before = []
hop_to = []

hop_dict = {}

for i in range(M) :
    a, b = map(int, input().split())
    
    if a == 1 :
        if b in hop_dict.keys() :
            hop_dict[b] += 1
        else :
            hop_dict[b] = 1
    if b == N :
        if a in hop_dict.keys() :
            hop_dict[a] += 1
        else :
            hop_dict[a] = 1
        
possible = False
for i in hop_dict.keys() :
    if hop_dict[i] >= 2 :
        print("POSSIBLE")
        possible = True
        break
        
if possible == False :
    print("IMPOSSIBLE")
### BUGGY CODE ###

import sys
readline = sys.stdin.buffer.readline

N, M = map(int, readline().split())
ans = []
append_ans = ans.append
graph = [[] for _ in range(N+1)]

for _ in range(M):
    a, b = map(int, readline().split())
    graph[a].append(b)
    graph[b].append(a)

root = 1
q = [root]
append_q = q.append
checked = [0] * (N + 1)
checked[root] = 1
order = []
append_order = order.append
parent = [-1 for _ in range(N+1)]

while q:
    x = q.pop(0)
    for y in graph[x]:
        if checked[y]:
            continue
        if parent[y] != -1:
            continue
        parent[y] = x
        append_ans(x)
        append_order(y-2)
        checked[y] = 1
        append_q(y)

if len(order) != N - 1:
    print('No')
else:
    print('Yes')
    for i in range(len(order)):
        j = order.index(i)
        print(ans[j])

### FIXED CODE ###

import sys
readline = sys.stdin.buffer.readline
read = sys.stdin.buffer.read

N, M = map(int, readline().split())
m = map(int, read().split())
AB = list(zip(m, m))
graph = [[] for _ in range(N+1)]
for a, b in AB:
    graph[a].append(b)
    graph[b].append(a)

root = 1
q = [root]
checked = [0] * (N + 1)
checked[root] = 1
order = []
D = [0 for _ in range(N+1)]
d = 0
while q:
    x = q.pop(0)
    d = D[x]
    for y in graph[x]:
        if checked[y]:
            continue
        D[y] = d + 1
        checked[y] = 1
        q.append(y)

ans = [0 for _ in range(N+1)]
for a, b in AB:
    d_a, d_b = D[a], D[b]
    if d_a < d_b:
        ans[b] = a
    elif d_a > d_b:
        ans[a] = b

print('Yes')
print('\n'.join(map(str, ans[2:])))
### BUGGY CODE ###

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

AB = []
graph = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    AB.append((a, b))
    graph[a].append(b)
    graph[b].append(a)
AB = sorted(AB, key=lambda x: (x[1], x[0]))

root = 0
q = [root]
parent = [-1] * N
while q:
    x = q.pop(0)
    p = parent[x]
    for y in graph[x]:
        if y == p:
            continue
        parent[y] = x
        q.append(y)

C = [0] * N
for _ in range(Q):
    p, x = map(int, input().split())
    p = p - 1
    C[p] += x

for a, b in AB:
    if a != parent[b]:
        tmp = a
        a = b
        b = tmp
    C[b] += C[a]

print(*C)

### FIXED CODE ###

from queue import deque


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

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

C = [0] * N
for _ in range(Q):
    p, x = map(int, input().split())
    C[p - 1] += x

P = [-1] * N

root = 0
q = deque([root])
while q:
    x = q.popleft()
    for y in graph[x]:
        if y == P[x]:
            continue
        C[y] += C[x]
        q.append(y)
        P[y] = x

print(*C)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def main():
    N, M = map(int, input().split())
    ab = sorted([list(map(int, input().split())) for i in range(M)], key = lambda x:x[1])
    bridge = [True] * (N-1)
    count = 0
    start = -1
    for a, b in ab:
        a -= 1; b -= 1;
        if a > start:
            ok = True
            for i in range(a, b):
                if not bridge[i]:
                    ok = False
                    break
            if ok:
                start = a
                bridge[b-1] = False
                count += 1
    print(count)

if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    N, M = map(int, input().split())
    ab = sorted([list(map(int, input().split())) for i in range(M)], key = lambda x:x[1])
    count = 0
    break_ = -1
    for a, b in ab:
        a -= 1; b -= 1;
        if a > break_:
            count += 1
            break_ = b-1
    print(count)

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

N = int(input())
P = list(map(int, input().split(' ')))

num = 0
for i in range(N):
  if all([P[i] <= P[j] for j in range(i)]):
    num += 1
      
print(num)

### FIXED CODE ###

N = int(input())
P = list(map(int, input().split(' ')))

min = N
num = 1
for i in range(1, N):
  if min > P[i - 1]:
    min = P[i - 1]
  if P[i] <= min:
    num += 1
    
print(num)
### BUGGY CODE ###

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

MOD = 10**9 + 7

from functools import reduce
from fractions import gcd
def lcm(x,y):return x*y//gcd(x,y)
def lcmm(l):return reduce(lcm,l)

x = lcmm(A)

ans = 0
for a in A:
    ans += x//a
ans %= MOD

print(ans)


### FIXED CODE ###

from functools import reduce
from fractions import gcd

N = int(input())
A = list(map(int, input().split()))
 
MOD = 10 ** 9 + 7
 
lcm = reduce(lambda x,y: x*(y//gcd(x,y)), A)
lcm %= MOD

coef = sum(pow(a, MOD-2, MOD) for a in A)
ans = lcm * coef % MOD

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

N = int(input())
A = list(map(int,input().split()))
P = 0
A_l = [num% (10**9+7) for num in A]

for i in range(N):
  for j in range(i+1,N):
    p = A_l[i]*A_l[j]
    P += p
    
sum = P%(10**9+7)
print(sum)


### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
P = 0
S = sum(A)
m = 10**9+7

for i in range(N):
  S -= A[i]
  P += A[i]*S
  
ans = P%m
print(ans)
### BUGGY CODE ###

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

lis_A = []
lis_K = [lis_NKQ[1] for i in range(lis_NKQ[0])]

for i in range(lis_NKQ[2]):
    lis_A.append(int(input()))

for i in range(lis_NKQ[2]):
    lis_K = list(map(lambda x: x - 1,lis_K))

for i in lis_A:
    lis_K[i - 1] += 1

for i in lis_K:
    if i > 0:
        print("Yes")
    else:
        print("No")


### FIXED CODE ###

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

lis_A = []
lis_K = [lis_NKQ[1] for i in range(lis_NKQ[0])]
lis_K = list(map(lambda x: x - lis_NKQ[2],lis_K))

for i in range(lis_NKQ[2]):
    inp = int(input())
    lis_A.append(inp)
    lis_K[inp - 1] += 1  

for i in lis_K:
    if i > 0:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

from bisect import bisect_left

N,P = LI()
S = list(map(int,list(str(input()))))

ans = 0
if P == 2:
    for i in range(N):
        if S[i]%2 == 0:
            ans += i+1
elif P == 5:
    for i in range(N):
        if S[i]%5 == 0:
            ans += i+1
else:
    M = [0]*(N+1)
    now = 0
    for i in range(N):
        now += 10**i*S[N-1-i]
        now %= P
        M[N-1-i] = now
    d = defaultdict(list)
    for i in range(N+1):
        d[M[i]].append(i)
    for i in range(N):
        p = bisect_left(d[M[i+1]],i+1)
        ans += p

print(ans)

### FIXED CODE ###

import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

from bisect import bisect_left

N,P = LI()
S = list(map(int,list(str(input()))))

ans = 0
if P == 2:
    for i in range(N):
        if S[i]%2 == 0:
            ans += i+1
elif P == 5:
    for i in range(N):
        if S[i]%5 == 0:
            ans += i+1
else:
    M = [0]*(N+1)
    now = 0
    for i in range(N):
        now += pow(10,i,P)*S[N-1-i]
        now %= P
        M[N-1-i] = now
    d = defaultdict(list)
    for i in range(N+1):
        d[M[i]].append(i)
    for i in range(N):
        p = bisect_left(d[M[i+1]],i+1)
        ans += p

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

a=int(input())
i=100/a
f=0
while i<1:
  i=int(i*1.01)
  f=f+1
print(f)


### FIXED CODE ###

a=int(input())
i=100
f=0
while i<a:
  i=i+i//100
  f=f+1
print(f)
### BUGGY CODE ###

def solve():
    MOD = 10 ** 9 + 7
    N, M = map(int, input().split())
    A = set(map(int, input().split()))
    B = set(map(int, input().split()))
    
    row, columun = 0, 0
    ans = 1
    for i in range(N * M, 0, -1):
        in_A = i in A
        in_B = i in B
        if in_A and in_B:
            row += 1
            columun += 1
        elif in_A:
            row += 1
            ans *= columun
        elif in_B:
            columun += 1
            ans *= row
        else:
            ans *= row * columun - (N * M - i)
    print(ans % MOD)


if __name__ == '__main__':
    solve()


### FIXED CODE ###

def solve():
    MOD = 10 ** 9 + 7
    N, M = map(int, input().split())
    A = set(map(int, input().split()))
    B = set(map(int, input().split()))
    
    row, columun = 0, 0
    ans = 1
    for i in range(N * M, 0, -1):
        in_A = i in A
        in_B = i in B
        if in_A and in_B:
            row += 1
            columun += 1
        elif in_A:
            row += 1
            ans *= columun
        elif in_B:
            columun += 1
            ans *= row
        else:
            ans *= row * columun - (N * M - i)
        ans %= MOD
    print(ans)


if __name__ == '__main__':
    solve()