Problem:
 Score : 500 points    Problem Statement 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 1 4 3
3543      Sample Output 1 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 .       Sample Input 2 4 2
2020      Sample Output 2 10  Here S = 2020 . There are ten non-empty (contiguous) substrings of S , all of which are divisible by 2 , so print 10 .  Note that substrings beginning with a 0 also count.       Sample Input 3 20 11
33883322005544116655      Sample Output 3 68

Solution (Python):
from collections import defaultdict

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

mod = p

if mod < 10:
    d = {0:0}
    ans = 0
    for i in t:
        nxt = defaultdict(int)
        for key,value in d.items():
            nxt[(key*10 + i)%mod] += value
        nxt[i%mod] += 1
        ans += nxt[0]
        d = nxt
    print(ans)
else:
    cnt = [0]*mod
    f = 1
    ans = 0
    cur = 0
    for i in reversed(range(n)):
        cur += f*t[i]
        cur %= mod
        ans += cnt[cur]
        cnt[cur] += 1
        if cur == 0:
            ans += 1
        f *= 10
        f %= mod
    print(ans)

Solution (Python):
n, p = map(int, input().split())
s = list(reversed(list(map(int, input()))))
if p == 2:
    ans = 0
    s = list(reversed(s))
    for i in range(n):
        if s[i] % 2 == 0:
            ans += i + 1
    print(ans)
    exit()
if p == 5:
    ans = 0
    s = list(reversed(s))
    for i in range(n):
        if s[i] % 5 == 0:
            ans += i + 1
    print(ans)
    exit()
cur = 1
c = [0] * (n + 1)
ans = 0
t = [0] * p
t[c[0]] += 1
for i in range(n):
    c[i + 1] = (c[i] + cur * s[i]) % p
    ans += t[c[i + 1]]
    t[c[i + 1]] += 1
    cur = cur * 10 % p
print(ans)

Solution (Python):
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)

Solution (Python):
N, P = map(int, input().split())

S = input()

total = 0
if P == 2 or P == 5:
	for i, s in enumerate(S):
		if int(s) % P == 0:
			total += i + 1
else:
	counts = [0] * P
	counts[0] = 1
	h = 0
	
	d = 1
	for s in reversed(S):
		m = int(s) * d % P
		h = (h + m) % P
		total += counts[h]
		counts[h] += 1
		d = (d * 10) % P



print(total)

Solution (Python):
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)

Solution (Python):
n,p=map(int,input().split())
s=input()
ans=0
if(p==2 or p==5):
    kensa=["0","2","4","6","8"]
    if(p==5):
        kensa=["0","5"]
    for i in range(n):
        if(s[i] in kensa):
            ans+=i+1
else:
    amari=0
    ju=1

    cnt=[0]*p
    cnt[0]=1

    for i in range(n):
        amari+=int(s[n-i-1])*ju
        amari%=p
        ju=(ju*10)%p
        cnt[amari]+=1
    for c in cnt:
        if(c==0 or c==1):
            continue
        ans+=c*(c-1)//2
print(ans)

Solution (Python):
n,p=map(int,input().split())
if p==2:
    l=[int(c) for c in input()]
    res=0
    for i in range(n):
        if (l[i]%2)==0:
            res+=i+1
    print(res)
elif p==5:
    l=[int(c) for c in input()]
    res=0
    for i in range(n):
        if (l[i]==0)or(l[i]==5):
            res+=i+1
    print(res)
else:
    s=input()[::-1]
    l=[int(c) for c in s]
    ll=[0 for i in range(p)]
    now=0
    fac=1
    for i in l:
        now+=fac*i
        now%=p
        ll[now]+=1
        fac*=10
        fac%=p
    res=0
    for i in range(p):
        res+=ll[i]*(ll[i]-1)//2
    res+=ll[0]
    print(res)

Solution (Python):
def examA():
    S = SI()
    if S=="AAA" or S=="BBB":
        print("No")
    else:
        print("Yes")
    return

