AtCoder Beginner Contest 158 - Divisible Substring

Takahashi has a string S of length N consisting of digits from 0 through 9.
He loves the prime number P. He wants to know how many non-empty (contiguous) substrings of S - there are N \times (N + 1) / 2 of them - are divisible by P when regarded as integers written in base ten.
Here substrings starting with a 0 also count, and substrings originated from different positions in S are distinguished, even if they are equal as strings or integers.
Compute this count to help Takahashi.

-----Constraints-----
 - 1 \leq N \leq 2 \times 10^5
 - S consists of digits.
 - |S| = N
 - 2 \leq P \leq 10000
 - P is a prime number.

-----Input-----
Input is given from Standard Input in the following format:
N P
S

-----Output-----
Print the number of non-empty (contiguous) substrings of S that are divisible by P when regarded as an integer written in base ten.

-----Sample Input-----
4 3
3543

-----Sample Output-----
6

Here S = 3543. There are ten non-empty (contiguous) substrings of S:
 - 3: divisible by 3.
 - 35: not divisible by 3.
 - 354: divisible by 3.
 - 3543: divisible by 3.
 - 5: not divisible by 3.
 - 54: divisible by 3.
 - 543: divisible by 3.
 - 4: not divisible by 3.
 - 43: not divisible by 3.
 - 3: divisible by 3.
Six of these are divisible by 3, so print 6.

Difficulty: MEDIUM

Starter code:

Solutions:
p = int(input().split()[1])
a = list(map(int, input()))
if 10 % p == 0:
	r = sum((i for (i, x) in enumerate(a, 1) if x % p == 0))
