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

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF = 1 << 60
MOD = 10**9 + 7 
input = lambda:sys.stdin.readline().rstrip()
from collections import Counter
def resolve():
    n, p = map(int, input().split())
    S = input()

    if p == 2 or p == 5:
        res = 0
        for i, c in enumerate(S, 1):
            if int(c) % p == 0:
                res += i
        print(res)
        return

    res = 0
    now = 0
    counter = Counter()
    counter[0] = 1
    for i in range(n - 1, -1, -1):
        now = (now + pow(10, n - i - 1, p) * int(S[i])) % p
        res += counter[now]
        counter[now] += 1
    print(res)
resolve()

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

Solution (Python):
n, p = map(int, input().split())

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

elif p == 5:
    s = input()
    ans = 0
    for i in range(n):
        if int(s[i]) % 5 == 0:
            ans += i + 1
    print(ans)

else:
    s = input()[::-1]
    mod = 0
    c = [0] * p
    c[0] = 1
    ten = 1
    for i in s:
        mod = (mod + ten * int(i)) % p
        ten = ten * 10 % p
        c[mod] += 1

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

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

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

Solution (Python):

import sys
from collections import defaultdict

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))


N, P = lr()
S = sr()
dic = defaultdict(int)
dic[0] = 1
num = 0
power = 1
answer = 0
if P%2 == 0 or P%5 == 0:
    x = [i for i, y in enumerate(S, 1) if int(y) % P == 0]
    answer = sum(x)
else:
    for s in S[::-1]:
        s = int(s)
        num += s * power
        num %= P
        answer += dic[num]
        dic[num] += 1
        power *= 10; power %= P

print(answer)

Solution (Python):
import math
import fractions



def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    
    return divisors

def ValueToBits(x,digit):
    res = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        res[i]=now%2
        now = now >> 1
    return res

def BitsToValue(arr):
    n = len(arr)
    ans = 0
    for i in range(n):
        ans+= arr[i] * 2**i
    return ans

def ZipArray(a):
    aa = [[a[i],i]for i in range(n)]

    aa.sort(key = lambda x : x[0])
    for i in range(n):
        aa[i][0]=i+1
    aa.sort(key = lambda x : x[1])
    b=[aa[i][0] for i in range(len(a))]
    return b

def ValueToArray10(x, digit):
    ans = [0 for i in range(digit)]
    now = x
    for i in range(digit):
        ans[digit-i-1] = now%10
        now = now //10
    return ans

def Zeros(a,b):
    if(b<=-1):
        return [0 for i in range(a)]
    else:
        return [[0 for i in range(b)] for i in range(a)]

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


'''
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

p = 2
N = 10 ** 6 + 2
fact = [1, 1]  
factinv = [1, 1]  
inv = [0, 1]  

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

'''










n,p = list(map(int, input().split()))
s = input()
nums = []
numsinv = []

for i in range(n):
    nums.append(int(s[i]))
    numsinv.append(int(s[n-1-i]))
    
if(p==2):
    ans = 0
    for i in range(n):
        ans += (numsinv[i]+1)%2 * (n-i)
    print(ans)
    exit()
if(p==5):
    ans=0
    for i in range(n):
        if(numsinv[i]%5==0):
            ans += (n-i)
    print(ans)
    exit()


pows = [0 for i in range(n)]


pows[0] = 1

for i in range(n-1):
    pows[i+1] = (pows[i] * 10)%p

rights = [0]
now = 0
for i in range(n):
    rights.append((rights[-1] + numsinv[i] * pows[i])%p)

lefts = [0]
for i in range(n):
    lefts.append((lefts[-1] + nums[i] * pows[n-1-i])%p)



total = lefts[-1]

timesL = [0 for i in range(p)]
timesR = [0 for i in range(p)]

for i in range(n+1):
    timesL[lefts[i]] += 1
    timesR[rights[i]] += 1
    
ans = 0

for i in range(p):
    ans += timesL[i] * timesR[(total-i+p)%p]

print((ans - (n+1))//2)

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

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

if __name__ == '__main__':
    main()

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

Solution (Python):

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

Solution (Python):
from collections import *
n, p = 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)
    exit()
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)

Solution (Python):


import sys
import math
import collections
import itertools
INF = 10 ** 13
MOD = 10 ** 9 + 7
def input() : return sys.stdin.readline().strip()
def lcm(x, y) : return (x * y) // math.gcd(x, y)
def I() : return int(input())
def LI() : return [int(x) for x in input().split()]
def RI(N) : return [int(input()) for _ in range(N)]
def LRI(N) : return [[int(x) for x in input().split()] for _ in range(N)]
def LS() : return input().split()
def RS(N) : return [input() for _ in range(N)]
def LRS(N) : return [input().split() for _ in range(N)]
def PL(L) : print(*L, sep="\n")
def YesNo(B) : print("Yes" if B else "No")
def YESNO(B) : print("YES" if B else "NO")

N, P = LI()
S = input()

if P == 2 or P == 5:
    ans = 0
    for i in range(N):
        if int(S[N-1 - i]) % P == 0:
            ans += N-i
    print(ans)
