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: interview

Starter code:

Solutions:
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()
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)

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 i in range(N):
    c[mods[i]] -= 1
    ans += c[mods[i]]

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)
    return

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

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)))


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 = 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())
S = str(input())
L = len(S)
ans = 0
dic = {0:1} #一番右端は0なのでこれは常に必要
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
#print(dic)
ans = 0  
for i in dic.values():
  if i != 1:
    ans += i*(i-1)//2
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)


n, p = [int(i) for i in input().split()]
s = [int(i) for i in list(input())][::-1]
summ  = 0
ans = 0
cnt = [0]*p # あまりの部屋
cnt[0] = 1
for i in range(n):
    d = s[i]*pow(10, i ,p)
    summ = (summ + d) %p
    cnt[summ] +=1

if p in [2,5]: # 10の因数は別処理
    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: # 他のは,あまりが同じものは差し引けばあまりが0になるのでpで割り切れる判定
    for i in range(p):
        ans += cnt[i] * (cnt[i]-1)//2 # nC2の計算

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)
  return
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)

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 = 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)


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
#print(l)
c = Counter(l)
#print(c)
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)

n, p = list(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)


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)

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()

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()
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)

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()[::-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)



#!python3

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

# input
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()

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)

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= 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)

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)


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 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)

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:  #10と素でない場合一番右の桁で決まる
    ans = 0
    for i in range(N):
        if S[i] % P == 0:
            ans += i+1
    print(ans)
    return

A = [0]  #A[i] = 下i桁をPで割った余り
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)

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)

'''ika tako　　ABC164Dの類題
基本は、1桁目、2桁目と下から10進数の数字として見て、
素数ｐで割った余りを考え、余りが同じである数字のスタートとエンドを
選ぶ組み合わせの数が答。
但し、10進数で考えているので、ｐが2と5のケースは別扱い。
末尾が2、5の倍数なら2の倍数。先頭の数字を0番目として、
i番目に2、5の倍数が出てきたら、
そこを右端とする部分文字列は i+1  個作れる。
'''
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))

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,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)

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 S[i] == "0" or S[i] == "5":
            ans += i+1
else:
    L = [0]*P
    num = 0
    for i in range(N):
        num += int(S[N-i-1])*pow(10, 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 = list(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)
  return
for i in range(p):
  ans += (c[i]*(c[i]-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
# print(t)
for i,x in enumerate(t):
    tmp = (pow(10,i,p) * int(x)) % p
    now += tmp
    now %= p
    d[now] += 1
# print(d)
for va in d.values():
    res += va*(va-1)//2
print(res)

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

#ep(d)

for i in range(N,-1,-1):
    ans += cnt[d[i]]
    cnt[d[i]] += 1;
    #ep(i,ans,cnt)
#ep(cnt)
print(ans)

from collections import Counter
N, P = list(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 list(C.values()):
        ans += v * (v - 1) // 2
    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: # Case when only last digit matters
    for j in range(N - 1, -1, -1): # Enumerate right endpoint
        if S[j] % P == 0:
            answer += j + 1
else: 
    # Enuerate left endpoint from right to left
    # Find number of right endpoints that make the substr % P == 0
    cnts = defaultdict(int)
    suffix = 0
    base = 1
    for i in range(N - 1, -1, -1):
        suffix = (suffix + S[i] * base) % P
        answer += cnts[suffix]  # Substr with length >= 2
        answer += 1 if suffix == 0 else 0 # Substr with length = 1
        cnts[suffix] += 1
        base = base * 10 % P

print(answer)

from collections import Counter

N, P = list(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)


N,P = list(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 = 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)


# coding: utf-8
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)

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math

    #inf = 10**17
    #mod = 10**9 + 7

    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()

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:
                # 以降桁を増やしてもOK
                c += i+1
        return c
    print(solve25(N, P, S))
else:
    def solve(N, P, S):
        rcounts = [0] * P
        rcounts[0] = 1 # sそのものが割り切れた場合に引き算する相手がいないから
        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 = 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 *
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)



def m():
    n,p=list(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)
def __starting_point():
    m()

__starting_point()

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
    # print(cnt)
    for v in cnt: ans += v*(v-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):
        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)

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 = 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)