def examB():
    N, A, B = LI()
    loop = N//(A+B)
    ans = loop*A + min(A,N%(A+B))
    print(ans)
    return

def examC():
    A, B = LI()
    ans = -1
    for i in range(1,20000):
        if i*8//100==A:
            if i*10//100==B:
                ans = i
                break
    print(ans)
    return

def examD():
    S = SI()
    Q = I()
    rev = 0
    L = ""; R = ""
    for _ in range(Q):
        q = LSI()
        if q[0]=="1":
            rev += 1
        else:
            c = int(q[1])
            if (c+rev)%2==1:
                L += q[2]
            else:
                R += q[2]
    ans = ""
    if rev%2==0:
        ans = L[::-1] + S + R
    else:
        ans = R[::-1] + S[::-1] + L
    print(ans)
    return

def examE():
    N, P = LI()
    S = SI()
    A = [0]*(N+1)
    cur = 0
    if P==5:
        ans = 0
        for i in range(N):
            if int(S[N-1-i])%5==0:
                ans += N-i
        print(ans)
        return
    elif P==2:
        ans = 0
        for i in range(N):
            if int(S[N-1-i])%2==0:
                ans += N-i
        print(ans)
        return

    for i in range(N):
        s = int(S[N-1-i])
        cur += s*pow(10,i,P)
        A[i+1] = cur%P
    D = [0]*P
    for a in A:
        D[a] += 1
    ans = 0
    
    for d in D:
        ans += d*(d-1)//2

    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math,random
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**6)

if __name__ == '__main__':
    examE()

"""

"""

Solution (Python):
n, p = map(int, raw_input().strip().split())
s = raw_input().strip()

if p == 2:
    ans = 0
    for i in xrange(n):
        if s[i] in '02468':
            ans += (i + 1)
    print ans
    exit()

if p == 5:
    ans = 0
    for i in xrange(n):
        if s[i] in '05':
            ans += (i + 1)
    print ans
    exit()

n = len(s)
l = [0 for i in xrange(n + 1)]

l[n] = int(s[n - 1])
if l[n] >= p: l[n] %= p

p10 = 1
for i in xrange(n - 1, 0, -1):
    p10 *= 10
    if p10 >= p: p10 %= p
    l[i] = p10 * (ord(s[i - 1]) - ord('0'))
    if l[i] >= p: l[i] %= p

cnt = [0 for i in xrange(p)]
cnt[l[0]] += 1
for i in xrange(1, n + 1):
    l[i] += l[i - 1]
    if l[i] >= p: l[i] -= p

    cnt[l[i]] += 1

ans = 0
for i in xrange(p):
    ans += ((cnt[i] * (cnt[i] - 1)) / 2)

print ans

Solution (Python):

import sys
input = sys.stdin.readline

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

if p == 2 or p == 5:
    ans = 0
    for i, item in enumerate(s):
        if int(item) % p == 0:
            ans += (i + 1)
else:
    mods = [0]
    s = s[::-1]
    mod = 0
    for i, ch in enumerate(s):
        mod = (mod + int(ch) * pow(10, i, p))  % p
        mods.append(mod)
    
    cnt = [0] * p
    for item in mods:
        cnt[item] += 1
    ans = 0
    for item in cnt:
        ans += item * (item - 1) // 2
print(ans)

Solution (Python):
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)

Solution (Python):
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

N,P = inpl()
S = list(map(int,list(input())))

if 10%P==0:
    ans= 0
    for i,s in enumerate(S):
        if s%P == 0:
            ans += i+1
    print(ans)
else:
    tmpl = [s*pow(10,N-1-i,P)%P for i,s in enumerate(S)]
    xx = [tmpl[0]]
    for t in tmpl[1:]:
        xx.append((xx[-1]+t)%P)

    yy = [S[0]%P]
    for s in S[1:]:
        yy.append((yy[-1]*10+s)%P)

    nums = [0]*P
    nums[0] += 1
    ans = 0
    for i,y in enumerate(yy):
        tmp = y*pow(10,N-1-i,P)%P
        ans += nums[tmp]
        nums[xx[i]] += 1
    print(ans)