else:
    A = [0] * (N+1)
    for i in range(N):
        A[i+1] = (A[i] + int(S[N-1 - i]) * pow(10, i, P)) % P

    c = collections.Counter(A)
    ans = 0
    for v in c.values():
        ans += v * (v-1) // 2
    
    print(ans)

Solution (Python):
N, P = 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 c.values():
        ans += (a * (a-1)) // 2
print(ans)

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

        
if __name__ == "__main__":
    main()

Solution (Python):
import sys
input = sys.stdin.readline
from collections import Counter
def main():
    N, P = map(int, input().split())
    S = list(map(int, input().rstrip("\r\n")))
    S.reverse()
    ans = 0
    if P == 2 or P == 5:
        for i in range(N):
            if S[i] % P == 0:ans += N-i
    else:
        A = [0] * N
        tenpow = 1
        for i in range(N):
            A[i] = (S[i]*tenpow) % P
            tenpow *= 10
            tenpow %= P
        D = [0] * (N+1)
        for i in range(N):
            D[i+1] = (D[i] + A[i]) % P
        c = Counter(D)
        for v in c.values():
            ans += v*(v-1)//2
    print(ans)
if __name__ == "__main__":
    main()

Solution (Python):
import sys

N, P = 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)
    sys.exit()


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)

Solution (Python):
def main():
    N, P = (int(i) for i in input().split())
    L = [int(s) for s in input()][::-1]
    ans = 0
    if P == 2 or P == 5:
        for i, e in enumerate(L):
            if e % P == 0:
                ans += N-i
    else:
        A = [0]*N
        d = 1
        for i, e in enumerate(L):
            A[i] = (e*d) % P
            d *= 10
            d %= P
        S = [0]*(N+1)
        for i in range(N):
            S[i+1] = S[i] + A[i]
            S[i+1] %= P
        from collections import Counter
        c = Counter(S)
        for v in c.values():
            ans += v*(v-1)//2
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys

N, P = 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)
    sys.exit()


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)

Solution (Python):
import sys
sys.setrecursionlimit(10**6) 
import math

from copy import copy, deepcopy
from operator import itemgetter

import bisect

from collections import deque 



from collections import Counter

from itertools import accumulate

from heapq import heapify,heappop,heappush


def input(): return sys.stdin.readline()[:-1]
def printl(li): print(*li, sep="\n")
def argsort(s): return sorted(range(len(s)), key=lambda k: s[k])




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



















if P!=2 and P!=5:
    pc=[0]*P
    pc[0]=1
    count=0
    ans=0
    p10=1
    for i in range(1,N+1):
        count+=int(S[N-i])*p10
        count%=P
        ans+=pc[count]
        pc[count]+=1
        p10*=10
        p10%=P

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

Solution (Python):
import sys
sys.setrecursionlimit(10**6) 
import math

from copy import copy, deepcopy
from operator import itemgetter

import bisect

from collections import deque 



from collections import Counter

from itertools import accumulate

from heapq import heapify,heappop,heappush


def input(): return sys.stdin.readline()[:-1]
def printl(li): print(*li, sep="\n")
def argsort(s): return sorted(range(len(s)), key=lambda k: s[k])




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



















if P!=2 and P!=5:
    pc=[0]*P
    pc[0]=1
    count=0
    ans=0
    for i in range(1,N+1):
        count+=int(S[N-i])*pow(10,(i-1),P)
        count%=P
        ans+=pc[count]
        pc[count]+=1

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

Solution (Python):
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)
    exit()
if p==5:
    ans=0
    for i,j in enumerate(s):
        if j%5==0:
            ans+=(n-i)
    print(ans)
    exit()

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

Solution (Python):
import sys
sys.setrecursionlimit(10**6) 
import math

from copy import copy, deepcopy
from operator import itemgetter

import bisect

from collections import deque 



from collections import Counter

from itertools import accumulate

from heapq import heapify,heappop,heappush


def input(): return sys.stdin.readline()[:-1]
def printl(li): print(*li, sep="\n")
def argsort(s): return sorted(range(len(s)), key=lambda k: s[k])




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



















if P!=2 and P!=5:
    l=[0]*(N+1)
    count=0
    for i in range(1,N+1):
        count+=int(S[N-i])*pow(10,(i-1),P)
        l[i]=count%P

    pc=[0]*P
    ans=0
    for p in l:  
        ans+=pc[p]
        pc[p]+=1
    print(ans)
elif P==2:
    ans=0
    for i in range(1,N+1):
        if int(S[N-i])%2==0:
            ans+=N-i+1
    print(ans)
elif P==5:
    ans=0
    for i in range(1,N+1):
        if int(S[N-i])%5==0:
            ans+=N-i+1
    print(ans)

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

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