n, p = 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):  # handling of 0's as n and rem
        n = int(s[i]) * power + rem
        power *= 10
        power = power % p
        rem = n % p
        if rem in d.keys():
            d[rem] += 1
        else:
            d[rem] = 1
        total += d[rem] - 1
    print(total + d[0])

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 = list(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)


#E
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)



# E - Divisible Substring
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)

#!/usr/bin/env python3
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)


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 = list(map(int, input().split()))
s = list(map(int, input().strip()))

count = 0

if(p == 2 or p == 5): #10と互いに素ではない場合
    co = 0
    for i in range(n): #1の位から順に数を追加していく
        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,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)


"""
s=1817181712114 なら
4
10
100
2000
10000
700000
1000000
80000000
100000000
7000000000
10000000000
800000000000
1000000000000
の数列とみて, 各々%Pを取ってzero sum range
P=2,5がコーナー
"""
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)

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))

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
# print(S, cnt)

# ans = cnt[0] * (cnt[0] - 1) // 2
for c in cnt:
    ans += c * (c - 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()

from collections import defaultdict


def main():
    N, P = list(map(int, input().split()))
    S = input()
    if P in [2, 5]:
        ans = 0
        # P = 2, 5の時は一番下の位の数だけ見ればカウント可能
        for right in range(N - 1, - 1, - 1):
            if int(S[right]) % P == 0:
                ans += right + 1
        print(ans)
        return
    # 例：S = 3543, P = 3
    # 左からn番目 ～ 1番右の数のmod Pの値を計算
    #     C = [3543, 543, 43, 3] % P = [0, 0, 1, 0]
    # C[m] == C[n] なる m < nのペア数 + C[n] == 0なるnの個数を求める
    #     3 + 3 = 6
    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 = 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)     

import sys
## io
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()))
## dp
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)]
## math
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: # pが2または5の場合
        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 # 0(mod p)はそれ単体で割り切れるため+1しておく
    ss = 0
    x = 1
    for si in s[::-1]:
        ss += x*si
        ss %= p
        d[ss] += 1
        x = (10*x)%p # %p無しだとTLE
    cnt = 0
    for di in d:
        cnt += di*(di-1)//2 # calc combination(n_C_2)
    print(cnt)


def __starting_point():
    main()
__starting_point()

import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
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 = input()

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:
  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
  for key in c:
    ans += c[key]*(c[key]-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:
  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)

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()

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): # enumerate right endpoint
        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]  # Substr with length >= 2
        answer += 1 if suffix == 0 else 0 # Substr with length = 1
        cnts[suffix] += 1
        base = base * 10 % P

print(answer)

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
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
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)











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, 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 = 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)


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)

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)

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):  # handling of 0's as n and rem
        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]))


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(t)
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 = 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 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)

N, P = list(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 = list(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)
    return
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)






from collections import defaultdict


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

"""
S[l:r]  : (S[l:] - S[r:]) / 10**x

Pが2,5以外であれば、S[l:]とS[r:]がPで割り切れればよい
2,5は10**xと互いに素ではないので例外。

例２の 2020について、左から4つ目の0に着目すると、
0
20
020
2020
いずれも2で割り切れるので、右端にくるものが２で割り切れるだけでよい。
"""

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 # S[r:]が空文字になるばあいのやつ
    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)

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を作成
        modp_counter = [0] * p
        modp = 0
        modp_counter[0] = 1 # 割り切れるやつが入る場所の初期値を1にしておかないと、1つ割り切れるやつがきたときにpair_count+=0となってしまう(pair_count+=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():
    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()

import sys
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()

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

if P == 2 or P == 5:  #10と素でない場合一番右の桁で決まる
    ans = 0
    for i in range(N):
        if S[i] % P == 0:
            ans += i+1
    print(ans)
    return

A = [0]  #A[i] = 下i桁をPで割った余り
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)

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())


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()

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)