Solution (Python):
from collections import defaultdict
n,p = map(int,input().split())
s = list(input())
s = [int(x) for x in s][::-1]
if p != 2 and p != 5:
    ans = 0
    data = [0 for _ in range(p)]
    now = 1
    data[0] = 1
    a = 0
    for i in range(n):
        a += now*s[i]
        a %=p
        data[a]+=1
        now *= 10
        now %= p
    for x in data:
        ans += x*(x-1)//2
    print(ans)
if p == 2:
    ans = 0
    for i,x in enumerate(s[::-1]):
        if x%2 == 0:
            ans += i+1
    print(ans)
if p == 5:
    ans = 0
    for i,x in enumerate(s[::-1]):
        if x%5 == 0:
            ans += i+1
    print(ans)

Solution (Python):
n, p = map(int, input().split())
s = [int(x) for x in input()]

if p == 2:
    ans = 0
    for i in range(n):
        if s[i] % 2 == 0:
            ans += i+1
    print(ans)
    exit()

if p == 5:
    ans = 0
    for i in range(n):
        if s[i] == 0 or s[i] == 5:
            ans += i+1
    print(ans)
    exit()


po10 = [1]
for i in range(n-1):
    po10.append((po10[-1]*10) % p)

for i in range(n):
    s[i] *= po10[n-1-i]
    s[i] %= p

ss = [0]

for i in range(n):
    ss.append(ss[-1]+s[i])
    ss[-1] %= p


ss = sorted(ss)

ll = len(ss)

ans = 0
tmp = [0,0]
for i in range(ll):
    if ss[i] != tmp[0]:
        ans += (i-tmp[1])*(i-tmp[1]-1) //2
        tmp[0] = ss[i]
        tmp[1] = i

ans += (ll-tmp[1])*(ll-tmp[1]-1)//2

print(ans)

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

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

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