else:
	d = [1] + [0] * (p - 1)
	(s, y) = (0, 1)
	for x in reversed(a):
		s = (s + x * y) % p
		d[s] += 1
		y = y * 10 % p
	r = sum((i * (i - 1) // 2 for i in d))
print(r)


(n, p) = map(int, input().split())
s = input()
total = [0] * p
total[0] = 1
t = [0] * (n + 1)
if p == 2 or p == 5:
	ans = 0
	for i in range(n):
		if int(s[i]) % p == 0:
			ans += i + 1
	print(ans)
else:
	for i in range(n - 1, -1, -1):
		t[i] = t[i + 1] % p + int(s[i]) * pow(10, n - 1 - i, p)
		total[t[i] % p] += 1
	ans = 0
	for i in range(p):
		ans += total[i] * (total[i] - 1) // 2
	print(ans)


(n, p) = map(int, input().split())
s = list(input())
if p == 2 or p == 5:
	ans = 0
	for (i, ss) in enumerate(s):
		if int(ss) % p == 0:
			ans += i + 1
	print(ans)
	exit(0)
from collections import Counter
c = Counter()
m = 0
c[m] += 1
d = 1
s = s[::-1]
for i in range(n):
	m += int(s[i]) * d
	m %= p
	d *= 10
	d %= p
	c[m] += 1
ans = 0
for v in c.values():
	ans += v * (v - 1) // 2
print(ans)


from collections import defaultdict
(N, P) = list(map(int, input().split()))
S = input().strip()[::-1]
if P in [2, 5]:
	ans = 0
	for r in range(N):
		if int(S[r]) % P == 0:
			ans += N - r
	print(ans)
	return
cum = [0] * (N + 1)
for i in range(N):
	now = int(S[i]) * pow(10, i, P)
	cum[i + 1] = (cum[i] + now) % P
cnt = defaultdict(int)
for _cum in cum:
	cnt[_cum] += 1
ans = 0
for (k, v) in list(cnt.items()):
	ans += v * (v - 1) // 2
print(ans)


from collections import Counter

def mpow(a, b, mod):
	ret = 1
	while b > 0:
		if b & 1:
			ret = ret * a % mod
		a = a * a % mod
		b >>= 1
	return ret
(n, p) = map(int, input().split())
s = [int(i) for i in input()]
if p == 2 or p == 5:
	ans = 0
	for i in range(n):
		if s[i] % p == 0:
			ans += i + 1
	print(ans)
else:
	ans = 0
	d = Counter()
	d[0] += 1
	num = 0
	for i in range(n - 1, -1, -1):
		num = (num + s[i] * mpow(10, n - 1 - i, p)) % p
		ans += d[num]
		d[num] += 1
	print(ans)


(n, p) = map(int, input().split())
s = list(map(int, list(input())))
cnt = [0] * p
cnt[0] = 1
rem = 0
sum = 0
if p == 2 or p == 5:
	for i in range(n):
		if s[i] % p == 0:
			sum += i + 1
else:
	for i in range(n):
		rem = (int(s[-i - 1]) * pow(10, i, p) + rem) % p
		sum += cnt[rem]
		cnt[rem] += 1
print(sum)


from collections import Counter
(n, p) = map(int, input().split())
s = input()
ans = 0
if p == 2 or p == 5:
	for (i, j) in enumerate(s):
		if int(j) % p == 0:
			ans += i + 1
else:
	(num, point) = (0, 1)
	A = [0]
	for i in s[::-1]:
		num += int(i) * point
		num %= p
		A.append(num)
		point *= 10
		point %= p
	A = Counter(A)
	for (i, j) in A.items():
		if j >= 2:
			ans += j * (j - 1) // 2
print(ans)


(N, P) = map(int, input().split())
S = input()
if P == 2 or P == 5:
	ans = 0
	for i in range(N):
		if int(S[i]) % P == 0:
			ans += i + 1
	print(ans)
else:
	mod_cnt = [0] * P
	mod_cnt[0] = 1
	k = 0.1
	t = 0
	for i in range(1, N + 1):
		k = int(k * 10) % P
		t = (t + k * int(S[-i])) % P
		mod_cnt[t] += 1
	ans = 0
	for cnt in mod_cnt:
		ans += cnt * (cnt - 1) // 2
	print(ans)


from collections import defaultdict
(N, P) = map(int, input().split())
S = input()
if P == 2 or P == 5:
	ans = 0
	for i in range(N):
		if int(S[i]) % P == 0:
			ans += i + 1
	print(ans)
else:
	d = defaultdict(int)
	a = 0
	for i in range(N):
		a += int(S[N - i - 1]) * pow(10, i, P)
		a %= P
		d[a] += 1
	ans = d[0]
	for v in d.values():
		ans += v * (v - 1) // 2
	print(ans)


from collections import defaultdict
(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:
	tmp = 0
	d = defaultdict(int)
	d[0] = 1
	for i in range(n)[::-1]:
		tmp += int(s[i]) * pow(10, n - i - 1, p)
		tmp %= p
		ans += d[tmp]
		d[tmp] += 1
print(ans)


(n, p) = map(int, input().split())
ans = 0
s = input()
if p == 2 or p == 5:
	for i in range(len(s)):
		n = int(s[i])
		if n % p == 0:
			ans += i + 1
	print(ans)
	exit()
r = [0] * p
r[0] = 1
t = 1
z = 0
for i in reversed(s):
	z = int(i) * t + z
	t *= 10
	t %= p
	z %= p
	r[z] += 1
ans = sum((i * (i - 1) // 2 for i in r))
print(ans)


def main():
	(N, P) = map(int, input().split())
	S = [int(s) for s in list(input().strip())][::-1]
	num = 0
	ans = 0
	if P == 2 or P == 5:
		for i in range(N):
			if S[i] % P == 0:
				ans += N - i
		print(ans)
		return
	L = [0] * P
	L[0] = 1
	t = 0
	s = 1
	for z in S:
		t = (z * s + t) % P
		L[t] += 1
		s = s * 10 % P
	for l in L:
		ans += l * (l - 1) // 2
	print(ans)
main()


(N, P) = map(int, input().split(' '))
S = list(map(int, list(input()[::-1])))
ans = 0
cnt = [0] * P
cnt[0] = 1
tmp = 0
for (n, i) in enumerate(S):
	d = i * pow(10, n, P)
	tmp = (tmp + d) % P
	cnt[tmp] += 1
if P in [2, 5]:
	if P == 2:
		check = [0, 2, 4, 6, 8]
	else:
		check = [0, 5]
	for (n, i) in enumerate(S):
		if i in check:
			ans += N - n
else:
	for i in cnt:
		ans += i * (i - 1) // 2
print(ans)


(n, p) = map(int, input().split())
s = input()
if 10 % p == 0:
	ans = sum((i + 1 for (i, x) in enumerate(s) if int(x) % p == 0))
	print(ans)
else:
	counter = [0] * p
	counter[0] = 1
	cur = 0
	p10 = 1
	ans = 0
	for x in s[::-1]:
		cur = (cur + int(x) * p10) % p
		ans += counter[cur]
		counter[cur] += 1
		p10 *= 10
		p10 %= p
	print(ans)


(n, m) = map(int, input().split())
s = input()
l = [0] * m
(a, t, p) = (0, 0, 1)
if 10 % m:
	for i in s[::-1]:
		l[t % m] += 1
		t += int(i) * p
		a += l[t % m]
		p = p * 10 % m
else:
	a = sum((i + 1 for i in range(n) if int(s[i]) % m < 1))
print(a)


from collections import Counter
(N, MOD) = map(int, input().split())
S = input()
res = 0
if MOD == 2 or MOD == 5:
	for i in range(N):
		if int(S[N - i - 1]) % MOD == 0:
			res += N - i
else:
	Cum = [0] * (N + 1)
	for i in range(N):
		Cum[i + 1] = (Cum[i] + int(S[N - i - 1]) * pow(10, i, MOD)) % MOD
	c = Counter(Cum).most_common()
	for (a, b) in c:
		res += b * (b - 1) // 2
print(res)


(N, P) = map(int, input().split())
(S, a, i, j, c) = (input(), 0, 0, 1, [1] + [0] * P)
if 10 % P:
	for v in S[::-1]:
		(i, j) = ((i + int(v) * j) % P, j * 10 % P)
		a += c[i]
		c[i] += 1
else:
	for v in S:
		i += 1
		if int(v) % P < 1:
			a += i
print(a)


def main():
	(n, p) = map(int, input().split())
	s = input()
	if 10 % p == 0:
		print(sum((i for (i, x) in enumerate(s, 1) if int(x) % p == 0)))
		exit()
	s = s[::-1]
	x = [0] * p
	x[0] = 1
	(a, t) = (0, 1)
	for i in range(n):
		a = (a + int(s[i]) * t) % p
		x[a] += 1
		t = t * 10 % p
	ans = sum([i * (i - 1) // 2 for i in x])
	print(ans)
main()


(n, p) = list(map(int, input().split()))
s = list(map(int, list(input())))[::-1]
sum = 0
cnt = [0] * p
cnt[0] = 1
n = len(s)
for i in range(n):
	d = s[i] * pow(10, i, p)
	sum = (sum + d) % p
	cnt[sum] += 1
ans = 0
if p in [2, 5]:
	if p == 2:
		ok_list = [0, 2, 4, 6, 8]
	if p == 5:
		ok_list = [0, 5]
	for i in range(n):
		d = s[i]
		if d in ok_list:
			ans += n - i
else:
	for i in range(p):
		ans += cnt[i] * (cnt[i] - 1) // 2
print(ans)


(N, P) = map(int, input().split())
S = input()
ans = 0
if P == 2 or P == 5:
	for (i, s) in enumerate(S):
		if int(s) % P == 0:
			ans += i + 1
else:
	counts = [0] * P
	h = 0
	d = 1
	for s in reversed(S):
		m = int(s) * d % P
		h = (h + m) % P
		counts[h] += 1
		d = d * 10 % P
		ans = counts[0]
	for i in counts:
		ans += i * (i - 1) // 2
print(ans)


(n, p) = map(int, input().split())
D = input()
out = 0
if 10 % p == 0:
	for i in range(n):
		if int(D[i]) % p == 0:
			out += i + 1
else:
	mod = 0
	count = [0] * p
	ten = 1
	count[mod] += 1
	for i in range(n):
		mod = (mod + int(D[n - i - 1]) * ten) % p
		ten = ten * 10 % p
		count[mod] += 1
	for c in count:
		out += c * (c - 1) // 2
print(out)


(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
	print(ans)
	exit()
modP = [0 for _ in range(P)]
modP[0] = 1
now = 0
t = 1
for i in range(N):
	now += int(S[-1 - i]) * t
	now %= P
	modP[now] += 1
	t = t * 10 % P
for r in modP:
	ans += r * (r - 1) // 2
print(ans)


def main():
	(N, P) = list(map(int, input().split()))
	(*s,) = list(map(int, input()))
	if P in {2, 5}:
		ans = 0
		for (i, x) in enumerate(reversed(s), start=0):
			if x % P == 0:
				ans += N - i
		print(ans)
		return
	ans = 0
	total = 0
	coef = 1
	ctr = [0] * P
	ctr[0] = 1
	for x in reversed(s):
		total = (total + x * coef) % P
		coef = coef * 10 % P
		ans += ctr[total]
		ctr[total] += 1
	print(ans)

def __starting_point():
	main()
__starting_point()


(N, P) = map(int, input().split())
S = input()
ans = 0
if P in (2, 5):
	for (i, s) in enumerate(S):
		if int(s) % P == 0:
			ans += i + 1
else:
	count = [0] * P
	count[0] = 1
	u = 0
	for (i, s) in enumerate(reversed(S)):
		u = (int(s) * pow(10, i, P) + u) % P
		ans += count[u]
		count[u] += 1
print(ans)


(n, p) = map(int, input().split())
s = list(map(int, list(input())))
if p == 2 or p == 5:
	ans = 0
	for i in range(n):
		if s[i] % p == 0:
			ans += i + 1
	print(ans)
else:
	lis = [0] * p
	cnt = 0
	kurai = 1
	for i in s[::-1]:
		cnt += i * kurai % p
		cnt %= p
		lis[cnt] += 1
		kurai *= 10
		kurai %= p
	ans = 0
	for i in lis:
		ans += i * (i - 1) // 2
	ans += lis[0]
	print(ans)


from math import gcd
from collections import defaultdict
(N, P) = map(int, input().split())
S = list(map(int, input()))
answer = 0
if P == 2 or P == 5:
	for j in range(N - 1, -1, -1):
		if S[j] % P == 0:
			answer += j + 1
else:
	cnts = defaultdict(int)
	suffix = 0
	base = 1
	for i in range(N - 1, -1, -1):
		suffix = (suffix + S[i] * base) % P
		answer += cnts[suffix]
		answer += 1 if suffix == 0 else 0
		cnts[suffix] += 1
		base = base * 10 % P
print(answer)


def main():
	(N, P) = list(map(int, input().split()))
	s = list(input())[::-1]
	ary_mod = [0] * P
	ary_mod[0] = 1
	now = 0
	digit = 1
	ans = 0
	if P == 2:
		for (i, ss) in enumerate(s):
			if int(ss) % 2 == 0:
				ans += N - i
		print(ans)
		return
	if P == 5:
		for (i, ss) in enumerate(s):
			if int(ss) % 5 == 0:
				ans += N - i
		print(ans)
		return
	for (i, ss) in enumerate(s):
		now += int(ss) * digit % P
		digit *= 10
		digit %= P
		remind = now % P
		ary_mod[remind] += 1
	ans = 0
	for (i, n) in enumerate(ary_mod):
		ans += n * (n - 1) // 2
	print(ans)

def __starting_point():
	main()
__starting_point()


(n, p) = map(int, input().split())
s = input()

def solve():
	if p in [2, 5]:
		ret = 0
		for i in range(n):
			if int(s[n - 1 - i]) % p == 0:
				ret += n - i
		return ret
	val = [0] * p
	ten = 1
	cur = 0
	val[cur] += 1
	for i in range(n):
		cur = (cur + int(s[n - 1 - i]) * ten) % p
		ten = ten * 10 % p
		val[cur] += 1
	ret = 0
	for i in range(p):
		ret += val[i] * (val[i] - 1) // 2
	return ret
print(solve())


(N, P) = map(int, input().split())
S = str(input())
L = len(S)
ans = 0
dic = {0: 1}
now = 0
if P == 2 or P == 5:
	kotae = 0
	for i in range(L):
		if int(S[L - 1 - i]) % P == 0:
			kotae += L - i
	print(kotae)
	return
else:
	for i in range(L):
		now += int(S[L - 1 - i]) * pow(10, i, P)
		temp = now % P
		if temp not in dic:
			dic[temp] = 1
		else:
			dic[temp] += 1
ans = 0
for i in dic.values():
	if i != 1:
		ans += i * (i - 1) // 2
print(ans)


(N, P) = map(int, input().split())
S = input()
ans = 0
if P in (2, 5):
	for (i, s) in enumerate(S):
		if int(s) % P == 0:
			ans += i + 1
else:
	cnt = [0 for _ in range(P)]
	CS = 0
	PLC = 1
	for s in S[::-1]:
		tmp = int(s) * PLC % P
		CS = (CS + tmp) % P
		cnt[CS] += 1
		PLC = PLC * 10 % P
	for c in cnt:
		ans += c * (c - 1) // 2
	ans += cnt[0]
print(ans)


(N, P) = map(int, input().split())
S = input()
ans = 0
if P in [2, 5]:
	for (l, s) in enumerate(S, 1):
		if int(s) % P == 0:
			ans += l
else:
	counter = [0] * P
	counter[0] = 1
	prev = 0
	temp = 1
	for (i, s) in reversed(list(enumerate(S))):
		num = (int(s) * temp + prev) % P
		ans += counter[num]
		counter[num] += 1
		prev = num
		temp = temp * 10 % P
print(ans)


import sys
import numpy as np
input = sys.stdin.readline

def ST():
	return input().rstrip()

def I():
	return int(input())

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

def LI():
	return list(MI())
(N, P) = MI()
S = ST()
ans = 0
if P == 2:
	for (i, s) in enumerate(S, 1):
		if int(s) % 2 == 0:
			ans += i
elif P == 5:
	for (i, s) in enumerate(S, 1):
		if int(s) % 5 == 0:
			ans += i
else:
	cnt = np.zeros(P)
	cnt[0] = 1
	res = 0
	tmp = 1
	for s in S[::-1]:
		res += int(s) * tmp
		res %= P
		cnt[res] += 1
		tmp *= 10
		tmp %= P
	for c in cnt[cnt >= 2]:
		ans += c * (c - 1) // 2
print(int(ans))


3
import sys
from collections import Counter
input = lambda : sys.stdin.readline().strip()
(n, p) = [int(x) for x in input().split()]
s = input()
ans = 0
if p == 2 or p == 5:
	allowed_digits = '24680' if p == 2 else '50'
	for (i, c) in enumerate(s, start=1):
		if c in allowed_digits:
			ans += i
else:

	def minv(x, p):
		return pow(x, p - 2, p)
	count = Counter({0: 1})
	(x, delta) = (0, 1)
	for c in s:
		x = (x * 10 + ord(c) - ord('0')) % p
		y = x * minv(delta, p) % p
		ans += count[y]
		count[y] += 1
		delta = delta * 10 % p
print(ans)


from collections import Counter
(N, P) = map(int, input().split())
S = input()
if 10 % P == 0:
	ans = 0
	for (i, s) in enumerate(S, start=1):
		if int(s) % P != 0:
			continue
		ans += i
	print(ans)
else:
	X = [0]
	for (i, s) in enumerate(S[::-1]):
		X.append((X[-1] + pow(10, i, P) * int(s)) % P)
	C = Counter(X)
	ans = 0
	for v in C.values():
		ans += v * (v - 1) // 2
	print(ans)


def main():
	(n, p) = map(int, input().split())
	s = input()
	num = 0
	s1 = [0] * (n + 1)
	ans = 0
	if p == 2 or p == 5:
		for i in range(len(s)):
			if int(s[i]) % p == 0:
				ans += i + 1
		print(ans)
		exit()
	ans = 0
	arr = [0] * p
	s = s[::-1]
	z = 1
	for i in range(n):
		s1[i + 1] = s1[i] + int(s[i]) * z
		z = z * 10 % p
		s1[i + 1] %= p
		arr[s1[i]] += 1
	arr[s1[n]] += 1
	for i in range(p):
		ans += arr[i] * (arr[i] - 1) // 2
	print(ans)
main()


import sys
IS = lambda : sys.stdin.readline().rstrip()
II = lambda : int(IS())
MII = lambda : list(map(int, IS().split()))
MIIZ = lambda : list(map(lambda x: x - 1, MII()))
INIT_VAL = 0
MD2 = lambda d1, d2: [[INIT_VAL] * d2 for _ in range(d1)]
MD3 = lambda d1, d2, d3: [MD2(d2, d3) for _ in range(d1)]
DIVC = lambda x, y: -(-x // y)
DIVF = lambda x, y: x // y

def main():
	(n, p) = MII()
	s = list(map(int, IS()))
	if 10 % p == 0:
		cnt = 0
		for (i, si) in enumerate(s):
			if si % p == 0:
				cnt += i + 1
		print(cnt)
		return None
	d = [0] * p
	d[0] = 1
	ss = 0
	x = 1
	for si in s[::-1]:
		ss += x * si
		ss %= p
		d[ss] += 1
		x = 10 * x % p
	cnt = 0
	for di in d:
		cnt += di * (di - 1) // 2
	print(cnt)

def __starting_point():
	main()
__starting_point()


from collections import defaultdict
(N, P) = map(int, input().split())
S = input()
ans = 0
if P in [2, 5]:
	for i in range(N):
		if int(S[i]) % P == 0:
			ans += i + 1
else:
	mod_P = defaultdict(int)
	mod_P[0] += 1
	tmp = 0
	for i in range(N):
		tmp = int(S[N - 1 - i]) * pow(10, i, P) + tmp
		tmp %= P
		ans += mod_P[tmp]
		mod_P[tmp] += 1
print(ans)


(N, P) = map(int, input().split())
S = input()
if P in (2, 5):
	ans = 0
	for (i, c) in enumerate(S):
		if int(c) % P == 0:
			ans += i + 1
	print(ans)
	return
mem = [0]
j = 1
for c in S[::-1]:
	mem.append((mem[-1] + int(c) * j) % P)
	j *= 10
	j %= P
from collections import Counter
ctr = Counter(mem)
ans = 0
for v in ctr.values():
	ans += v * (v - 1) // 2
print(ans)


(N, P) = list(map(int, input().split()))
S = input()
now = 0
hyou = [0] * P
hyou[0] = 1
cnt = 1
ans = 0
if P == 2 or P == 5:
	for (i, t) in enumerate(S[::-1]):
		temp = int(t)
		if temp % P == 0:
			ans += N - i
	print(ans)
	return
for (i, t) in enumerate(S[::-1]):
	now = (now + int(t) * pow(10, i, P)) % P
	ans += hyou[now]
	hyou[now] += 1
print(ans)


(n, p) = map(int, input().split())
s = input().rstrip()
ans = 0
l = [0] * p
a = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
c = 0
if p == 2 or p == 5:
	for i in range(n):
		if int(s[i]) % p == 0:
			ans += i + 1
else:
	for i in range(n):
		mod = (c + a[int(s[-(i + 1)])]) % p
		ans += l[mod]
		l[mod] += 1
		if mod == 0:
			ans += 1
		c = mod
		for j in range(10):
			a[j] = a[j] * 10 % p
print(ans)


(n, p) = map(int, input().split())
s = input()
sum_cnt = 0
if p in {2, 5}:
	for r in range(n):
		if int(s[r]) % p == 0:
			sum_cnt += r + 1
else:
	modp_cnt = [0] * p
	modp_cnt[0] = 1
	(subs_modp, pow) = (0, 1)
	for si in s[::-1]:
		subs_modp += int(si) * pow % p
		subs_modp %= p
		modp_cnt[subs_modp] += 1
		pow = pow * 10 % p
	for cnt in modp_cnt:
		sum_cnt += cnt * (cnt - 1) // 2
print(sum_cnt)


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

def ma25():
	ret = 0
	for i in range(N):
		if S[i] % P == 0:
			ret += i + 1
	print(ret)

def ma():
	dp = [0] * P
	dp[0] = 1
	r = 0
	for i in range(N - 1, -1, -1):
		r = (S[i] * pow(10, N - 1 - i, P) + r) % P
		dp[r] += 1
	ret = 0
	for m in dp:
		ret += m * (m - 1) // 2
	print(ret)
if P == 2 or P == 5:
	ma25()
else:
	ma()


(n, p) = map(int, input().split())
s = input()[::-1]
A = [0] * n
A[0] = int(s[0]) % p
t = 10
for i in range(1, n):
	A[i] = (int(s[i]) * t + A[i - 1]) % p
	t = t * 10 % p
ans = 0
import collections
D = collections.defaultdict(int)
D[0] = 1
if p != 2 and p != 5:
	for i in range(n):
		ans += D[A[i]]
		D[A[i]] += 1
	print(ans)
else:
	s = s[::-1]
	ans = 0
	for i in range(n):
		if int(s[i]) % p == 0:
			ans += i + 1
	print(ans)


I = lambda s: map(int, s)
p = int(input().split()[1])
s = input()
if 10 % p == 0:
	r = sum((i for (i, x) in enumerate(I(s), 1) if x % p == 0))
else:
	d = {0: 1}
	(t, y) = (0, 1)
	for (i, x) in enumerate(I(reversed(s)), 1):
		t = (t + x * y) % p
		d[t] = d.get(t, 0) + 1
		y = y * 10 % p
	r = sum((i * (i - 1) // 2 for i in d.values()))
print(r)


(n, p) = map(int, input().split())
s = list(input())
ans = 0
if p == 2 or p == 5:
	for i in range(n):
		if int(s[i]) % p == 0:
			ans += i + 1
else:
	d = [0] * (n + 1)
	ten = 1
	for i in range(n - 1, -1, -1):
		a = int(s[i]) * ten % p
		ten *= 10
		ten %= p
		d[i - 1] = (d[i] + a) % p
	cnt = [0] * p
	for i in range(n, -1, -1):
		cnt[d[i]] += 1
	for i in cnt:
		ans += i * (i - 1) / 2
print(int(ans))


(n, p) = list(map(int, input().split()))
S = input()[::-1]
ans = 0
if p == 2:
	for (i, s) in enumerate(S):
		if int(s) % 2 == 0:
			ans += n - i
	print(ans)
	return
if p == 5:
	for (i, s) in enumerate(S):
		if int(s) == 0 or int(s) == 5:
			ans += n - i
	print(ans)
	return
sd = 0
d = 1
count = [0] * (p + 1)
count[0] += 1
for s in S:
	sd += int(s) * d
	d *= 10
	sd %= p
	d %= p
	count[sd] += 1
for cnt in count:
	ans += cnt * (cnt - 1) // 2
print(ans)


(n, p) = map(int, input().split())
s = list(input())
r = [0] * p
ans = 0
if not (p == 2 or p == 5):
	(x, t) = (0, 1)
	for i in range(-1, -(n + 1), -1):
		x += int(s[i]) * t
		x %= p
		r[x] += 1
		t *= 10
		t %= p
	for i in r:
		if i >= 2:
			ans += i * (i - 1) // 2
	ans += r[0]
else:
	for i in range(n):
		if int(s[i]) % p == 0:
			ans += i + 1
print(ans)


(n, p) = map(int, input().split())
s = [int(j) for j in input()][::-1]
if p == 2:
	ans = 0
	for (i, j) in enumerate(s):
		if j % 2 == 0:
			ans += n - i
	print(ans)
	return
if p == 5:
	ans = 0
	for (i, j) in enumerate(s):
		if j % 5 == 0:
			ans += n - i
	print(ans)
	return
c = [0] * p
tmp = 0
c[0] += 1
t = 1
import numpy as np
for i in s:
	tmp += t * i
	c[tmp % p] += 1
	t = t * 10 % p
c = np.array(c)
ans = c * (c - 1) // 2
print(ans.sum())


(n, p) = map(int, input().split())
s = input()
x = [1] + [0] * (p - 1)
ans = 0
u = 0
if p in [2, 5]:
	for i in range(n):
		if int(s[i]) % p == 0:
			ans += i + 1
else:
	for i in range(n - 1, -1, -1):
		u = (int(s[i]) * pow(10, n - 1 - i, p) + u) % p
		ans += x[u]
		x[u] += 1
print(ans)


import sys
(N, P) = list(map(int, input().split()))
A = input()
ans = 0
if 10 % P == 0:
	for r in range(len(A)):
		if int(A[r]) % P == 0:
			ans += r + 1
	print(ans)
	return
A = '0' + A[::-1]
S = [0] * len(A)
cnt = [0] * P
cnt[0] = 1
for i in range(len(A) - 1):
	S[i + 1] = (S[i] + int(A[i + 1]) * pow(10, i, P)) % P
	cnt[S[i + 1] % P] += 1
for c in cnt:
	ans += c * (c - 1) // 2
print(ans)


from math import factorial
import collections

def permutations_count(n, r):
	return factorial(n) // factorial(n - r)

def combinations_count(n, r):
	return factorial(n) // (factorial(n - r) * factorial(r))
(n, p) = map(int, input().split())
S = input()
su = 0
if p > 6 or p == 3:
	lis = []
	amari = 1
	lis.append(int(S[-1]) % p)
	for i in range(2, len(S) + 1):
		amari = amari * 10 % p
		lis.append((int(S[-1 * i]) * amari + lis[i - 2]) % p)
	c = collections.Counter(lis)
	for k in c:
		if c[k] > 1:
			su += combinations_count(c[k], 2)
	su += c[0]
	print(su)
else:
	S = S[::-1]
	for i in range(len(S)):
		if int(S[i]) % p == 0:
			su += len(S) - i
	print(su)


(n, p) = map(int, input().split())
s = input()
ans = 0
mod = [-1 for i in range(p)]
mod[0] = 0
if p == 2 or p == 5:
	for i in range(n):
		if int(s[i]) % p == 0:
			ans += i + 1
else:
	mp = 0
	m10 = 1
	for i in range(n - 1, -1, -1):
		mp = (mp + int(s[i]) * m10) % p
		m10 = 10 * m10 % p
		mod[mp] += 1
	for m in mod:
		ans += m * (m + 1) // 2
print(ans)


from collections import Counter
(N, P) = map(int, input().split())
S = list(map(int, list(input())))
ans = 0
if P in (2, 5):
	cnt = 0
	for (i, s) in enumerate(S):
		if s % P == 0:
			ans += i + 1
else:
	S.reverse()
	now = 0
	d = [0] * (N + 1)
	for i in range(N):
		now += S[i] * pow(10, i, P)
		now %= P
		d[i] = now % P
	c = Counter(d)
	for (i, v) in c.items():
		ans += v * (v - 1) // 2
print(ans)


(N, P) = map(int, input().split())
S = list(map(int, input()))
if P == 2 or P == 5:
	ans = 0
	for (i, c) in enumerate(S, 1):
		if c % P == 0:
			ans += i
	print(ans)
	exit()
L = [0] * P
cum = 0
ans = 0
L[0] += 1
inv10 = pow(10, P - 2, P)
base = 1
for c in S:
	cum = (cum + c * base) % P
	base = base * inv10 % P
	ans += L[cum]
	L[cum] += 1
print(ans)


(N, P) = map(int, input().split())
S = input()
if 10 % P == 0:
	ans = 0
	for r in range(N):
		if int(S[r]) % P == 0:
			ans += r + 1
	print(ans)
	exit()
d = [0] * (N + 1)
ten = 1
for i in range(N - 1, -1, -1):
	a = int(S[i]) * ten % P
	d[i] = (d[i + 1] + a) % P
	ten *= 10
	ten %= P
cnt = [0] * P
ans = 0
for i in range(N, -1, -1):
	ans += cnt[d[i]]
	cnt[d[i]] += 1
print(ans)


(N, P) = list(map(int, input().split()))
S = input().strip()[::-1]
if P in [2, 5]:
	ans = 0
	for r in range(N):
		if int(S[r]) % P == 0:
			ans += N - r
	print(ans)
	return
d = [0] * (N + 1)
ten = 1
for i in range(N):
	a = int(S[i]) * ten % P
	d[i + 1] = (d[i] + a) % P
	ten *= 10
	ten %= P
cnt = [0] * P
ans = 0
for i in range(N + 1):
	ans += cnt[d[i]]
	cnt[d[i]] += 1
print(ans)


(N, P) = map(int, input().split())
S = input()
if 10 % P == 0:
	ans = 0
	for i in range(N):
		if int(S[i]) % P == 0:
			ans += i + 1
	print(ans)
else:
	S = S[::-1]
	D = {}
	D[0] = 1
	Amari = 0
	for i in range(N):
		I = (Amari + pow(10, i, P) * int(S[i])) % P
		Amari = I
		if I not in D:
			D[I] = 1
		else:
			D[I] += 1
	ans = 0
	for (k, v) in D.items():
		ans += v * (v - 1) // 2
	print(ans)


import sys
input = sys.stdin.readline
(n, p) = [int(i) for i in 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
	print(ans)
	exit()
else:
	chk = [0] * p
	chk[0] = 1
	m = 0
	for i in range(n)[::-1]:
		m = (int(s[i]) * pow(10, n - 1 - i, p) + m) % p
		chk[m] += 1
	for i in chk:
		ans += i * (i - 1) / 2
	print(int(ans))


import sys

def I():
	return int(sys.stdin.readline().rstrip())

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

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

def S():
	return sys.stdin.readline().rstrip()

def LS():
	return list(sys.stdin.readline().rstrip().split())

def LS2():
	return list(sys.stdin.readline().rstrip())
(N, P) = map(int, S().split())
S = LI2()
if P == 2 or P == 5:
	ans = 0
	for i in range(N):
		if S[i] % P == 0:
			ans += i + 1
	print(ans)
	return
A = [0]
for i in range(1, N + 1):
	A.append((A[i - 1] + pow(10, i, P) * S[N - i]) % P)
from collections import Counter
c = Counter(A)
B = c.values()
ans = 0
for i in B:
	ans += i * (i - 1) // 2
print(ans)


import sys
input = sys.stdin.readline
(N, P) = map(int, input().split())
S = input().strip()
if P in {2, 5}:
	r = 0
	for i in range(N):
		if not int(S[i]) % P:
			r += i + 1
	print(r)
else:
	S = S[::-1]
	r = 0
	from collections import defaultdict
	d = defaultdict(int)
	d[0] += 1
	R = 0
	X = 1
	for i in range(N):
		r += int(S[i]) * X
		R += d[r % P]
		X = X * 10 % P
		d[r % P] += 1
	print(R)


def m():
	(n, p) = map(int, input().split())
	now = 0
	s = input()
	if p == 2 or p == 5:
		ans = 0
		for i in range(n):
			if int(s[i]) % p:
				continue
			ans += i + 1
	else:
		table = [0] * p
		table[0] = 1
		c = 1
		for i in range(n - 1, -1, -1):
			now = (now + c * int(s[i])) % p
			c = 10 * c % p
			table[now] += 1
		ans = sum((j * (j - 1) // 2 for j in table))
	print(ans)
m()


from collections import defaultdict as dd
(N, p) = map(int, input().split())
s = input()
res = 0
dic = dd(int)
c = [0] * (N + 1)
if p == 2 or p == 5:
	for i in range(N):
		now = int(s[N - i - 1]) % p
		if now == 0:
			res += N - i
	print(res)
	exit()
for i in range(N):
	now = int(s[N - i - 1]) % p
	c[i + 1] = (c[i] + pow(10, i, p) * now) % p
for val in c:
	dic[str(val)] += 1
	if dic[str(val)] >= 2:
		res += dic[str(val)] - 1
print(res)


from collections import Counter
(n, mod) = map(int, input().split())
s = input()
if mod == 2:
	ans = 0
	for i in range(n - 1, -1, -1):
		if int(s[i]) % 2 == 0:
			ans += i + 1
	print(ans)
	return
elif mod == 5:
	ans = 0
	for i in range(n - 1, -1, -1):
		if int(s[i]) % 5 == 0:
			ans += i + 1
	print(ans)
	return
l = [0] * (n + 1)
for i in range(n - 1, -1, -1):
	l[i] = (l[i + 1] + int(s[i]) * pow(10, n - 1 - i, mod)) % mod
c = Counter(l)

def nC2(i):
	return i * (i - 1) // 2
ans = c[0] - 1 + nC2(c[0] - 1)
for i in range(1, mod):
	ans += nC2(c[i])
print(ans)


LI = lambda : list(map(int, input().split()))
(N, P) = LI()
S = input()

def solve2():
	ans = 0
	for i in range(N):
		if int(S[i]) % 2 == 0:
			ans += i + 1
	return ans

def solve5():
	ans = 0
	for i in range(N):
		if int(S[i]) % 5 == 0:
			ans += i + 1
	return ans

def solve():
	d = [0] * P
	d[0] = 1
	w = 0
	ans = 0
	m = 1
	for s in S[::-1]:
		x = int(s)
		v = x * m % P
		w = (w + v) % P
		ans += d[w]
		d[w] += 1
		m = 10 * m % P
	return ans

def main():
	if P == 2:
		ans = solve2()
	elif P == 5:
		ans = solve5()
	else:
		ans = solve()
	print(ans)

def __starting_point():
	main()
__starting_point()


from collections import *
(n, p) = list(map(int, input().split()))
s = list(map(int, input()))
if 10 % p == 0:
	r = 0
	for i in range(n):
		if s[i] % p == 0:
			r += i + 1
	print(r)
	return
c = Counter()
c[0] += 1
v = r = 0
k = 1
for i in s[::-1]:
	v += int(i) * k
	v %= p
	r += c[v]
	c[v] += 1
	k *= 10
	k %= p
print(r)


(n, p) = map(int, input().split())
s = input()
if p == 2 or p == 5:
	a = 0
	for i in range(n):
		if int(s[i]) % p == 0:
			a += i + 1
	print(a)
else:
	a = 0
	g = [0] * (n + 1)
	t = [0] * p
	t[0] = 1
	d = 1
	for i in range(n - 1, -1, -1):
		g[i] = (g[i + 1] + int(s[i]) * d) % p
		a += t[g[i]]
		t[g[i]] += 1
		d *= 10
		d %= p
	print(a)


(n, p) = map(int, input().split())
s = input()
ans = 0
d = {i: 0 for i in range(p)}
d[0] = 1
ap = 1
if p not in [2, 5]:
	pre = 0
	for si in s[::-1]:
		si = int(si)
		a = (si * ap + pre) % p
		ans += d[a]
		d[a] += 1
		pre = a
		ap = ap * 10 % p
else:
	for (i, si) in enumerate(s):
		if int(si) % p == 0:
			ans += i + 1
print(ans)


(n, p) = map(int, input().split())
(s, n, N, c, d) = (map(int, list(input())), 1, 0, 0, [0] * p)
if p != 5:
	for i in s:
		(N, a) = ((N * 10 + i) % p, pow(n, p - 2, p))
		d[(i - N) * a % p] += 1
		c += d[-N * a % p]
		n = n * 10 % p
else:
	c = sum([j + 1 for (j, i) in enumerate(s) if i % 5 == 0])
print(c)


(n, p) = map(int, input().split())
S = list(map(int, list(input())))
if p == 2 or p == 5:
	ans = 0
	for (i, x) in enumerate(S[::-1]):
		if x % p == 0:
			ans += n - i
else:
	mods = [0 for _ in range(p)]
	mods[0] = 1
	num = 0
	digit = 1
	for s in S[::-1]:
		num = (s * digit + num) % p
		mods[num] += 1
		digit = digit * 10 % p
	ans = 0
	for m in mods:
		ans += m * (m - 1) // 2
print(ans)


from collections import Counter
(N, P) = map(int, input().split())
Ss = input()
if P == 2 or P == 5:
	ans = 0
	for (i, S) in enumerate(Ss):
		if int(S) % P == 0:
			ans += i + 1
else:
	As = [0]
	A = 0
	D = 1
	for S in Ss[::-1]:
		S = int(S)
		A = (A + S * D) % P
		As.append(A)
		D = D * 10 % P
	cnt = Counter()
	ans = 0
	for A in As:
		ans += cnt[A]
		cnt[A] += 1
print(ans)


from collections import Counter
(n, p) = map(int, input().split())
s = input()
if p == 2 or p == 5:
	ans = 0
	for i in range(n):
		if int(s[i]) % p == 0:
			ans += i + 1
	print(ans)
	exit()
num = 0
a = [0] * (n + 1)
for i in reversed(range(n)):
	j = n - 1 - i
	num += int(s[i]) * pow(10, j, p) % p
	num %= p
	a[j + 1] = num
ctr = Counter(a)
ans = 0
for v in ctr.values():
	ans += v * (v - 1) // 2
print(ans)


import sys
input = sys.stdin.readline
(N, P) = map(int, input().split())
S = list(input().rstrip())
if P in {2, 5}:
	ans = 0
	for (i, s) in enumerate(S):
		if int(s) % P == 0:
			ans += i + 1
else:
	ans = 0
	T = [0] * P
	T[0] = 1
	tmp = 0
	k = 1
	for s in reversed(S):
		tmp = (tmp + k * int(s)) % P
		k = k * 10 % P
		ans += T[tmp]
		T[tmp] += 1
print(ans)


(n, p) = map(int, input().split())
s = input()
count = [0] * p
key = 0
if p % 2 and p % 5:
	count = [0] * p
	key = 0
	mod = 1
	for i in range(n):
		key += mod * int(s[n - 1 - i]) % p
		key %= p
		count[key] += 1
		mod *= 10
		mod %= p
	ans = count[0]
	for i in range(p):
		if count[i] >= 2:
			ans += count[i] * (count[i] - 1) // 2
else:
	ans = 0
	for i in range(n):
		key = int(s[n - 1 - i])
		if key % p == 0:
			ans += n - i
print(ans)


(n, p) = map(int, input().split())
s = list(map(int, input()[::-1]))
cnt = 0
if 10 % p == 0:
	for (i, c) in enumerate(s):
		if int(c) % p == 0:
			cnt += n - i
else:
	accmod = [0] * p
	accmod[0] = 1
	num = 0
	for i in range(n):
		num = (num + s[i] * pow(10, i, p)) % p
		accmod[num] += 1
	for v in accmod:
		if v > 1:
			cnt += v * (v - 1) // 2
print(cnt)


(N, P) = list(map(int, input().split()))
S = input()
tot = 0
if P in [2, 5]:
	for i in range(1, N + 1):
		if int(S[-i]) % P == 0:
			tot += N - i + 1
else:
	S_mod = [0] * P
	S_mod[0] = 1
	mod = 0
	mod10 = 10 % P
	mod_power10 = 1
	for i in range(N - 1, -1, -1):
		mod = (int(S[i]) % P * mod_power10 + mod % P) % P
		tot += S_mod[mod]
		S_mod[mod] += 1
		mod_power10 = mod_power10 * mod10 % P
print(tot)


from collections import defaultdict

def main():
	(N, P) = list(map(int, input().split()))
	S = input()
	if P in [2, 5]:
		ans = 0
		for right in range(N - 1, -1, -1):
			if int(S[right]) % P == 0:
				ans += right + 1
		print(ans)
		return
	cur_c = 0
	C = [0] * N
	pw = 1
	for (n, s) in enumerate(S[::-1]):
		cur_c = (cur_c + pw * int(s)) % P
		C[N - 1 - n] = cur_c
		pw = pw * 10 % P
	counter = defaultdict(int)
	for c in C:
		counter[c] += 1
	ans = 0
	for c in C:
		counter[c] -= 1
		ans += counter[c]
	ans += len([c for c in C if c == 0])
	print(ans)

def __starting_point():
	main()
__starting_point()


(N, P) = list(map(int, input().split()))
S = input()
from collections import Counter
ans = 0
if P == 2 or P == 5:
	for i in range(N - 1, -1, -1):
		t = S[i]
		if not int(t) % P:
			ans += i + 1
else:
	c = Counter()
	c[0] += 1
	p = 1
	t = int(S[N - 1])
	c[t % P] += 1
	for i in range(N - 2, -1, -1):
		p *= 10
		t = int(S[i]) * p + t
		c[t % P] += 1
		p %= P
	for a in list(c.values()):
		ans += a * (a - 1) // 2
print(ans)


from collections import Counter, defaultdict, deque
from heapq import heappop, heappush, heapify
import sys, bisect, math, itertools, fractions, copy
sys.setrecursionlimit(10 ** 8)
mod = 10 ** 9 + 7
INF = float('inf')

def inp():
	return int(sys.stdin.readline())

def inpl():
	return list(map(int, sys.stdin.readline().split()))
(n, p) = inpl()
t = list(input())[::-1]
res = 0
if p == 2 or p == 5:
	t = t[::-1]
	for (i, x) in enumerate(t):
		if int(x) % p == 0:
			res += i + 1
	print(res)
	return
d = defaultdict(int)
now = 0
d[0] += 1
for (i, x) in enumerate(t):
	tmp = pow(10, i, p) * int(x) % p
	now += tmp
	now %= p
	d[now] += 1
for va in d.values():
	res += va * (va - 1) // 2
print(res)


(n, p) = list(map(int, input().split()))
s = input()
r = set()
last = 0
d = {0: 0}
total = 0
rem = 0
if p == 2:
	for i in range(0, len(s)):
		if int(s[i]) % 2 == 0:
			total += i + 1
	print(total)
elif p == 5:
	for i in range(0, len(s)):
		if int(s[i]) % 5 == 0:
			total += i + 1
	print(total)
else:
	power = 1
	for i in range(len(s) - 1, -1, -1):
		n = int(s[i]) * power + rem
		power *= 10
		power = power % p
		rem = n % p
		if rem in list(d.keys()):
			d[rem] += 1
		else:
			d[rem] = 1
		total += d[rem] - 1
	print(total + d[0])


import sys
input = sys.stdin.readline
(N, P) = map(int, input().split())
S = list(map(int, list(input().rstrip())))
ans = 0
if P == 2 or P == 5:
	for i in range(N):
		if S[i] % P == 0:
			ans += i + 1
else:
	U = [0] * (N + 1)
	count = [0] * P
	count[0] = 1
	factor = 10
	for i in range(N)[::-1]:
		U[i] = (S[i] * factor + U[i + 1]) % P
		factor = factor * 10 % P
		ans += count[U[i]]
		count[U[i]] += 1
print(ans)


(N, P) = map(int, input().split())
S = input()
ans = 0
if P == 2:
	for i in range(N):
		if int(S[i]) % 2 == 0:
			ans += i + 1
elif P == 5:
	for i in range(N):
		if int(S[i]) == 0 or int(S[i]) == 5:
			ans += i + 1
else:
	cnt = [0 for _ in range(P)]
	cnt[0] = 1
	bai = 1
	v = 0
	for i in range(N)[::-1]:
		v = (v + int(S[i]) * bai) % P
		bai *= 10
		bai %= P
		cnt[v] += 1
	for i in range(P):
		ans += (cnt[i] - 1) * cnt[i] // 2
print(ans)


(N, P) = map(int, input().split())
S = input()
mods = [0] * (N + 1)
for i in range(N - 1, -1, -1):
	mods[i] = (int(S[i]) * pow(10, N - i - 1, P) + mods[i + 1]) % P
c = dict()
for m in mods:
	c[m] = c.get(m, 0) + 1
ans = 0
if P == 2 or P == 5:
	for (i, s) in enumerate(S):
		s = int(s)
		if s % P == 0:
			ans += i + 1
else:
	for key in c:
		ans += c[key] * (c[key] - 1) // 2
print(ans)


(n, p) = map(int, input().split())
s = input()
if p == 2:
	ans = 0
	for i in range(n):
		if int(s[i]) % 2 == 0:
			ans = ans + i + 1
	print(ans)
elif p == 5:
	ans = 0
	for i in range(n):
		if int(s[i]) % 5 == 0:
			ans = ans + i + 1
	print(ans)
else:
	R = [0] * p
	x = 0
	y = 1
	for i in range(n - 1, -1, -1):
		a = int(s[i])
		b = (a * y + x) % p
		R[b] = R[b] + 1
		y = y * 10 % p
		x = b
	ans = R[0] * (R[0] + 1) // 2
	for i in range(1, p):
		ans = ans + R[i] * (R[i] - 1) // 2
	print(ans)


from collections import Counter
(N, P) = list(map(int, input().split()))
S = input()
if P in (2, 5):
	ans = sum((i for (i, s) in enumerate(S, 1) if not int(s) % P))
else:
	Acc = [0] * (N + 1)
	p10 = 1
	for (i, s) in enumerate(reversed(S)):
		Acc[N - i - 1] = (Acc[N - i] + p10 * int(s)) % P
		p10 = p10 * 10 % P
	ans = sum((v * (v - 1) // 2 for v in list(Counter(Acc).values())))
print(ans)


(n, mod) = map(int, input().split())
S = input()
total = 0
if mod == 2 or mod == 5:
	for (i, q) in enumerate(S):
		if int(q) % mod == 0:
			total += i + 1
else:
	counts = [0] * mod
	counts[0] = 1
	h = 0
	d = 1
	for s in reversed(S):
		m = int(s) * d % mod
		h = (h + m) % mod
		total += counts[h]
		counts[h] += 1
		d = d * 10 % mod
print(total)


import sys
from collections import Counter

def ep(*params):
	print(*params, file=sys.stderr)
(N, P) = list(map(int, input().split()))
S = input().rstrip()
if 10 % P == 0:
	ans = 0
	for i in range(N):
		if int(S[i]) % P == 0:
			ans += i + 1
	print(ans)
	return
ans = 0
d = [0] * (N + 1)
cnt = [0] * P
ten = 1
for i in range(N - 1, -1, -1):
	a = int(S[i]) * ten % P
	d[i] = (d[i + 1] + a) % P
	ten *= 10
	ten %= P
for i in range(N, -1, -1):
	ans += cnt[d[i]]
	cnt[d[i]] += 1
print(ans)


(n, p) = map(int, input().split())
s = input()
c = [0 for i in range(p)]
c[0] = 1
x = 0
ans = 0
for (i, j) in enumerate(s[::-1]):
	if p == 2 or p == 5:
		if int(j) % p == 0:
			ans += n - i
	x = (x + int(j) * pow(10, i, p)) % p
	c[x] += 1
if ans:
	print(ans)
	exit()
for i in range(p):
	ans += c[i] * (c[i] - 1) // 2
print(ans)


(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:
	t = [0] * 20000
	t[0] = 1
	now = 0
	po = 1
	for i in range(N):
		n = N - i - 1
		now = (int(S[n]) * po + now) % P
		po = 10 * po % P
		ans += t[now]
		t[now] += 1
print(ans)


from collections import defaultdict
(N, p) = map(int, input().split())
S = input()
S = S[::-1]
d = defaultdict(lambda : 0)
r = 0
for i in range(N):
	r += int(S[i]) * pow(10, i, p)
	r %= p
	d[r] += 1
ans = 0
for r in d:
	ans += d[r] * (d[r] - 1) // 2
ans += d[0]
if p == 2 or p == 5:
	S = S[::-1]
	ans = 0
	for i in range(N):
		if int(S[i]) % p == 0:
			ans += i + 1
print(ans)


from collections import Counter
(N, P) = map(int, input().split())
S = input()
if P == 2:
	ret = 0
	for i in range(N):
		if int(S[i]) % 2 == 0:
			ret += i + 1
	print(ret)
	return
if P == 5:
	ret = 0
	for i in range(N):
		if int(S[i]) % 5 == 0:
			ret += i + 1
	print(ret)
	return
mods = [0] * (N + 1)
for i in reversed(range(N)):
	mods[i] = (mods[i + 1] + pow(10, N - i - 1, P) * int(S[i])) % P
cnt = Counter(mods)
ans = 0
for i in cnt:
	ans += cnt[i] * (cnt[i] - 1) // 2
print(ans)


from collections import Counter
(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:
	mods = [0] * p
	mods[0] = 1
	m = 0
	d = 1
	for i in range(n):
		m = (m + int(s[-i - 1]) * d) % p
		d = d * 10 % p
		mods[m] += 1
	for i in range(p):
		ans += mods[i] * (mods[i] - 1) // 2
print(ans)


from collections import Counter
(n, p) = map(int, input().split())
s = list(map(int, list(input())))
ans = 0
if p in {2, 5}:
	for (i, num) in enumerate(s):
		if num % p == 0:
			ans += i + 1
else:
	(bfo, cnt) = (0, [1] + [0] * (p - 1))
	for (i, num) in enumerate(s[::-1]):
		bfo = (bfo + pow(10, i, p) * num) % p
		ans += cnt[bfo]
		cnt[bfo] += 1
print(ans)


(N, P) = map(int, input().split())
S = input()
ans = 0
if P == 2 or P == 5:
	for (i, s) in enumerate(S):
		if int(s) % P == 0:
			ans += i + 1
else:
	l = [0] * P
	l[0] = 1
	Sum = 0
	digits = 1
	for c in S[::-1]:
		Sum += int(c) * digits % P
		Sum %= P
		l[Sum] += 1
		digits = digits * 10 % P
	for i in range(len(l)):
		ans += l[i] * (l[i] - 1) // 2
print(ans)


from collections import Counter

def make_modlist(Len, mod):
	modlist = [0] * Len
	modlist[0] = 1
	for i in range(1, Len):
		modlist[i] = 10 * modlist[i - 1] % mod
	return modlist
(n, p) = map(int, input().split())
a = list(map(int, input()))
ans = 0
a.reverse()
if p == 2 or p == 5:
	for i in range(n):
		if a[i] % p == 0:
			ans += n - i
else:
	d = make_modlist(n, p)
	b = [0] * (n + 1)
	for i in range(n):
		b[i + 1] = a[i] * d[i] % p
	for i in range(1, n + 1):
		b[i] += b[i - 1]
		b[i] %= p
	for i in Counter(b).values():
		ans += i * (i - 1) // 2
print(ans)


p = int(input().split()[1])
s = input()
if 10 % p == 0:
	r = sum((i for (i, x) in enumerate(s, 1) if int(x) % p == 0))
else:
	d = [1] + [0] * (p - 1)
	(t, y) = (0, 1)
	for x in reversed(s):
		t = (t + int(x) * y) % p
		d[t] += 1
		y = y * 10 % p
	r = sum((i * (i - 1) // 2 for i in d))
print(r)


(N, P) = map(int, input().split())
S = input()
ans = 0
if P == 2:
	for i in range(N - 1, -1, -1):
		if int(S[i]) % 2 == 0:
			ans += i + 1
elif P == 5:
	for i in range(N - 1, -1, -1):
		if int(S[i]) % 5 == 0:
			ans += i + 1
else:
	L = [0] * P
	num = 0
	for i in range(N - 1, -1, -1):
		num += int(S[i]) * pow(10, N - 1 - i, P)
		num %= P
		L[num] += 1
	ans += L[0]
	for i in range(P):
		ans += L[i] * (L[i] - 1) // 2
print(ans)


(N, P) = map(int, input().split())
S = input()
if P == 2 or P == 5:
	ans = 0
	for (i, s) in enumerate(S):
		if int(s) % P == 0:
			ans += i + 1
	print(ans)
	import sys
	sys.exit(0)
surpluses = [0] * P
s = 0
power = 1
for i in range(N):
	s = (s + int(S[-1 - i]) * power) % P
	surpluses[s % P] += 1
	power = power * 10 % P
ans = surpluses[0]
for count in surpluses:
	ans += count * (count - 1) // 2
print(ans)


(N, P) = map(int, input().split())
S = list(map(int, list(input())))[::-1]
counter = [0] * P
counter[0] = 1
ans = 0
sum = 0
d = 0
r = []
mod = 0
if P != 2 and P != 5:
	mod = 1 % P
	for i in range(N):
		d = S[i] * mod
		sum = (sum + d) % P
		mod = mod * 10 % P
		counter[sum] += 1
	for k in range(P):
		ans += counter[k] * (counter[k] - 1) // 2
if P == 2 or P == 5:
	if P == 2:
		r = [0, 2, 4, 6, 8]
	if P == 5:
		r = [0, 5]
	for j in range(N):
		if S[j] in r:
			ans += N - j
print(ans)


import collections
import sys
sys.setrecursionlimit(10 ** 8)

def Z():
	return int(input())

def ZZ():
	return [int(_) for _ in input().split()]

def main():
	(N, P) = ZZ()
	S = input()
	output = 0
	if P in {2, 5}:
		for i in range(N):
			if int(S[i]) % P == 0:
				output += i + 1
		print(output)
		return
	dp = [0] * (N + 1)
	ex = 1
	for i in range(N):
		dp[i + 1] = (int(S[-1 - i]) * ex + dp[i]) % P
		ex *= 10
		ex %= P
	d = collections.defaultdict(int)
	for i in range(N + 1):
		d[dp[i]] += 1
	for i in list(d.keys()):
		output += d[i] * (d[i] - 1) // 2
	print(output)
	return

def __starting_point():
	main()
__starting_point()


(N, P) = list(map(int, input().split()))
S = input()
if P == 2 or P == 5:
	cnt = 0
	cnt_a = 0
	for s in S[::-1]:
		if int(s) % P == 0:
			cnt_a += 1
		cnt += cnt_a
else:
	r_lst = [0] * P
	r_lst[0] = 1
	cnt = 0
	num = 0
	for (i, s) in enumerate(S[::-1]):
		num = (num + int(s) * pow(10, i, P)) % P
		cnt += r_lst[num]
		r_lst[num] += 1
print(cnt)


from collections import defaultdict
(N, P) = map(int, input().split())
S = input()
if P == 2 or P == 5:
	ans = 0
	for i in range(N):
		if int(S[i]) % P == 0:
			ans += i + 1
	print(ans)
else:
	ctr = defaultdict(int)
	ctr[0] = 1
	cur = 0
	for i in reversed(range(N)):
		cur = (cur + int(S[i]) * pow(10, N - i - 1, P)) % P
		ctr[cur] += 1
	ans = 0
	for v in ctr.values():
		ans += v * (v - 1) // 2
	print(ans)


(N, P) = input().split()
p_len = len(P)
N = int(N)
P = int(P)
S = input()
cnt = 0
if P in [2, 5]:
	for i in range(N):
		cnt += i + 1 if int(S[i]) % P == 0 else 0
else:
	table = [0] * P
	Ui = 0
	ten = 1
	S = S[::-1]
	table[0] = 1
	for i in range(N):
		Ui = (Ui + int(S[i]) * ten) % P
		cnt += table[Ui]
		table[Ui] += 1
		ten = ten * 10 % P
print(cnt)


from collections import Counter
(n, p) = map(int, input().split())
s = input()
ans = 0
if p in {2, 5}:
	lst = set((i for i in range(0, 10, p)))
	for (i, num) in enumerate(s):
		if int(num) in lst:
			ans += i + 1
else:
	num = [0]
	for i in range(len(s)):
		tmp = num[-1] + pow(10, i, p) * int(s[-i - 1])
		num.append(tmp % p)
	mod = [0] * p
	for i in num:
		ans += mod[i]
		mod[i] += 1
print(ans)


import sys
from collections import defaultdict

def solve():
	input = sys.stdin.readline
	(N, P) = map(int, input().split())
	S = input().strip('\n')
	modSum = 0
	modDict = defaultdict(int)
	modDict[0] += 1
	ans = 0
	if P == 2 or P == 5:
		for i in range(N):
			if int(S[i]) % P == 0:
				ans += i + 1
	else:
		for i in range(N):
			modSum += int(S[N - i - 1]) * pow(10, i, P)
			modSum %= P
			modDict[modSum] += 1
		for key in modDict:
			v = modDict[key]
			ans += v * (v - 1) // 2
	print(ans)
	return 0

def __starting_point():
	solve()
__starting_point()


(n, p) = map(int, input().split())
s = input()
b = 1
d = 0
l = [0] * p
l[0] = 1
ans = 0
for (i, c) in enumerate(s[::-1]):
	if p == 2 or p == 5:
		if int(c) % p == 0:
			ans += n - i
	else:
		d += int(c) * b
		d %= p
		l[d] += 1
		b *= 10
		b %= p
if p != 2 and p != 5:
	for i in l:
		ans += i * (i - 1) // 2
print(ans)


def main():
	import sys
	input = sys.stdin.readline
	from collections import defaultdict
	(N, P) = map(int, input().split())
	S = input().rstrip()
	if P in (2, 5):
		ans = 0
		for (i, c) in enumerate(S):
			if int(c) % P == 0:
				ans += i + 1
		print(ans)
		return
	num = 0
	d = 1
	counter = defaultdict(int)
	counter[0] += 1
	for c in S[::-1]:
		num += int(c) * d
		num %= P
		counter[num] += 1
		d *= 10
		d %= P
	ans = 0
	for v in counter.values():
		ans += v * (v - 1) // 2
	print(ans)

def __starting_point():
	main()
__starting_point()


(n, k) = list(map(int, input().split()))
s = list(map(int, list(input())))
ans = 0
if k == 2 or k == 5:
	for (i, p) in enumerate(s):
		if p % k == 0:
			ans += i + 1
else:
	inv10 = pow(10, k - 2, k)
	inv = 10
	total = 0
	S = [0] * k
	S[0] = 1
	for (i, p) in enumerate(s):
		inv *= inv10
		inv %= k
		total += p * inv
		total %= k
		ans += S[total]
		S[total] += 1
print(ans)


(N, P) = map(int, input().split())
S = input()
cnt = 0
if P == 2 or P == 5:
	for i in range(N):
		if int(S[i]) % P == 0:
			cnt += i + 1
else:
	dic = dict()
	dic[0] = 1
	r = 0
	for i in range(N):
		s = (pow(10, i, P) * int(S[N - 1 - i]) + r) % P
		r = s
		if not s in dic:
			dic[s] = 1
		else:
			dic[s] += 1
	for i in dic:
		cnt += dic[i] * (dic[i] - 1) / 2
print(int(cnt))


(n, p) = map(int, input().split())
s = list(map(int, input()))
ans = 0
if p == 2 or p == 5:
	for (i, x) in enumerate(s):
		if p == 2 and (not x % 2) or (p == 5 and (x == 0 or x == 5)):
			ans += i + 1
	print(ans)
	exit()
s.reverse()
cum = [0] * (n + 1)
for i in range(n):
	cum[i + 1] = (cum[i] + s[i] * pow(10, i, p)) % p
t = [0] * p
for x in cum:
	t[x] += 1
for x in t:
	ans += x * (x - 1) // 2
print(ans)


from itertools import accumulate
from collections import Counter
I = lambda s: map(int, s)
p = int(input().split()[1])
s = input()
if 10 % p == 0:
	r = sum((i for (i, x) in enumerate(I(s), 1) if x % p == 0))
else:
	a = accumulate((x * pow(10, i, p) for (i, x) in enumerate(I(reversed(s)), 1)))
	c = Counter((x % p for x in a))
	c[0] += 1
	r = sum((i * (i - 1) // 2 for i in c.values()))
print(r)


(n, p) = map(int, input().split())
S = input()
m = [0 for i in range(p)]
ans = 0
m[0] = 1
if p == 2 or p == 5:
	for i in range(n):
		if int(S[i]) % p == 0:
			ans += i + 1
else:
	cnt = 10 % p
	for i in range(n):
		s = int(S[n - 1 - i])
		if i == 0:
			r = s % p
		else:
			r = (cnt * s + r) % p
			cnt = cnt * 10 % p
		if m[r] >= 1:
			ans += m[r]
		m[r] += 1
print(ans)


def main():
	(N, P) = map(int, input().split())
	S = input()
	if P == 2 or P == 5:
		r = 0
		for (i, v) in enumerate(S):
			if int(v) % P == 0:
				r += i + 1
		return r
	l = [0] * P
	l[0] = 1
	p = 0
	r = 0
	for (i, v) in enumerate(reversed(S)):
		p = (p + int(v) * pow(10, i, P)) % P
		r += l[p]
		l[p] += 1
	return r
print(main())


from collections import Counter
(n, p) = map(int, input().split())
s = input()
if p == 2 or p == 5:
	ans = 0
	for (i, e) in enumerate(s, 1):
		if int(e) % p == 0:
			ans += i
	print(ans)
else:
	li = [0]
	for (i, e) in enumerate(s[::-1], 1):
		li.append((li[-1] + int(e) * pow(10, i, p)) % p)
	c = Counter(li)
	ans = 0
	for v in c.values():
		ans += v * (v - 1) // 2
	print(ans)


(N, P) = map(int, input().split())
S = input()
ans = 0
C = [0] * P
C[0] = 1
a = 0
if P in (2, 5):
	for (i, s) in enumerate(S):
		if int(s) % P == 0:
			ans += i + 1
	print(ans)
else:
	for (i, s) in enumerate(S[::-1]):
		a = (a + int(s) * pow(10, i, P)) % P
		ans += C[a]
		C[a] += 1
	print(ans)


import math
import queue
from collections import deque, defaultdict
import heapq as hpq
from sys import stdin, setrecursionlimit
ipt = stdin.readline
setrecursionlimit(10 ** 7)

def main():
	(n, p) = list(map(int, ipt().split()))
	s = input()
	ans = 0
	if p == 2:
		for i in range(n):
			if int(s[i]) % 2 == 0:
				ans += i + 1
		print(ans)
	elif p == 5:
		for i in range(n):
			if int(s[i]) % 5 == 0:
				ans += i + 1
		print(ans)
	else:
		d = defaultdict(int)
		pi = 0
		nk = 10 % p
		for i in s[::-1]:
			pi = (pi + int(i) * nk) % p
			d[pi] += 1
			nk = nk * 10 % p
		for i in list(d.values()):
			ans += i * (i - 1) // 2
		ans += d[0]
		print(ans)
	return

def __starting_point():
	main()
__starting_point()


(N, P) = map(int, input().split())
S = [int(_) for _ in list(input())]
if P == 2 or P == 5:
	ans = 0
	for n in range(N):
		if S[n] % P == 0:
			ans += n + 1
	print(ans)
else:
	S = [S[n] * pow(10, N - n - 1, P) % P for n in range(N)]
	S.reverse()
	T = [0]
	for s in S:
		T.append((T[-1] + s) % P)
	lst = {i: 0 for i in range(P)}
	ans = 0
	for t in T:
		ans += lst[t]
		lst[t] += 1
	print(ans)


from collections import Counter
(N, P) = map(int, input().split())
S = input()
ans = 0
if P == 2 or P == 5:
	for i in range(N):
		if int(S[-1 - i]) % P == 0:
			ans += N - i
else:
	M = []
	cum = [0]
	for i in range(N):
		M.append(pow(10, i, P) * int(S[-1 - i]) % P)
	for i in range(N):
		cum.append((cum[-1] + M[i]) % P)
	C = Counter(cum)
	for v in C.values():
		ans += v * (v - 1) // 2
print(ans)


(n, p) = [int(i) for i in input().split()]
s = input()
if p == 2 or p == 5:
	ans = 0
	for (i, j) in enumerate(s):
		if int(j) % p == 0:
			ans += i + 1
	print(ans)
	exit()
a = [0]
j = n - 1
for i in s:
	a.append((a[-1] + int(i) * pow(10, j, p)) % p)
	j -= 1
b = {}
for i in a:
	if i in b:
		b[i] += 1
	else:
		b[i] = 1
ans = 0
for i in b:
	ans += b[i] * (b[i] - 1) // 2
print(ans)


import sys
sys.setrecursionlimit(10 ** 9)
(N, P) = list(map(int, input().split()))
S = input()
if P == 2 or P == 5:
	ans = 0
	for i in range(N):
		if int(S[i]) % P == 0:
			ans += i + 1
	print(ans)
	sys.exit()
num = [0] * P
num[0] = 1
(now, ans) = (0, 0)
_10 = 1
for i in range(N - 1, -1, -1):
	now = (now + int(S[i]) * _10) % P
	_10 *= 10
	_10 %= P
	ans += num[now]
	num[now] += 1
print(ans)


(n, p) = map(int, input().split())
if p in (2, 5):
	c = 0
	for (i, x) in enumerate(map(int, input()[::-1])):
		if x % p == 0:
			c += n - i
	print(c)
else:
	c = [0] * p
	y = 0
	t = 1
	for x in map(int, input()[::-1]):
		y = (y + t * x) % p
		c[y] += 1
		t = 10 * t % p
	print(sum((i * (i - 1) // 2 for i in c)) + c[0])


(n, p) = map(int, input().split())
s = str(input())
ans = 0
if p == 2 or p == 5:
	for i in range(n):
		if int(s[i]) % p == 0:
			ans += i + 1
	print(ans)
	exit()
tmp = [0] * p
tmp[0] = 1
mod = 0
r = 1
for i in range(1, n + 1):
	mod += int(s[-i]) * r % p
	mod %= p
	tmp[mod] += 1
	r *= 10
	r %= p
for i in tmp:
	ans += i * (i - 1) // 2
print(ans)


(n, p) = map(int, input().split())
s = input()
ans = 0
ten = 1
d = 0
if 10 % p == 0:
	for i in range(n):
		if int(s[i]) % p == 0:
			ans += i + 1
	print(ans)
else:
	cntlist = [0] * p
	cntlist[0] = 1
	for i in range(n - 1, -1, -1):
		a = int(s[i]) * ten % p
		d = (d + a) % p
		ten *= 10
		ten %= p
		cntlist[d] += 1
	for i in cntlist:
		ans += i * (i - 1) // 2
	print(ans)


from collections import defaultdict
(n, p) = map(int, input().split())
s = input()
if p == 2 or p == 5:
	res = 0
	for i in range(n - 1, -1, -1):
		if int(s[i]) % p == 0:
			res += i + 1
	print(res)
	exit()
u = defaultdict(int)
u[0] = 1
f = 1
d = 0
for i in range(n - 1, -1, -1):
	d = (d + int(s[i]) * f) % p
	f = f * 10 % p
	u[d % p] += 1
res = 0
for v in u.values():
	res += v * (v - 1) // 2
print(res)


(N, P) = map(int, input().split())
S = list(map(int, input()))
if P == 2 or P == 5:
	ans = 0
	for (i, s) in enumerate(S):
		if s % P == 0:
			ans += i + 1
	print(ans)
	exit()
R = [None] * N
k = 1
for i in range(N - 1, -1, -1):
	R[i] = S[i] * k % P
	k = k * 10 % P
ans = 0
X = []
x = 0
for r in R:
	x = (x + r) % P
	X.append(x)
D = [0] * P
D[0] = 1
for x in X:
	ans += D[x]
	D[x] += 1
print(ans)


from collections import defaultdict

def solve2(s):
	ans = 0
	for (i, c) in enumerate(s):
		if c in '02468':
			ans += i + 1
	return ans

def solve5(s):
	ans = 0
	for (i, c) in enumerate(s):
		if c in '05':
			ans += i + 1
	return ans

def solve_other(s, p):
	reminders = defaultdict(lambda : 0)
	tmp = 0
	mul = 1
	for c in s[::-1]:
		c = int(c)
		tmp = (tmp + c * mul) % p
		mul = mul * 10 % p
		reminders[tmp] += 1
	reminders[0] += 1
	ans = 0
	for (r, cnt) in reminders.items():
		ans += cnt * (cnt - 1) // 2
	return ans
(n, p) = list(map(int, input().split()))
s = input()
if p == 2:
	print(solve2(s))
elif p == 5:
	print(solve5(s))
else:
	print(solve_other(s, p))


(N, P) = list(map(int, input().split()))
S = [int(i) for i in input()]
from collections import Counter

def solve(S, N, P):
	if P == 2 or P == 5:
		ans = 0
		for i in range(N):
			if S[i] % P == 0:
				ans += i + 1
		return ans
	cum = [0] * (N + 1)
	mods = [0] * N
	mods[0] = 1
	for i in range(1, N):
		mods[i] = mods[i - 1] * 10 % P
	for i in range(N):
		cum[i + 1] = (cum[i] + S[N - 1 - i] * mods[i]) % P
	c = Counter(cum)
	ans = 0
	for v in list(c.values()):
		ans += v * (v - 1) // 2
	return ans
print(solve(S, N, P))


from collections import Counter
(n, p) = map(int, input().split())
s = input()[::-1]
a = 0
t = 0
d = 1
m = [0] * p
m = [0]
for i in range(n):
	x = int(s[i]) * d % p
	m.append((m[-1] + x) % p)
	d = d * 10 % p
c = Counter(m)
for (i, j) in c.items():
	a += j * (j - 1) // 2
if p == 2 or p == 5:
	a = 0
	for i in range(n):
		x = int(s[i])
		if x % p == 0:
			a += n - i
	print(a)
else:
	print(a)


import sys
input = sys.stdin.readline
(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
	print(ans)
	exit()
total = [0] * p
total[0] = 1
t = [0] * (n + 1)
for i in range(n - 1, -1, -1):
	t[i] = t[i + 1] + int(s[i]) * pow(10, n - 1 - i, p)
	total[t[i] % p] += 1
for i in range(p):
	ans += total[i] * (total[i] - 1) // 2
print(ans)


(n, p) = map(int, input().split())
s = input()
ans = 0
ruisekiwa = [0] * (n + 1)
ten = 1
if 10 % p == 0:
	for i in range(n):
		if int(s[i]) % p == 0:
			ans += i + 1
else:
	for i in range(0, n)[::-1]:
		a = int(s[i]) * ten % p
		ruisekiwa[i] = (ruisekiwa[i + 1] + a) % p
		ten *= 10
		ten %= p
	cnt = [0] * p
	for i in range(0, n + 1)[::-1]:
		ans += cnt[ruisekiwa[i]]
		cnt[ruisekiwa[i]] += 1
print(ans)


(n, p) = map(int, input().split())
s = input()
ans = 0
if 10 % p == 0:
	for r in range(n):
		if int(s[r]) % p == 0:
			ans += r + 1
	print(ans)
	exit()
d = [0 for _ in range(n + 1)]
ten = 1
for i in range(n - 1, -1, -1):
	a = int(s[i]) * ten % p
	d[i] = (d[i + 1] + a) % p
	ten *= 10
	ten %= p
cnt = [0 for _ in range(p)]
for i in range(n, -1, -1):
	ans += cnt[d[i]]
	cnt[d[i]] += 1
print(ans)


(n, p) = map(int, input().split())
S = input()[::-1]
if p == 2 or p == 5:
	ans = 0
	for i in range(n):
		if int(S[i]) % p == 0:
			ans += n - i
	print(ans)
	exit()
mod = [0] * (n + 1)
mod_l = [0] * p
mod_10 = [1] * n
for i in range(n - 1):
	mod_10[i + 1] = mod_10[i] * 10 % p
for i in range(n):
	mod[i + 1] = (mod[i] + int(S[i]) * mod_10[i]) % p
for i in range(n + 1):
	mod_l[mod[i]] += 1
ans = 0
for i in range(p):
	ans += mod_l[i] * (mod_l[i] - 1) // 2
print(ans)


(N, P) = map(int, input().split())
lst = [int(d) for d in input()]
chk = [0] * P
t = 0
c = 1
if P == 2:
	ans = 0
	a = N
	for x in lst[::-1]:
		if x % 2 == 0:
			ans += a
		a -= 1
	print(ans)
elif P == 5:
	ans = 0
	a = N
	for x in lst[::-1]:
		if x % 5 == 0:
			ans += a
		a -= 1
	print(ans)
else:
	for x in lst[::-1]:
		t += c * x
		t %= P
		chk[t] += 1
		c *= 10
		c %= P
	md = 0
	ans = chk[0]
	d = 1
	for i in range(N - 1):
		md = (md + lst[N - 1 - i] * d) % P
		if chk[md] > 0:
			chk[md] -= 1
		ans += chk[md]
		d *= 10
		d %= P
	print(ans)


(N, P) = map(int, input().split())
S = input()
if P % 2 == 0 or P % 5 == 0:
	ans = 0
	for (i, j) in enumerate(S):
		if int(j) % P == 0:
			ans += i + 1
	print(ans)
else:
	tmp = 0
	mod = [0] * P
	mod[0] = 1
	S = S[::-1]
	for (i, j) in enumerate(S):
		tmp = (tmp + int(j) * pow(10, i, P)) % P
		mod[tmp] += 1
	print(sum([i * (i - 1) // 2 for i in mod]))


(N, P) = map(int, input().split())
S = input()
ans = 0
if P == 2:
	for (i, d) in enumerate(S):
		if d in '02468':
			ans += i + 1
elif P == 5:
	for (i, d) in enumerate(S):
		if d in '05':
			ans += i + 1
else:
	x = 1
	curr = 0
	mods = [0] * P
	mods[0] = 1
	for d in reversed(S):
		curr = (curr + x * int(d)) % P
		ans += mods[curr % P]
		mods[curr % P] += 1
		x = x * 10 % P
print(ans)


(n, p) = list(map(int, input().split()))
S = input()
if p == 2 or p == 5:
	ans = 0
	for (i, s) in enumerate(S):
		if int(s) % p == 0:
			ans += i + 1
	print(ans)
	exit()

def MS(i, s, pre):
	return (s * i + pre) % p
M = [0] * p
M[0] = 1
t = 1
now = 0
for i in S[::-1]:
	i = int(i)
	now += i * t
	now %= p
	M[now] += 1
	t = t * 10 % p
ans = sum(map(lambda m: m * (m - 1) // 2, M))
print(ans)


import collections
(n, p) = map(int, input().split())
s = input()
arr = [int(s[i]) for i in range(len(s))]
if p == 2 or p == 5:
	ans = 0
	for i in range(n):
		if arr[i] % p == 0:
			ans += i + 1
	print(ans)
else:
	dic = collections.defaultdict(int)
	tmp = 0
	for i in range(n - 1, -1, -1):
		tmp += arr[i] * pow(10, n - 1 - i, p)
		tmp %= p
		dic[tmp] += 1
	ans = 0
	rem = 0
	for i in range(n - 1, -1, -1):
		ans += dic[rem]
		rem += arr[i] * pow(10, n - 1 - i, p)
		rem %= p
		dic[rem] -= 1
	print(ans)


(n, p) = map(int, input().split())
s = input()
if 10 % p == 0:
	print(sum((i for (i, x) in enumerate(s, 1) if int(x) % p == 0)))
	exit()
ans = 0
u = 0
d = 1
l = [0] * p
l[0] = 1
s = s[::-1]
for i in map(int, s):
	u = (u + i * d) % p
	l[u] += 1
	d = d * 10 % p
for i in l:
	ans += i * (i - 1) // 2
print(ans)


(N, P) = map(int, input().split())
S = input()
if P in (2, 5):
	ans = 0
	for (i, c) in enumerate(S):
		c = int(c)
		if c % P == 0:
			ans += i + 1
	print(ans)
else:
	ans = 0
	a = [0]
	j = 1
	for c in S[::-1]:
		c = int(c)
		a.append((a[-1] + j * c) % P)
		j *= 10
		j %= P
	from collections import Counter
	ctr = Counter(a)
	for (k, v) in ctr.items():
		ans += v * (v - 1) // 2
	print(ans)


(N, P) = map(int, input().split())
S = [int(s) for s in input()]
if P == 2 or P == 5:
	print(sum((i for (i, s) in enumerate(S, 1) if s % P == 0)))
	quit()
C = [0] * P
tens = 1
cur = 0
for s in reversed(S):
	cur = (cur + s * tens) % P
	C[cur] += 1
	tens = tens * 10 % P
print(C[0] + sum((c * (c - 1) // 2 for c in C)))


def main():
	(n, p) = map(int, input().split())
	s = list(map(int, list(input())))
	(cnt, ans) = (0, 0)
	m = [0] * p
	m[0] = 1
	if p in [2, 5]:
		for (i, x) in enumerate(s):
			if x % p == 0:
				ans += i + 1
		print(ans)
		exit()
	sm = 0
	d = 1
	for i in range(n):
		sm = (sm + s[n - 1 - i] * d) % p
		m[sm] += 1
		d = d * 10 % p
	for i in m:
		ans += i * (i - 1) // 2
	print(ans)
main()


(N, P) = map(int, input().split())
S = input()
list = [0 for _ in range(P)]
list[0] = 1
now = 0
a = 0
if P == 2 or P == 5:
	M = len(S)
	S = reversed(S)
	l = 0
	for s in S:
		if int(s) % P == 0:
			a += M - l
			l += 1
		else:
			l += 1
	print(a)
else:
	b = 1
	h = 0
	for s in reversed(S):
		h = h + b * int(s)
		list[h % P] += 1
		b = b * 10 % P
	c = 0
	for i in range(len(list)):
		c += list[i] * (list[i] - 1) / 2
	print(int(c))


from collections import defaultdict
import sys

def input():
	return sys.stdin.readline().strip()

def main():
	(N, P) = map(int, input().split())
	S = input()
	ans = 0
	if P in [2, 5]:
		for (i, c) in enumerate(S[::-1]):
			if int(c) % P == 0:
				ans += N - i
	else:
		d = defaultdict(int)
		d[0] = 1
		num = 0
		ten = 1
		for c in S[::-1]:
			num += int(c) * ten
			num %= P
			d[num] += 1
			ten *= 10
			ten %= P
		ans = sum([d[i] * (d[i] - 1) // 2 for i in range(P)])
	print(ans)

def __starting_point():
	main()
__starting_point()


(N, P) = map(int, input().split())
S = input()
if P == 2 or P == 5:

	def solve25(N, P, S):
		c = 0
		for i in range(N - 1, -1, -1):
			if int(S[i]) % P == 0:
				c += i + 1
		return c
	print(solve25(N, P, S))
else:

	def solve(N, P, S):
		rcounts = [0] * P
		rcounts[0] = 1
		ints = 0
		for (i, s) in enumerate(S[::-1]):
			ints += int(s) * pow(10, i, P)
			r = ints % P
			rcounts[r] += 1
		c = 0
		for v in rcounts:
			c += v * (v - 1) // 2
		return c
	print(solve(N, P, S))


from collections import Counter
(N, P) = list(map(int, input().split()))
S = input()
ans = 0
if not 10 % P:
	for r in range(N):
		if not int(S[r]) % P:
			ans += r + 1
else:
	S = S[::-1]
	s = 0
	d = [0] * (N + 1)
	for i in range(N):
		s = (s + int(S[i]) * pow(10, i, P)) % P
		d[i + 1] = s
	c = Counter()
	for i in range(N + 1):
		ans += c[d[i]]
		c[d[i]] += 1
print(ans)


import sys
(n, p) = map(int, input().split())
s = list(input())
if p == 2 or p == 5:
	ans = 0
	for i in range(n):
		if int(s[i]) % p == 0:
			ans += i + 1
	print(ans)
	sys.exit(0)
ans = 0
count = [0] * p
count[0] = 1
s = s[::-1]
num = 0
seki = 1
for i in range(n):
	num += int(s[i]) * seki
	num = num % p
	count[num] += 1
	seki = seki * 10
	seki = seki % p
for i in range(p):
	N = count[i]
	ans += N * (N - 1) // 2
print(ans)


(n, p) = map(int, input().split())
s = input()
if (p == 2) | (p == 5):
	ans = 0
	for i in range(n):
		tmp = int(s[i])
		if tmp % p == 0:
			ans += i + 1
	print(ans)
	exit()
ans = 0
tmp = 0
rem = [0] * p
rem[0] = 1
for i in range(n):
	tmp = (tmp + int(s[-1 * (i + 1)]) * pow(10, i, p)) % p
	ans += rem[tmp]
	rem[tmp] += 1
print(ans)


(N, P) = list(map(int, input().split()))
S = list(str(input()))
zcount = S.count('0')
U = []
for i in range(N):
	u = int(S[N - i - 1])
	U.append(u)
npow = 1
T = [0]
now = 0
for i in range(N):
	now += U[i] * npow
	now %= P
	T.append(now)
	npow *= 10
	npow %= P
pmod = [0] * P
for t in T:
	pmod[t] += 1
ans1 = 0
for p in pmod:
	ans1 += p * (p - 1) // 2
if P != 2 and P != 5:
	print(ans1)
else:
	ans2 = 0
	for i in range(N):
		u = U[i]
		if u % P == 0:
			ans2 += N - i
	print(ans2)


(N, P) = map(int, input().split())
S = input()
if P in (2, 5):
	ans = 0
	for (i, c) in enumerate(S):
		if int(c) % P == 0:
			ans += i + 1
	print(ans)
	exit()
a = [0]
r = 1
for c in S[::-1]:
	d = int(c)
	a.append((a[-1] + d * r) % P)
	r *= 10
	r %= P
from collections import Counter
ctr = Counter(a)
ans = 0
for v in ctr.values():
	ans += v * (v - 1) // 2
print(ans)


(n, p) = map(int, input().split())
s = input()
a = []
c = 0
if p == 2:
	b = [0] * n
	for i in range(n):
		if int(s[i]) % 2 == 0:
			b[i] += 1
	for i in range(n):
		if b[i] == 1:
			c += i + 1
elif p == 5:
	b = [0] * n
	for i in range(n):
		if int(s[i]) % 5 == 0:
			b[i] += 1
	for i in range(n):
		if b[i] == 1:
			c += i + 1
else:
	b = [0] * p
	b[0] = 1
	d = [1]
	a.append(int(s[-1]) % p)
	for i in range(n - 1):
		d.append(d[-1] * 10 % p)
	for i in range(1, n):
		a.append((int(s[-i - 1]) * d[i] + a[i - 1]) % p)
	for i in range(n):
		b[a[i]] += 1
	for i in range(p):
		c += int(b[i] * (b[i] - 1) / 2)
print(c)


def i1():
	return int(input())

def i2():
	return [int(i) for i in input().split()]
[n, p] = i2()
s = input()
if p == 2 or p == 5:
	x1 = 0
	for i in range(n):
		if int(s[i]) % p == 0:
			x1 += i + 1
	print(x1)
else:
	t = 0
	x2 = 0
	d = {0: 1}
	a = 1
	for i in range(n)[::-1]:
		t += int(s[i]) * a
		t %= p
		a *= 10
		a %= p
		if t in d:
			x2 += d[t]
			d[t] += 1
		else:
			d[t] = 1
	print(x2)


(N, P) = [int(x) for x in input().split()]
S = input()
res = 0
if P in [2, 5]:
	for i in range(N):
		if int(S[i]) % P == 0:
			res += i + 1
else:
	dic = {0: 1}
	t1 = 0
	t2 = 1
	for i in range(N):
		t2 = 10 * t2 % P
		t1 = (int(S[N - 1 - i]) * t2 + t1) % P
		if t1 in dic:
			res += dic[t1]
			dic[t1] += 1
		else:
			dic[t1] = 1
print(res)


(n, p) = map(int, input().split())
s = list(map(int, list(input())))[::-1]
if 10 % p == 0:
	result = 0
	for i in range(n):
		if s[i] % p == 0:
			result += n - i
else:
	r = [0 for _ in range(p)]
	r[0] = 1
	t = 0
	ten = 1
	for i in s:
		t = (t + i * ten) % p
		ten = ten * 10 % p
		r[t] += 1
	result = 0
	for i in r:
		result += i * (i - 1) // 2
print(result)


from collections import defaultdict
(N, P) = map(int, input().split())
S = input()
if P in (2, 5):
	count = 0
	for i in range(N):
		if int(S[i]) % P == 0:
			count += i + 1
	print(count)
else:
	d = defaultdict(int)
	r = 0
	for i in range(N):
		r += int(S[N - 1 - i]) * pow(10, i % (P - 1), P)
		r %= P
		d[r] += 1
	count = d[0]
	for num in d.values():
		count += num * (num - 1) // 2
	print(count)


(n, p) = [int(_) for _ in input().split()]
s = input()
if p == 2 or p == 5:
	ans = 0
	for i in range(n):
		if int(s[i]) % p == 0:
			ans += i + 1
	print(ans)
	return
t = [0 for i in range(n + 1)]
P = [0 for i in range(p)]
P[0] += 1
d = 1
for i in range(1, n + 1):
	t[i] = (t[i - 1] + int(s[n - i]) * d) % p
	P[t[i]] += 1
	d = d * 10 % p
ans = 0
for c in P:
	ans += c * (c - 1) // 2
print(ans)


(N, P) = map(int, input().split())
S = input()
if P == 2 or P == 5:
	x = 0
	for j in range(N):
		if int(S[j]) % P == 0:
			x += j + 1
	print(x)
else:
	A = [0] * P
	a = 0
	b = 1
	for i in range(N):
		a = (a + int(S[N - 1 - i]) * b) % P
		A[a] += 1
		b = b * 10 % P
	x = A[0]
	for k in range(P):
		x += int(A[k] * (A[k] - 1) / 2)
	print(x)


def main():
	(N, p) = list(map(int, input().split()))
	S = input()
	S = S[::-1]
	if p == 2 or p == 5:
		ans = 0
		for (i, s) in enumerate(S):
			if int(s) % p == 0:
				ans += N - i
		print(ans)
	else:
		modp_counter = [0] * p
		modp = 0
		modp_counter[0] = 1
		pair_count = 0
		d = 1
		for s in S:
			modp = (int(s) * d % p + modp) % p
			pair_count += modp_counter[modp]
			modp_counter[modp] += 1
			d *= 10
			d %= p
		print(pair_count)
main()


def main():
	import collections
	(N, P) = map(int, input().split())
	S = input()[::-1]
	ans = 0
	if P == 2 or P == 5:
		for (i, s) in enumerate(S):
			if int(s) % P == 0:
				ans += N - i
	else:
		mod = [0] * P
		mod[0] = 1
		current = 0
		X = 1
		for s in S:
			current = (current + int(s) * X) % P
			ans += mod[current]
			mod[current] += 1
			X = X * 10 % P
	print(ans)

def __starting_point():
	main()
__starting_point()


(n, p) = map(int, input().split())
s = input()
if p == 2:
	ans = 0
	for i in range(n):
		if int(s[i]) % 2 == 0:
			ans += i + 1
	print(ans)
elif p == 5:
	ans = 0
	for i in range(n):
		if s[i] == '5' or s[i] == '0':
			ans += i + 1
	print(ans)
else:
	mods = [0 for _ in range(p)]
	cur = 0
	mods[0] += 1
	t = s[::-1]
	for i in range(n):
		cur = (cur + int(t[i]) * pow(10, i, p)) % p
		mods[cur] += 1
	ans = 0
	for m in mods:
		ans += m * (m - 1) // 2
	print(ans)


(n, p) = map(int, input().split())
s = input()
if p == 2 or p == 5:
	ans = 0
	for i in range(n):
		if int(s[i]) % p == 0:
			ans += i + 1
	print(ans)
else:
	t = []
	ti = 0
	for i in range(n):
		ti += int(s[-i - 1]) * pow(10, i, p)
		ti %= p
		t.append(ti)
	from collections import Counter
	tc = Counter(t)
	ans = 0
	for v in tc.values():
		ans += v * (v - 1) // 2
	if 0 in tc:
		ans += tc[0]
	print(ans)


(N, P) = [int(s) for s in input().split()]
S = list(input())
if P != 2 and P != 5:
	ls = [0 for _ in range(N)]
	mod = [0 for _ in range(P)]
	d = 10
	ls[0] = int(S[-1]) % P
	mod[ls[0]] += 1
	for i in range(1, N):
		ls[i] = (ls[i - 1] + d * int(S[-1 - i])) % P
		d = d * 10 % P
		mod[ls[i]] += 1
	ans = mod[0]
	for i in range(N):
		m = ls[i]
		mod[ls[i]] -= 1
		ans += mod[ls[i]]
else:
	ans = 0
	for i in range(N):
		if int(S[i]) % P == 0:
			ans += i + 1
print(ans)


(n, p) = list(map(int, input().split()))
s = list(map(int, input().strip()))
count = 0
if p == 2 or p == 5:
	co = 0
	for i in range(n):
		ne = int(s[n - i - 1]) % p
		if ne == 0:
			co += 1
		count += co
	print(count)
else:
	sta = [0] * p
	sta[0] += 1
	d = 1
	co = 0
	for i in range(n):
		ne = int(s[n - i - 1]) * d % p
		co += ne
		co %= p
		sta[co] += 1
		d *= 10
		d %= p
	for i in range(p):
		count += sta[i] * (sta[i] - 1) // 2
	print(count)


(N, P) = map(int, input().split())
S = str(input())
ans = 0
if 10 % P == 0:
	for i in range(N):
		if int(S[i]) % P == 0:
			ans += i + 1
else:
	rem = [0] * P
	mod = 0
	ten = 1
	rem[mod] = 1
	for i in range(N):
		mod = (mod + int(S[N - i - 1]) * ten) % P
		ten = ten * 10 % P
		rem[mod] += 1
	for j in rem:
		ans += j * (j - 1) // 2
print(ans)


(n, p) = map(int, input().split())
s = list(map(int, list(input())))
if p in (2, 5):
	print(sum((i + 1 for i in range(n) if s[i] % p == 0)))
	exit(0)
ans = g = 0
d = [0] * p
d[0] = 1
t = 1
for i in range(n - 1, -1, -1):
	g = (g + s[i] * t) % p
	ans += d[g]
	d[g] += 1
	t = t * 10 % p
print(ans)


(n, p) = map(int, input().split())
s = input()
count = 0
if p == 2 or p == 5:
	for i in range(n):
		if int(s[i]) % p == 0:
			count += i + 1
	print(count)
else:
	mod = [0] * p
	mod[0] = 1
	tmp = 0
	ten = 1
	for i in s[::-1]:
		ten = ten * 10 % p
		tmp = (tmp + int(i) * ten) % p
		mod[tmp] += 1
	for m in mod:
		count += m * (m - 1) // 2
	print(count)


import sys
(n, p) = map(int, input().split())
s = input()
x = [0 for i in range(p)]
ans = 0
if p == 2 or p == 5:
	for i in range(n):
		if int(s[i]) % p == 0:
			ans += i + 1
	print(ans)
else:
	tmp1 = 1
	tmp2 = 0
	for i in range(n - 1, -1, -1):
		tmp2 = (tmp1 * int(s[i]) + tmp2) % p
		x[tmp2] += 1
		tmp1 = tmp1 * 10 % p
	ans += x[0]
	for i in range(p):
		ans += x[i] * (x[i] - 1) // 2
	print(ans)


(n, p) = map(int, input().split())
s = input()[::-1]
if p == 2:
	ans = 0
	for (num, i) in enumerate(s):
		if int(i) % 2 == 0:
			ans += n - num
elif p == 5:
	ans = 0
	for (num, i) in enumerate(s):
		if int(i) % 5 == 0:
			ans += n - num
else:
	C = [0] * p
	now = 0
	for (num, i) in enumerate(s):
		a = int(i)
		now = (now + pow(10, num, p) * a) % p
		C[now] += 1
	ans = C[0]
	for c in C:
		ans += c * (c - 1) // 2
print(ans)


(N, P) = map(int, input().split(' '))
S = input()
ans = 0
if P in [2, 5]:
	for i in range(N):
		if int(S[i]) % P == 0:
			ans += i + 1
else:
	lis = [0 for _ in range(N + 1)]
	ten = 1
	for i in reversed(range(N)):
		tmp = int(S[i]) * ten % P
		lis[i] = (lis[i + 1] + tmp) % P
		ten *= 10
		ten %= P
	cnt = [0 for _ in range(P)]
	for i in reversed(range(N + 1)):
		ans += cnt[lis[i]]
		cnt[lis[i]] += 1
print(ans)


(n, p) = map(int, input().split())
s = list(map(int, list(input())))
ans = 0
cnt = [0] * p
cnt[0] = 1
if p == 2:
	for i in range(n):
		if s[i] in [0, 2, 4, 6, 8]:
			ans += i + 1
elif p == 5:
	for i in range(n):
		if s[i] in [0, 5]:
			ans += i + 1
else:
	sum = 0
	for i in range(n):
		sum = (sum + s[n - i - 1] * pow(10, i, p)) % p
		cnt[sum] += 1
	for j in range(p):
		cj = cnt[j]
		ans += cj * (cj - 1) // 2
print(ans)


from sys import stdin
from collections import Counter
(N, P) = map(int, stdin.readline().split())
S = stdin.readline().strip()
ans = 0
if P in (2, 5):
	for i in range(N):
		if int(S[i]) % P == 0:
			ans += i + 1
else:
	count = Counter()
	ten = 1
	mod = 0
	for i in range(N):
		x = (int(S[N - i - 1]) * ten + mod) % P
		ten = ten * 10 % P
		mod = x
		count[x] += 1
	count[0] += 1
	for i in count.values():
		ans += i * (i - 1) // 2
print(ans)


(n, p) = map(int, input().split())
s = list(map(int, list(input())))
ans = 0
if p == 2:
	for i in range(n):
		if s[i] % 2 == 0:
			ans += i + 1
	print(ans)
	return
if p == 5:
	for i in range(n):
		if s[i] == 0 or s[i] == 5:
			ans += i + 1
	print(ans)
	return
num = 1
l = [0]
for i in range(n - 1, -1, -1):
	l.append((num * s[i] + l[-1]) % p)
	num *= 10
	num %= p
from collections import Counter
dic = Counter(l)
for i in dic.values():
	ans += i * (i - 1) // 2
print(ans)


(N, P) = map(int, input().split())
S = input()
if P == 2:
	ans = 0
	for (i, d) in enumerate(map(int, S)):
		if d % 2 == 0:
			ans += i + 1
	print(ans)
elif P == 5:
	ans = 0
	for (i, d) in enumerate(map(int, S)):
		if d % 5 == 0:
			ans += i + 1
	print(ans)
else:
	mods = [0] * P
	mods[0] = 1
	cur_mod = 0
	for (i, digit) in enumerate(map(int, S)):
		cur_mod += pow(10, N - i - 1, P) * digit
		cur_mod %= P
		mods[cur_mod] += 1
	ans = 0
	for count in mods:
		ans += count * (count - 1) // 2
	print(ans)


import sys
input = sys.stdin.readline
from collections import Counter
(N, mod) = map(int, input().split())
S = list(input().rstrip())
if mod == 2 or mod == 5:
	ans = 0
	for (i, s) in enumerate(S):
		if int(s) % mod == 0:
			ans += i + 1
else:
	dp = [0]
	t = 1
	for s in reversed(S):
		dp.append((dp[-1] + int(s) * t) % mod)
		t = t * 10 % mod
	ans = 0
	C = Counter(dp)
	for v in C.values():
		ans += v * (v - 1) // 2
print(ans)


def main():
	(n, p) = map(int, input().split())
	s = input()
	if p == 2:
		ans = 0
		for i in range(n):
			if int(s[i]) % 2 == 0:
				ans += i + 1
		print(ans)
		return
	if p == 5:
		ans = 0
		for i in range(n):
			if int(s[i]) % 5 == 0:
				ans += i + 1
		print(ans)
		return
	dp = [0 for _ in range(p)]
	dp[0] += 1
	x = 0
	for i in range(n):
		x = (x + int(s[n - 1 - i]) * pow(10, i, p)) % p
		dp[x] += 1
	ans = 0
	for i in range(p):
		ans += dp[i] * (dp[i] - 1) // 2
	print(ans)

def __starting_point():
	main()
__starting_point()


(N, P) = map(int, input().split())
S = input()
S = S[::-1]
result = 0
if P == 2 or P == 5:
	for i in range(N):
		if int(S[i]) % P == 0:
			result += N - i
else:
	t = [0] * P
	m = 1
	n = 0
	for i in range(len(S)):
		t[n] += 1
		n += int(S[i]) * m
		n %= P
		result += t[n]
		m *= 10
		m %= P
print(result)


from collections import Counter
(n, p) = list(map(int, input().split()))
s = input()
a = 0
t = list(map(int, list(s)))
t.reverse()
if p == 2:
	for i in range(n):
		if t[i] % 2 == 0:
			a += len(t) - i
elif p == 5:
	for i in range(n):
		if t[i] % 5 == 0:
			a += len(t) - i
else:
	u = []
	k = 1
	l = 0
	for i in t:
		l = (l + i * k) % p
		u.append(l)
		k = k * 10 % p
	c = Counter(u)
	a += c[0]
	for i in list(c.values()):
		if i > 1:
			a += i * (i - 1) // 2
print(a)


from collections import Counter
(N, P) = map(int, input().split())
S = input()
c = 0
if P == 2 or P == 5:
	for (i, v) in enumerate(S):
		if int(v) % P == 0:
			c += i + 1
else:
	T = [0] * (N + 1)
	d = 1
	for (i, v) in enumerate(S[::-1]):
		a = (int(v) * d + T[i]) % P
		T[i + 1] = a
		d *= 10
		d %= P
	count = Counter(T)
	c = sum((x * (x - 1) / 2 for x in count.values()))
print(int(c))


(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:
	l = [1] + [0] * (P - 1)
	tmp = 0
	r10 = 1
	for i in range(N - 1, -1, -1):
		tmp = (r10 * int(S[i]) + tmp) % P
		l[tmp] += 1
		r10 = r10 * 10 % P
	for x in l:
		ans += x * (x - 1) // 2
print(ans)


(N, P) = map(int, input().split())
S = input()
res = 0
if P == 2 or P == 5:
	for i in range(N):
		if int(S[i]) % P == 0:
			res += i + 1
else:
	mp = [0] * P
	mp[0] = 1
	cur = 0
	p10 = 1
	for c in S[::-1]:
		cur = (cur + int(c) * p10) % P
		res += mp[cur]
		mp[cur] += 1
		p10 *= 10
		p10 %= P
print(res)


(n, p) = map(int, input().split())
s = input()
if p == 2 or p == 5:
	ans = 0
	for i in range(n):
		if int(s[i]) % p == 0:
			ans += i + 1
	print(ans)
else:
	di = {0: 1}
	tmp = 0
	for i in range(n):
		tmp += int(s[n - i - 1]) * pow(10, i, p)
		tmp %= p
		if tmp in di:
			di[tmp] += 1
		else:
			di[tmp] = 1
	ans = 0
	for i in di.values():
		ans += i * (i - 1) // 2
	print(ans)


(n, p) = map(int, input().split())
a = list(map(int, list(input())))
ans = 0
if p == 2:
	for i in range(n):
		if a[i] % 2 == 0:
			ans += i + 1
elif p == 5:
	for i in range(n):
		if a[i] == 5 or a[i] == 0:
			ans += i + 1
else:
	b = 0
	c = [0 for i in range(p)]
	c[0] = 1
	for i in range(n):
		b = (b + pow(10, n - i, p) * a[i]) % p
		c[b] += 1
	c = list(map(lambda x: x * (x - 1) // 2, c))
	ans = sum(c)
print(ans)


from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque, Counter
from operator import mul
import copy
import heapq
(n, p) = list(map(int, input().split()))
s = input()
ans = 0
if p == 2 or p == 5:
	for i in range(n):
		a = int(s[n - 1 - i])
		if a % p == 0:
			ans += n - i
else:
	d = {0: 1}
	c = 0
	for i in range(n):
		c += pow(10, i, p) * int(s[n - 1 - i]) % p
		c %= p
		if c not in d:
			d[c] = 1
		else:
			d[c] += 1
	for dd in list(d.values()):
		ans += dd * (dd - 1) // 2
print(ans)


3
import sys
from collections import Counter
input = lambda : sys.stdin.readline().strip()
(n, p) = [int(x) for x in input().split()]
s = input()
ans = 0
if p == 2 or p == 5:
	allowed_digits = '24680' if p == 2 else '50'
	for (i, c) in enumerate(s, start=1):
		if c in allowed_digits:
			ans += i
else:
	count = Counter({0: 1})
	(x, e) = (0, 1)
	for c in reversed(s):
		x = (x + (ord(c) - ord('0')) * e) % p
		e = e * 10 % p
		ans += count[x]
		count[x] += 1
print(ans)


from collections import Counter
(N, P) = map(int, input().split())
S = input()
cnt = 0
if P in [2, 5]:
	for (i, s) in enumerate(S):
		if int(s) % P == 0:
			cnt += i + 1
else:
	T = [0] * (N + 1)
	mods = Counter({0: 1})
	for (i, s) in enumerate(reversed(S)):
		T[N - 1 - i] = (T[N - i] + int(s) * pow(10, i, P)) % P
		mods[T[N - 1 - i]] += 1
	for t in T:
		mods[t] -= 1
		cnt += mods[t]
print(cnt)


from collections import Counter
(N, P) = map(int, input().split())
S = input()
sum = 0
if P == 2 or P == 5:
	for i in range(N):
		if int(S[i]) % P == 0:
			sum += i + 1
	print(sum)
	exit()
m = []
t = 1
q = 0
for i in range(N, 0, -1):
	q = (int(S[i - 1]) % P * t + q) % P
	m.append(q)
	t = 10 * t % P
mc = Counter(m)
for v in mc.values():
	if v > 1:
		sum += v * (v - 1) // 2
sum += mc[0]
print(sum)


(n, p) = map(int, input().split())
s = list(input())
if p == 2 or p == 5:
	ans = 0
	for i in range(n):
		if int(s[n - i - 1]) % p == 0:
			ans += n - i - 1 + 1
	print(ans)
	exit()
mods = [0] * p
mods[0] = 1
num = 0
fac = 1
for i in range(n):
	num += int(s[n - i - 1]) * fac
	num %= p
	fac = fac * 10
	fac %= p
	mods[num] += 1
ans = 0
for item in mods:
	ans += item * (item - 1) // 2
print(ans)


(n, p) = map(int, input().split())
s = list(map(int, list(input())))

def solve():
	total = 0
	if 10 % p == 0:
		for i in range(n):
			if s[i] % p == 0:
				total += i + 1
		return total
	cnt = [0] * p
	r = 0
	ten = 1
	for i in range(n - 1, 0 - 1, -1):
		cnt[r] += 1
		r = (r + s[i] * ten) % p
		total += cnt[r]
		ten = ten * 10 % p
	return total
print(solve())


from collections import defaultdict
dd = defaultdict(int)
(n, p) = map(int, input().split())
S = list(input().rstrip())
tmp = 0
r = 1
su = 0
dd[0] = 1
if p == 2 or p == 5:
	c = n
	for s in S[::-1]:
		if int(s) % p == 0:
			su += c
		c -= 1
	print(su)
else:
	for s in S[::-1]:
		tmp += int(s) * r
		tmp %= p
		dd[tmp] += 1
		r *= 10
		r %= p
	for i in dd.values():
		su += i * (i - 1) // 2
	print(su)


(n, p) = tuple(map(int, input().split()))
s = input()
modlist = [0] * p
modlist[0] = 1
if p != 2 and p != 5:
	mod = 0
	pwrmod = 1
	for i in s[::-1]:
		mod = (mod + pwrmod * int(i)) % p
		pwrmod = pwrmod * 10 % p
		modlist[mod] += 1
	ans = 0
	for i in modlist:
		ans += i * (i - 1) // 2
	print(ans)
else:
	ans = 0
	for i in range(n):
		if int(s[i]) % p == 0:
			ans += i + 1
	print(ans)


(N, P) = map(int, input().split())
S = input()
ans = 0
rui = [0] * (N + 1)
if 10 % P == 0:
	for i in range(len(S)):
		if int(S[i]) % P == 0:
			ans += i + 1
	print(ans)
	exit()
t = 1
for i in reversed(range(N)):
	tmp = int(S[i]) * t % P
	rui[i] = (rui[i + 1] + tmp) % P
	t *= 10
	t %= P
cnt = [0] * P
for i in reversed(range(N + 1)):
	ans += cnt[rui[i]]
	cnt[rui[i]] += 1
print(ans)


(N, P) = map(int, input().split())
S = input()
answer = 0
if P == 2 or P == 5:
	for i in range(N):
		si = int(S[i])
		if si % P == 0:
			answer += i + 1
else:
	mod_table = [0] * P
	mod_table[0] = 1
	revS = S[::-1]
	modp = 0
	mod10 = 1
	for i in range(N):
		mod10 = mod10 * 10 % P
		modp = (modp + mod10 * int(revS[i])) % P
		mod_table[modp] += 1
	for i in range(P):
		answer += mod_table[i] * (mod_table[i] - 1) // 2
print(answer)


(n, p) = map(int, input().split())
s = input()
if p == 2 or p == 5:
	ans = 0
	for i in range(n):
		if int(s[i]) % p == 0:
			ans += i + 1
	print(ans)
else:
	res = 0
	cnt = [0] * p
	for i in range(n):
		res = (res + int(s[n - 1 - i]) * pow(10, i, p)) % p
		cnt[res] += 1
	ans = 0
	for c in cnt:
		ans += c * (c - 1) // 2
	ans += cnt[0]
	print(ans)


(N, P) = map(int, input().split())
S = input()
ans = 0
mod = [0] * P
if P == 2 or P == 5:
	for i in range(N):
		if int(S[i]) % P == 0:
			ans += i + 1
	print(ans)
else:
	un1 = 0
	un = 0
	for i in range(N - 1, -1, -1):
		a = int(S[i]) * pow(10, un, P) + un1 % P
		un += 1
		un1 = a
		mod[a % P] += 1
	ans += mod[0]
	for i in range(P):
		ans += mod[i] * (mod[i] - 1) / 2
	print(int(ans))


(n, p) = map(int, input().split())
s = list(map(int, input()))
if p == 2 or p == 5:
	r = 0
	for i in range(n):
		if s[i] % p == 0:
			r += i + 1
	print(r)
else:
	c = 0
	cnt = [0] * p
	cnt[0] += 1
	for k in range(len(s) - 1, -1, -1):
		c = (c + s[k] * pow(10, len(s) - 1 - k, p)) % p
		cnt[c] += 1
	print(sum((x * (x - 1) // 2 for x in cnt)))


(N, P) = map(int, input().split())
S = input()
sn = int(S)
if P == 2:
	ans = 0
	for i in range(1, N + 1):
		if int(S[-i]) % 2 == 0:
			ans += N - i + 1
	print(ans)
	exit()
if P == 5:
	ans = 0
	for i in range(1, N + 1):
		if int(S[-i]) % 5 == 0:
			ans += N - i + 1
	print(ans)
	exit()
amari = [0] * P
amari[0] = 1
mod = 0
for i in range(1, N + 1):
	mod = (mod + int(S[-i]) * pow(10, i - 1, P)) % P
	amari[mod] += 1
ans = 0
for tmp in amari:
	ans += tmp * (tmp - 1) // 2
print(ans)


(n, p) = map(int, input().split())
s = input()
ans = 0
if p == 2:
	for i in range(n):
		if s[i] in ['0', '2', '4', '6', '8']:
			ans += i + 1
elif p == 5:
	for i in range(n):
		if s[i] in ['0', '5']:
			ans += i + 1
else:
	mod = [1] + [0] * (p - 1)
	a = 0
	for i in range(n):
		si = int(s[n - 1 - i])
		a = si * pow(10, i, p) + a
		mod[a % p] += 1
	ans = sum((m * (m - 1) // 2 for m in mod))
print(ans)


(n, p) = list(map(int, input().split()))
s = input()
res = 0
if p == 2 or p == 5:
	for i in range(n):
		if int(s[i]) % p == 0:
			res += i + 1
else:
	s = s[::-1]
	cnt = {0: 1}
	now = 0
	d = 1
	for i in range(n):
		now = (now + int(s[i]) * d) % p
		res += cnt.get(now, 0)
		d = d * 10 % p
		cnt[now] = cnt.get(now, 0) + 1
print(res)


from collections import Counter
(n, p) = map(int, input().split())
s = input()
cnt = 0
if p == 2 or p == 5:
	for i in range(n):
		if int(s[i]) % p == 0:
			cnt += i + 1
else:
	U = [0] * (n + 1)
	for i in range(n, 0, -1):
		U[i - 1] = (int(s[i - 1]) * pow(10, n - i, p) + U[i]) % p
	C = Counter(U)
	for c in C.values():
		cnt += c * (c - 1) // 2
print(cnt)


(n, p) = map(int, input().split())
s = list(map(int, list(input()[::-1])))
if p in [2, 5]:
	ans = 0
	for i in range(n):
		if s[-i - 1] % p == 0:
			ans += i + 1
	print(ans)
	exit()
from collections import defaultdict
d = defaultdict(int)
t = 0
d[t] += 1
m = 1
for i in range(n):
	t += m * s[i]
	t %= p
	d[t] += 1
	m *= 10
	m %= p
print(sum((d[i] * (d[i] - 1) // 2 for i in range(p))))


(n, p) = map(int, input().split())
s = input()
ans = 0
if p == 2 or p == 5:
	for (i, c) in enumerate(s, 1):
		if int(c) % p == 0:
			ans += i
else:
	cnt = [0] * p
	cnt[0] = 1
	x = 0
	d = 1
	for c in s[::-1]:
		x += d * int(c)
		x %= p
		cnt[x % p] += 1
		d *= 10
		d %= p
	for v in cnt:
		ans += v * (v - 1) // 2
print(ans)


(N, P) = map(int, input().split())
S = input()
T = [0] * (N + 1)
T[0] = 0
e = 1
for i in range(N):
	T[i + 1] = T[i] + int(S[N - i - 1]) * e
	T[i + 1] %= P
	e *= 10
	e %= P
a = {}
for i in range(N + 1):
	if T[i] in a:
		a[T[i]] += 1
	else:
		a[T[i]] = 1
num = 0
if P % 2 == 0 or P % 5 == 0:
	for i in range(N):
		if int(S[i]) % P == 0:
			num += 1 + i
else:
	for k in a:
		num += a[k] * (a[k] - 1) // 2
print(num)


(n, p) = map(int, input().split())
s = input()
ans = 0
if p in (2, 5):
	for (i, j) in enumerate(s):
		if int(j) % p == 0:
			ans += i + 1
else:
	cnt = [0] * p
	cnt[0] = 1
	now = 0
	for (i, j) in enumerate(reversed(s)):
		now = (int(j) * pow(10, i, p) + now) % p
		ans += cnt[now]
		cnt[now] += 1
print(ans)


def main():
	import sys
	input = sys.stdin.readline
	sys.setrecursionlimit(10 ** 7)
	from collections import Counter, deque
	from itertools import combinations, permutations, accumulate, groupby, product
	from bisect import bisect_left, bisect_right
	from heapq import heapify, heappop, heappush
	import math
	(s, p) = list(map(int, input().split()))
	n = input().rstrip()
	n = n[::-1]
	if p == 2 or p == 5:
		res = 0
		for i in range(s):
			a = int(n[i])
			if a % p == 0:
				res += s - i
		print(res)
	else:
		res = [0] * p
		res[0] += 1
		b = 1
		c = 0
		for i in range(s):
			a = int(n[i])
			c += a * b
			c %= p
			res[c] += 1
			b = b * 10 % p
		ans = 0
		for i in res:
			if i >= 2:
				ans += i * (i - 1) // 2
		print(ans)

def __starting_point():
	main()
__starting_point()


def main():
	(N, P) = list(map(int, input().split()))
	A = list(map(int, input()))
	if 10 % P == 0:
		ret = 0
		for (i, x) in enumerate(reversed(tuple(A)), start=0):
			if x % P == 0:
				ret += N - i
		print(ret)
		return
	ctr = [0] * P
	ctr[0] = 1
	ret = 0
	t = 0
	c = 1
	for x in reversed(tuple(A)):
		t = (t + c * x) % P
		ret += ctr[t]
		ctr[t] += 1
		c = c * 10 % P
	print(ret)

def __starting_point():
	main()
__starting_point()


(n, p) = map(int, input().split())
s = list(map(int, list(input())))
if p in [2, 5]:
	ans = 0
	for (i, x) in enumerate(s):
		if x % p == 0:
			ans += i + 1
	print(ans)
	exit()
x = [0] * p
x[0] = 1
temp = 0
d = 1
for i in range(n - 1, -1, -1):
	temp = (temp + s[i] * d) % p
	x[temp] += 1
	d = d * 10 % p
ans = 0
for z in x:
	ans += z * (z - 1) // 2
print(ans)


(n, p) = map(int, input().split())
s = list(map(int, list(input())))[::-1]
div = [0 for _ in range(p)]
su = 0
for i in range(n):
	su = (su + s[i] * pow(10, i, p)) % p
	div[su] += 1
cnt = 0
if p in [2, 5]:
	if p == 2:
		ok = [0, 2, 4, 6, 8]
	else:
		ok = [0, 5]
	for i in range(len(s)):
		if s[i] in ok:
			cnt += n - i
else:
	for i in range(len(div)):
		x = div[i]
		if i == 0:
			y = x * (x + 1) // 2
		else:
			y = x * (x - 1) // 2
		cnt += y
print(cnt)


(N, P) = map(int, input().split())
S = input()
U = [0] * P
ans = 0
if P == 2 or P == 5:
	for i in range(0, N):
		if int(S[i]) % P == 0:
			ans += i + 1
	print(ans)
else:
	(t, s) = (0, 1)
	for i in range(N - 1, -1, -1):
		t = (int(S[i]) * s + t) % P
		U[t] += 1
		s = s * 10 % P
	for u in U:
		ans += u * (u - 1) // 2
	ans += U[0]
	print(ans)


import sys
import collections
(n, p) = map(int, input().split())
s = list(input())
s.reverse()
ans = 0
if p == 2:
	for i in range(n):
		if int(s[i]) % 2 == 0:
			ans += n - i
	print(ans)
	sys.exit()
if p == 5:
	for i in range(n):
		if int(s[i]) % 5 == 0:
			ans += n - i
	print(ans)
	sys.exit()
l = [0, int(s[0]) % p]
x = int(s[0])
y = 1
for i in range(1, n):
	y *= 10
	y %= p
	x += y * int(s[i]) % p
	x %= p
	l.append(x)
L = collections.Counter(l)
for j in L.values():
	ans += j * (j - 1) // 2
print(ans)