def main():
    n, p = map(int, input().split())
    s = list(input())
    if 10 % p == 0:
        ans = 0
        for i in range(n):
            if (ord(s[i])-ord('0')) % p == 0:
                ans += i+1
        print(ans)
        return

    d = [0] * (n+1)
    ten = 1
    for i in reversed(range(n)):
        a = (ord(s[i])-ord('0')) * ten % p
        d[i] = (d[i+1]+a) % p
        ten *= 10
        ten %= p

    cnt = [0] * p
    ans = 0
    for i in reversed(range(n+1)):
        ans += cnt[d[i]]
        cnt[d[i]] += 1
    print(ans)


main()

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

Solution (Python):

import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n,mod = map(int,input().split())
S = list(map(int,input()))
if mod == 2:
  for i in range(n):
    if S[i] % 2 == 0:
      ans += i+1
elif mod == 5:
  for i in range(n):
    if S[i] % 5 == 0:
      ans += i + 1
else:
  tenpow = 1
  for i in range(n-1,-1,-1):
    S[i] = S[i] * tenpow % mod
    tenpow = tenpow * 10 % mod
  acum = [0]*(n+1)
  for i in range(n):
    acum[i+1] = (acum[i]+S[i]) % mod
  C = collections.Counter(acum)
  for key,item in C.items():
    ans += (item-1) * item //2


print(ans)

Solution (Python):
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)
 
if __name__ == "__main__":
    main()

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

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

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

l = len(S)
if P == 2:
    ans = 0
    for i in range(l):
        if S[i]%2 == 0:
            ans += i+1
elif P == 5:
    ans = 0
    for i in range(l):
        if S[i]%5 == 0:
            ans += i+1
else:
    data = [0]*P
    temp = 0
    ans = 0
    for i in range(l-1, -1, -1):
        temp += S[i]*pow(10, l-i-1, P)
        temp %= P
        ans += data[temp]
        data[temp] += 1
    ans += data[0]

print(ans)

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

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

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

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

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

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

Solution (Python):
'''
0から9までの数字から成る長さNの文字列Sの部分文字列の内、
十進数表記の整数とみなした時、素数Pで割り切れるものの個数を求めよ。
部分文字列は先頭が0であっても良く、文字列の位置で区別する。

terms:
    1<=n<=2*10**5
    2<=p<=10**4

input:
    4 3
    3543

output:
    6
'''

from collections import defaultdict
import sys
input = sys.stdin.readline
INF = float('inf')
mod = 10 ** 9 + 7
eps = 10 ** -7
def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))
n, p = inpl()
s = input()[:-1]
arr = [int(s[i]) for i in range(n)]
ans = 0
if p == 2 or p == 5:
    '''
    10を割り切ると桁の話が使えないので場合分け
    1の位が割り切れればそれだけ
    '''
    for i in range(n):
        if arr[i] % p == 0:
            ans += i + 1
    print(ans)
else:
    '''
    Pが10の約数である2,5だと以下の仮定が成り立たないので使えない
    ・ある数XがPで割り切れるならそれを10倍したものもPで割り切れる

    f(i)=Sの下i桁をPで割った時の余り
    として、f(i)=f(j)になる組を考える。
    するとiからj桁目までの値はPで割り切れる(i%p-j%p≡(i-j)%p)
    pow(x,y,z)=x^y%z
    '''
    dic = defaultdict(int)
    
    now = 0
    dic[0]=1 
    for i in range(n-1,-1,-1): 
        now += arr[i] * pow(10, n - 1 - i, p)
        now %= p
        ans+=dic[now]
        dic[now] += 1
    
    print(ans)

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

N, P = map(int, input().split())
S = input()[:-1]

if P in [2, 5]:
    ans = 0
    
    for i in range(N):
        if int(S[i])%P==0:
            ans += i+1
    
    print(ans)
    exit()

cnt = defaultdict(int)
cnt[0] = 1
now = 0
ans = 0

for i in range(N-1, -1, -1):
    now = (int(S[i])*pow(10, N-1-i, P)+now)%P
    ans += cnt[now]
    cnt[now] += 1

print(ans)

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

Solution (Python):
N, P = 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)
    exit()

for i, t in enumerate(S[::-1]):
    now = (now + int(t) * pow(10, i, P)) % P
    ans += hyou[now]
    hyou[now] += 1

print(ans)

Solution (Python):
def main():
    N, P = map(int, input().split())
    *s, = 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)


if __name__ == '__main__':
    main()

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

Solution (Python):
from collections import Counter
n,p = map(int,input().split())
s = input()
n = len(s)
mod = [0] * (n+1)
ten = [0] * n

a = 1
for i in range(n):
    ten[i] = a
    a = a * 10 % p

ans = 0
if p != 2 and p != 5:
    rui = 0
    for i in range(n):
        rui = (int(s[n-1-i]) * ten[i] + rui) % p
        mod[n-1-i] = rui

    b = Counter(mod)
    c = list(b.values())
    c.sort(reverse = True)

    for i in c:
        if i > 1:
            ans += i * (i-1) // 2
        else:
            break
            
elif p == 2:
    for i in range(n):
        if int(s[i]) % 2 == 0:
            ans += i+1
else:
    for i in range(n):
        if int(s[i]) % 5 == 0:
            ans += i+1

print(ans)

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

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

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

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)

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

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

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)