if P != 2 and P != 5:
    p_array = [0] * P
    mod = 0
    amari = 1
    for i, s in enumerate(S[::-1]):
        s = int(s)
        mod = (mod + s * amari) % P
        amari = amari * 10 % P
        p_array[mod] += 1

    ans = 0
    for i, p in enumerate(p_array):
        if i == 0:
            ans += p
        ans += (p * (p-1) // 2)

    print(int(ans))

else:
    ans = 0
    for i, s in enumerate(S):
        if int(s) % P == 0:
            ans += (i+1)
    print(ans)

Solution (Python):
import sys
input = sys.stdin.readline

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

if P==2:
    L=[int(s)%2 for s in S[::-1]]

    ANS=0
    for i in range(N):
        if L[i]==0:
            ANS+=N-i
    print(ANS)

elif P==5:
    L=[int(s)%5 for s in S[::-1]]

    ANS=0
    for i in range(N):
        if L[i]==0:
            ANS+=N-i
    print(ANS)

else:   
    L=[0]
    NOW=1
    for i in range(N):
        L.append((L[-1]+int(S[N-i-1])*NOW)%P)
        NOW=NOW*10%P

    from collections import Counter
    C=Counter(L)
    ANS=0

    for i in range(N):
        ANS+=C[L[i]]-1
        C[L[i]]-=1
    print(ANS)

Solution (Python):
from itertools import accumulate,chain
from collections import defaultdict


def solve(N,P,S):
    S = list(map(int,S))

    if P == 2:
        cnt = 0
        for i,n in enumerate(S):
            if n%2 == 0:
                cnt += i+1
        return cnt
    elif P == 5:
        cnt = 0
        for i,n in enumerate(S):
            if n%5 == 0:
                cnt += i+1
        return cnt


    n = 1
    T = [None]*N
    for i in reversed(range(N)):
        T[i] = (n*S[i])%P
        n *= 10
        n %= P
    T = tuple(chain((0,),accumulate(T, lambda a,b: (a+b)%P)))



    cnt = 0
    c = defaultdict(int)
    for t in T:
        cnt += c[t]
        c[t] += 1
    return cnt

if __name__ == '__main__':

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

Solution (Python):
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
else:
    s2 = s[::-1]
    rems = [0]
    tmp = 0
    tmp2 = 1
    for i in range(n):
        tmp += int(s2[i]) * tmp2
        tmp %= p
        tmp2 *= 10
        tmp2 %= p
        rems.append(tmp)

    from collections import Counter
    counter = Counter(rems)
    ans = 0
    for key in counter.keys():
        v = counter[key]
        ans += v * (v - 1) // 2
print(ans)

Solution (Python):
from collections import Counter
N, P = map(int, input().split())
if P not in [2,5]:
  pt = [1]
  for i in range(N):
    pt.append(pt[-1]*10%P)
  S = [int(c)%P for c in input()]
  dp = [(S[0]*pt[N-1])%P]
  for i in range(1,N):
    dp.append((dp[-1]+S[i]*pt[N-1-i])%P)

  c = Counter(dp)
  ans = sum(u*(u-1)//2 for u in c.values())
  print(ans+c[0])
elif P==2:
  S = [int(c) for c in input()]
  ans = 0
  for i in range(N):
    if S[i]%2==0:
      ans += i+1
  print(ans)
else:
  ans = 0
  S = [int(c) for c in input()]
  for i in range(N):
    if S[i]%5==0:
      ans += i+1
  print(ans)

Solution (Python):
from itertools import accumulate

def equalfind(A):
    A.sort()
    s=1
    count=0
    if len(A)==1:
        return count
    else:
        for i in range(0,len(A)-1):
            if A[i]==A[i+1]:
                s+=1
            else:
                count+=s*(s-1)//2
                s=1
        return count+s*(s-1)//2

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

def pow(x, n):
  ans = 1
  while(n > 0):
    if(bin(n & 1) == bin(1)):
      ans = (ans*x)%P
    x = (x*x)%P
    n = n >> 1 
  return ans%P

if P!=2 and P!=5:
    data=[(int(S[i])*(pow(10,N-1-i)))%P for i in range(0,N)]
    ans=list(accumulate(data))
    ans=[ans[i]%P for i in range(0,N)]
    ans.append(0)
    print(equalfind(ans))
elif P==2:
    ans=0
    for i in range(0,N):
        if int(S[i])%2==0:
            ans+=i+1
    print(ans)
else:
    ans=0
    for i in range(0,N):
        if int(S[i])%5==0:
            ans+=i+1
    print(ans)

Solution (Python):
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)
elif p == 5:
    ans = 0
    for i in range(n):
        if int(s[i]) % 5 == 0:
            ans += (i + 1)
else:
    a = [1]
    for i in range(n - 1):
        a.append(a[-1] * 10 % p)
    a.reverse()
    b = [int(s[i]) * a[i] % p for i in range(n)]
    c = [0]
    for i in range(n):
        c.append((c[-1] + b[i]) % p)
    d = {}
    for i in c:
        d.setdefault(i, 0)
        d[i] += 1
    ans = 0
    for i in d.values():
        ans += i * (i - 1) // 2
print(ans)

Solution (Python):
from collections import Counter
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)
    exit()
if p==5:
    ans=0
    for i in range(n):
        if int(s[i])%5==0:
            ans += i+1
    print(ans)
    exit()


accm = [0]
s = s[::-1]

sm = 0
beki_p = 1
for i in range(n):
    sm += int(s[i])*beki_p
    sm %=p
    accm.append(sm)
    beki_p *=10
    beki_p%=p

aC = Counter(accm)
ans = 0
for k in aC:
    ans += aC[k]*(aC[k]-1)//2
print(ans)

Solution (Python):
import sys
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)
    sys.exit()

res = 0
cnt = [0]*p
for i in range(n):
    res = (res+int(s[-i-1])*pow(10, i, p))%p
    cnt[res]+=1
ans = 0
for c in cnt:
    ans+=c*(c-1)//2
ans+=cnt[0]
print(ans)

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,p = LI()
    s = list(map(int, input()))
    if p in [2,5]:
        ans = 0
        for i in range(n):
            si = s[i]
            if si%p == 0:
                ans += i+1
        print(ans)
        return
    a = [0]
    k = pow(10,p-2,p)
    K = k
    for i in range(n):
        si = s[i]
        a.append((a[-1]+si*K)%p)
        K *= k
        K %= p
    ans = 0
    d = defaultdict(lambda : 0)
    for i in a:
        ans += d[i]
        d[i] += 1
    print(ans)
    return


if __name__ == "__main__":
    solve()

Solution (Python):
def main():
    import sys
    from collections import Counter
    input = sys.stdin.readline

    N, mod = map(int, input().split())
    S = input().rstrip('\n')

    if mod == 2 or mod == 5:
        S = S[::-1]
        ans = 0
        for i, s in enumerate(S):
            s = int(s)
            if s%mod == 0:
                ans += N - i
        print(ans)
        exit()

    M = [0] * N
    S = S[::-1]
    for i, s in enumerate(S):
        s = int(s)
        M[i] = (M[i-1] + (s * pow(10, i, mod))%mod)%mod
    M.reverse()
    M.append(0)
    C = Counter(M)
    ans = 0
    for x in C:
        ans += (C[x] * (C[x]-1)) // 2
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
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))

Solution (Python):
n,p = map(int,input().split())
pr = [0 for _ in range(p)]
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()
ten = [1]
for i in range(n-1):
  ten.append(ten[-1]*10%p)
ten.reverse()

pr[0] = 1
now = 0
for i in range(n):
  now *= 10
  now += int(s[i])
  now %= p
  tmp = int(now)
  tmp *= ten[i]
  tmp %= p
  pr[tmp] += 1

ans = 0
for x in pr:
  ans += x * (x-1)
ans //= 2
print(ans)

Solution (Python):
n, p = map(int, input().split())
s = input()
ans = 0
if p == 2 or p == 5:
    if p == 2:
        ok = [0, 2, 4, 6, 8]
    else:
        ok = [0, 5]
    for i, c in enumerate(s):
        if int(c) in ok:
            ans += i+1
    print(ans)
    exit()

s = s[::-1]
cum = [0] * (n+1)
keta = 1
for i, c in enumerate(s):
    cum[i+1] = cum[i] + keta * int(c)
    cum[i+1] %= p
    keta = (keta * 10) % p
counter = [0] * p
for c in cum:
    counter[c] += 1
for c in counter:
    ans += c * (c-1)//2
print(ans)

Solution (Python):
def calc(S, P):
    ans = 0
    if P == 2 or P == 5:
        for i, s in enumerate(S):
            if int(s) % P == 0:
                ans += i + 1
        return ans
    else:
        C = [0] * P
        C[0] = 1
        a = 0
        for i, s in enumerate(S[::-1]):
            a = (a + int(s) * pow(10, i, P)) % P
            ans += C[a]
            C[a] += 1
        return ans

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

Solution (Python):
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)

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

S = S[::-1]

if P!=2 and P!=5:

    current = 1

    SP = []

    for i in range(N):
        SP.append((int(S[i])*current)%P)
        current*=10
        current%=P

    SSP = [0]
    s = 0
    for i in range(N):
        s+=SP[i]
        s%=P
        SSP.append(s)

    from collections import Counter

    counter = Counter(SSP)
    ans = 0
    for key in counter:
        ans += (counter[key]*(counter[key]-1))//2

    print(ans)
else:
    ans = 0
    for i in range(N):
        if int(S[i])%P==0:
            ans+=N-i
    print(ans)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from collections import Counter

N, P = map(int, readline().split())
S = list(map(int, read().rstrip().decode()))

def solve_2(S):
    ind = (i for i, x in enumerate(S, 1) if x % 2 == 0)
    return sum(ind)

def solve_5(S):
    ind = (i for i, x in enumerate(S, 1) if x % 5 == 0)
    return sum(ind)

def solve(S,P):
    if P == 2:
        return solve_2(S)
    if P == 5:
        return solve_5(S)
    S = S[::-1]
    T = [0] * len(S)
    T[0] = S[0] % P
    power = 1
    for i in range(1, len(S)):
        power *= 10
        power %= P
        T[i] = T[i-1] + power * S[i]
        T[i] %= P
    counter = Counter(T)
    return sum(x * (x - 1) // 2 for x in counter.values()) + counter[0]


print(solve(S,P))

Solution (Python):
n, p = 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)

Solution (Python):
from collections import Counter
from itertools import accumulate
import sys
input = sys.stdin.readline
n,p = map(int,input().split())
s = input().rstrip()
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 int(s[i])%5 == 0:
      ans += i+1
  print(ans)
else:
  ls = [0]
  prev = 0
  for i in range(n):
    x = int(s[n-i-1])
    y = (prev+x*pow(10,i,p))%p
    ls.append(y)
    prev = y
  c = Counter(ls)
  ans = 0
  for x in c.values():
    ans += x*(x-1)//2
  print(ans)

Solution (Python):
from collections import Counter
 
rr = raw_input
rri = lambda: int(rr())
rrm = lambda: map(int, rr().split())
 
def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)
 
def modinv(a, m):
    g, x, y = egcd(a, m)
    return x % m
 
def solve(N, P, S):
    A = map(int, S)
    if P == 2 or P == 5:
        ans = 0
        for i, x in enumerate(A):
            if x % P == 0:
                ans += i + 1
        return ans

    powers = [0] * N
    pwr = 1
    for i in xrange(N-1, -1, -1):
        powers[i] = pwr
        pwr *= 10; pwr %= P

    
    count = Counter()
    count[0] += 1
    s = 0
    ans = 0
    for i in xrange(N-1, -1, -1):
        w = A[i] * powers[i] % P
        s += w; s %= P
        ans += count[s]
        count[s] += 1
        
    return ans
 
 
N, P = rrm()
print solve(N, P, rr())

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
read = sys.stdin.read

n,p = [int(i) for i in readline().split()]
s = input()

if p==2 or p==5:
    ans = 0
    for i,c in enumerate(s):
        if int(c)%p==0:
            ans += i+1
    print(ans)
    exit()
            



res = [0]*p
res[0] = 1
t = 1
now = 0
for i in s[::-1]:
    i = int(i)
    now += i*t
    now %= p
    res[now] += 1
    t = t*10%p

ans = 0    
for i in res:
    ans += i*(i-1)//2

print(ans)

Solution (Python):
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)

Solution (Python):
import sys
from collections import defaultdict

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  

n, p = na()
s = ns()

if p != 2 and p != 5:
    a = []
    t = 1
    for i in range(n-1, -1, -1):
        a.append((ord(s[i])-ord("0")) * t % p)
        t = t * 10 % p
    cum = [0]
    for v in a:
        cum.append((cum[-1] + v) % p)

    dic = defaultdict(int)
    ans = 0
    for v in cum:
        ans += dic[v]
        dic[v] += 1
    print(ans)
elif p == 2:
    ans = 0
    for i in range(n):
        if (ord(s[i]) - ord("0")) % 2 == 0:
            ans += i+1
    print(ans)
else:
    ans = 0
    for i in range(n):
        if (ord(s[i]) - ord("0")) % 5 == 0:
            ans += i+1
    print(ans)