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

def hoge():

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

    if p in (2,5):
        a = tuple(int(c)%p for c in s)
        out = 0
        for i,x in enumerate(a):
            if x==0:
                out += (i + 1)
    else:
        a = [0]*n
        tmp = 0
        for i in reversed(range(n)):
            tmp = (tmp + pow(10, n-i-1, p) * int(s[i])) % p
    
            a[i] = tmp
        d = {i: 0 for i in range(p)}
        d[0] = 1
        out = 0
        for x in a[::-1]:
            out += d[x]
            d[x] += 1
    print(out)
hoge()

Solution (Python):
from collections import Counter


n, p = map(int, input().split())
S = map(int, reversed(input()))

if p == 2 or p == 5:
    ans = 0
    mods = map(lambda x: x % p, S)
    for idx, mod in enumerate(mods):
        if mod == 0:
            ans += n - idx
    print(ans)
    exit()

mods = [0]
num = 0
digit = 1
for s in S:
    num += s * digit
    num %= p
    mods.append(num)
    digit = digit * 10 % p

counter = Counter(mods)
ans = 0
for count in counter.values():
    ans += count * (count-1) // 2
print(ans)

Solution (Python):
N,P=map(int,input().split())
S=input()
s=[0 for i in range(N+1)]
a=[0 for i in range(N+1)]
a[0]=(10**0)%P
for i in range(N):
    A=a[i]
    a[i+1]=(A*(10%P))%P
    s[i+1]=(s[i]+A*int(S[N-i-1]))%P
d=[0 for i in range(P)]
for i in range(len(s)):
    d[s[i]]+=1
ans=0
if P!=2 and P!=5:
    for D in d:
        ans+=D*(D-1)//2
    print(ans)
elif P==2:
    for i in range(N):
        if int(S[N-1-i])%2==0:
            ans+=(N-i)
    print(ans)
else:
    for i in range(N):
        if int(S[N-1-i])%5==0:
            ans+=(N-i)
    print(ans)

Solution (Python):
def sol(s, p):
	n = len(s)
	cnt = 0
	if p == 2 or p == 5:
		for i in range(n):
			if (s[i] % p == 0):
				cnt += i + 1
	else:
		pre = [0] * (n+2)
		pre[n+1] = 0
		b = 1
		for i in range(n, 0, -1):
			pre[i] = (pre[i+1] + s[i-1] * b) % p
			b = (b * 10) % p
		rec = [0] * p
		rec[0] = 1
		for i in range(n, 0, -1):
			cnt += rec[pre[i]]
			rec[pre[i]] += 1
	return cnt

if __name__ == "__main__":
	n, p = map(int, input().split())
	s = input()
	print (sol([int(i) for i in s], p))

Solution (Python):
def main():
    n,p=map(int,input().split())
    s=list(map(int,list(input())))
    cnt,ans=0,0
    m=[0]*p
    m[0]=1

    if p in [2, 5]:
        for i, x in enumerate(s):
            if x % p == 0:
                ans += i + 1
        print(ans)
        exit()

    sm=0
    d=1
    for i in range(n):
        sm=(sm+s[n-1-i]*d)%p
        m[sm]+=1
        d=(d*10)%p
    
    for i in m:
        ans+=i*(i-1)//2

    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
from collections import defaultdict

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

def solMin():
    dp = [[0] * P for _ in range(N + 1)]

    for i, s in enumerate(map(int, S), start=1):
        dp[i][s % P] += 1
        for p in range(P):
            dp[i][(p * 10 + s) % P] += dp[i - 1][p]

    return sum(dp[i][0] for i in range(N + 1))

def solLarge():
    cnt = defaultdict(int)
    ret = 0
    now = 0

    for d, s in enumerate(map(int, S[:: -1])):
        now += pow(10, d, P) * s
        now %= P
        ret += cnt[(now - P) % P]
        if now == 0:
            ret += 1
        cnt[now] += 1

    return ret

print(solMin() if P * N <= 10**6 else solLarge())

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

def nCr(n, r):
    if n < r:
        return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
ans = 0
if p == 2 or p == 5:
    for i in range(n):
        if int(s[i]) % p == 0:
            ans += i + 1
else:
    
    
    
    
    
    
    
    
    

    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    dp = [0] * p
    dp[0] = 1
    tmp = 0
    for i in range(n)[::-1]:
        tmp = (int(s[i]) * pow(10, n - i - 1, p) + tmp) % p
        dp[tmp] += 1
    for i in dp:
        ans += nCr(i, 2)
print(ans)

Solution (Python):
n, p = map(int, input().split())
s = list(map(int, list(input())))[::-1]

div = [0 for _ in range(p)]

su = 0
for i in range(n):
	su = (su + s[i] * pow(10, i, p)) % p
	div[su] += 1

cnt = 0
if p in [2, 5]:
	if p == 2:
		ok = [0, 2, 4, 6, 8]
	else:
		ok = [0, 5]

	for i in range(len(s)):
		if s[i] in ok:
			cnt += n - i

else:
	for i in range(len(div)):
		x = div[i]
		if i == 0:
			y = x * (x + 1) // 2
		else:
			y = x * (x - 1) // 2
		cnt += y

print(cnt)

Solution (Python):
from copy import copy
from collections import defaultdict
n, p = map(int, input().split())

s = input()
ans = 0
if p == 2 or p == 5:
    for i in range(n):
        if int(s[i]) % p == 0:
            ans += i + 1
else:
    dp = [0] * p
    dp[0] = 1
    tmp = 0
    for i in range(n)[::-1]:
        tmp = (int(s[i]) * pow(10, n - i - 1, p) + tmp) % p
        
        
        ans += dp[tmp]
        dp[tmp] += 1 
    

print(ans)

Solution (Python):
n, p = map(int, input().split())
s = input()
sum_count = 0
if p in {2, 5}:
    for right in range(n):
        if int(s[right]) % p == 0:
            sum_count += (right + 1)
else:
    modp_count = [0] * p
    modp_count[0] = 1
    subs_modp, pow = 0, 1
    for si in s[::-1]:
        subs_modp += ((int(si)*pow) % p)
        subs_modp %= p
        modp_count[subs_modp] += 1
        pow = (pow*10) % p
        
    for count in modp_count:
        sum_count += count*(count - 1) // 2
print(sum_count)

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

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

modP = [0 for _ in range(P)]
modP[0] = 1
now = 0
t = 1
for i in range(N) :
    now += int(S[-1-i]) * t
    now %= P
    modP[now] += 1
    t = t * 10 % P

for r in modP :
    ans += r*(r-1)//2

print(ans)

Solution (Python):

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


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

if p == 2 or p == 5:
    for i in range(n):
        if s[i] % p == 0:
            sum += i + 1

else:
    for i in range(n):
        rem = (int(s[-i - 1]) * pow(10, i, p) + rem) % p
        sum += cnt[rem]
        cnt[rem] += 1

print(sum)

Solution (Python):
import sys
"""
方針：まず左端を固定して実際にPで割ったあまりを計算しながら数値列を伸ばしていけばO(N^2)で計算ができる
文字列の左右を固定した場合に（部分文字列について？）Pで割ったあまりを計算できないか，定式化を考えてみよう．
Ui := S[i:N]をSのi文字以降を評価した整数と置く．便宜上UN+1=0とする．
この時Sのi文字目からj文字目までを評価した整数は(Ui - Uj+1)/10^(j+1-i)と表せる．

"""

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):
from collections import defaultdict


def comb(n, k):
    if n < k or n < 0 or k < 0:
        return 0
    k = min(k, n - k)
    ans = 1
    for i in range(1, k + 1):
        ans *= n - i + 1
        ans //= i
    return 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 int(s[i]) in [0, 5]:
            ans += i + 1
else:
    mod_list = [0] * (n + 1)
    d = 1
    for i in reversed(range(n)):
        mod_list[i] = int(s[i]) * d + mod_list[i + 1]
        mod_list[i] %= p
        d = (d * 10) % p

    mod_dict = defaultdict(int)
    for i in range(n + 1):
        mod_dict[mod_list[i]] += 1

    
    

    ans = 0
    for c in mod_dict:
        ans += comb(mod_dict[c], 2)

print(ans)

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

    if P == 2 or P == 5:
        res = 0

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

    else:
        res = 0
        count = [0] * P
        r = 0

        for i in range(N-1, -1, -1):
            r = (int(S[i]) * pow(10, N-1 - i, P) + r) % P
            if r == 0: res += 1
            res += count[r]
            count[r] += 1
        
        print(res)

if __name__ == '__main__':
    solve()

Solution (Python):
import sys
"""
方針：まず左端を固定して実際にPで割ったあまりを計算しながら数値列を伸ばしていけばO(N^2)で計算ができる
文字列の左右を固定した場合に（部分文字列について？）Pで割ったあまりを計算できないか，定式化を考えてみよう．
Ui := S[i:N]をSのi文字以降を評価した整数と置く．便宜上UN+1=0とする．
この時Sのi文字目からj文字目までを評価した整数は(Ui - Uj+1)/10^(j+1-i)と表せる．

"""

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

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

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

if P == 2 or P == 5:
  ma25()
else:
  ma()

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

if p in [2, 5]:
    ans = 0
    for i, x in enumerate(s):
        if x % p == 0:
            ans += i + 1
    print(ans)
    exit()

x = [0] * p
x[0] = 1
temp = 0
d = 1
for i in range(n-1, -1, -1):
    temp = (temp + s[i] * d) % p
    x[temp] += 1
    d = (d * 10) % p

ans = 0

for z in x:
    ans += z * (z-1) // 2

print(ans)

Solution (Python):
n,p = map(int, input().split())
s = input()
ans = 0
ruisekiwa = [0]*(n+1)
ten = 1

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

    cnt = [0]*p
    for i in range(0, n+1)[::-1]:
        ans += cnt[ruisekiwa[i]]
        cnt[ruisekiwa[i]] += 1

print(ans)

Solution (Python):
from collections import defaultdict
n,p = [int(x) for x in input().split()]
s = input()
if p!=2 and p!=5:
  r = defaultdict(int)
  a = int(s)
  r[a%p]+=1
  for i in range(n):
    a = (a%p-int(s[i])%p*pow(10,(n-1-i),p))%p
    r[a]+=1
  
  ans = 0
  cnt=1
  for i in r.values():
    ans+=i*(i-1)//2
  print(ans)
elif 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)

Solution (Python):
from collections import defaultdict,deque
import itertools
n,p = [int(x) for x in input().split()]
s = list(input())
if p!=2 and p!=5:
  r = defaultdict(int)
  a =[]
  s1 = s[::-1]
  for i in range(n):
    a.append((int(s1[i])%p*pow(10,i,p))%p)
  a = [0]+a[::-1]
  b = list(itertools.accumulate(a))
  for i in b:
    r[i%p]+=1
  ans = 0
  for i in r.values():
    ans+=(i*(i-1))//2
  print(ans)
elif 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)

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

s = input()

ruisekiwa = [0 for _ in range(0, n + 1)]
if 10 % p == 0:
    ans = 0
    for i in range(0, n):
        if (ord(s[i]) - ord('0')) % p == 0:
            ans += i + 1
    print(ans)
    exit()

ten = 1
for _i in range(0, n):
    i = n - _i - 1
    ruisekiwa[n - i] = ((ord(s[i]) - ord('0')) * ten + ruisekiwa[n - i - 1]) % p
    ten *= 10
    ten %= p

ans = 0
cnt = [0 for _ in range(0, p)]
for i in range(0, n+1):
    ans += cnt[ruisekiwa[i]]
    cnt[ruisekiwa[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[N-1-i] % 2 == 0:
            ans += N-i
elif P == 5:
    ans = 0
    for i in range(N):
        if S[N-1-i] % 5 == 0:
            ans += N-i
else:
    ans = 0
    cnt = [0] * P
    cnt[0] = 1
    dec_mod, pre_mod = 1, 0
    for i in range(N):
        mod = (S[N-1-i] * dec_mod + pre_mod) % P
        ans += cnt[mod]
        cnt[mod] += 1
        dec_mod = dec_mod * 10 % P
        pre_mod = mod
print(ans)

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

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

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

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

def MS(i,s,pre):
  return (int(s)*i+pre)%p
 
M = [0]*p
M[0] = 1
i = 1
pre = 0
for s in S[::-1]:
  
  pre = pre + int(s)*i
  pre = pre%p
  M[pre] += 1
  i = i*10%p

ans = sum(map(lambda m:(m*(m-1))//2, M))
print(ans)

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

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

def MS(i,s,pre):
  return (int(s)*i+pre)%p
 
M = [0]*p
M[0] = 1
i = 1
pre = 0
for s in S[::-1]:
  
  pre += int(s)*i
  pre %= p
  M[pre] += 1
  i = i*10%p

ans = sum(map(lambda m:(m*(m-1))//2, M))
print(ans)

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

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

def MS(i,s,pre):
  return (int(s)*i+pre)%p
 
M = [0]*p
M[0] = 1
i = 1
pre = 0
for s in S[::-1]:
  pre = MS(i,int(s),pre)
  M[pre] += 1
  i = i*10%p

ans = sum(map(lambda m:(m*(m-1))//2, M))
print(ans)

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

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

def MS(i,s,pre):
  return (int(s)*i+pre)%p
 
M = [0]*p
M[0] = 1
i = 1
pre = 0
for s in S[::-1]:
  pre = MS(i,int(s),pre)
  M[pre] += 1
  i = i*10%p

ans = sum(map(lambda m:(m*(m-1))//2, M))
print(ans)

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

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

def MS(i,s,pre):
  pre = (int(s)*i+pre)
  return pre%p
 
M = [0]*p
M[0] = 1
i = 1
pre = 0
for s in S[::-1]:
  pre = MS(i,int(s),pre)
  M[pre] += 1
  i = i*10%p

ans = sum(map(lambda m:(m*(m-1))//2, M))
print(ans)

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

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

def MS(i,s,pre):
  pre += int(s)*i
  return pre%p
 
M = [0]*p
M[0] = 1
i = 1
pre = 0
for s in S[::-1]:
  pre = MS(i,int(s),pre)
  M[pre] += 1
  i = i*10%p

ans = sum(map(lambda m:(m*(m-1))//2, M))
print(ans)

Solution (Python):
N, P = [int(x) for x in input().split()]
S = input()

res = 0

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

print(res)

Solution (Python):


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

if P == 2:
    c = 0
    for i in range(N):
        u = int(S[i])
        if u % 2 == 0:
            c += i+1
    print(c)
        
elif P == 5:
    c = 0
    for i in range(N):
        u = int(S[i])
        if u % 5 == 0:
            c += i+1
    print(c)

else:
    U = [0]
    a = 0
    t = 1
    
    for i in range(N):
        t %= P
        a += int(S[-i-1])*t
        a %= P
        t *= 10
        U.append(a)
    U.append(10001)
    
    
    
    
    c = 0
    
    """
    for i in range(P):
        m = U.count(i)
        c += m*(m-1)//2
    print(c)
    """
    U.sort()
    
    idx = 0
    q = -1
    for i in range(N+2):
        if q != U[i]:
            q = U[i]
            m = i - idx
            idx = i
            c += m*(m-1)//2
    print(c)

Solution (Python):
n, p = map(int, input().split())
s = list(map(int, input()))
if p == 2 or p == 5:
    ans = 0
    for i, digit in enumerate(s):
        if digit % p == 0:
            ans += i + 1
    print(ans)
else:
    ans = 0
    ten_pow_i_mod = 1
    
    temp_mod = 0
    mod_multiset = [1] + [0] * (p - 1)
    for digit in reversed(s):
        temp_mod += digit * ten_pow_i_mod
        temp_mod %= p
        
        ans += mod_multiset[temp_mod]
        mod_multiset[temp_mod] += 1
        ten_pow_i_mod *= 10
        ten_pow_i_mod %= p
    print(ans)

Solution (Python):

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

if p == 2:
    ret = 0
    for i in range(len(s)):
        if int(s[i]) % 2 == 0:
            ret = ret + i + 1
    print(ret)
elif p == 5:
    ret = 0
    for i in range(len(s)):
        if int(s[i]) % 5 == 0:
            ret = ret + i + 1
    print(ret)
else:
    c_list = [0] * n
    power = 1
    for i in range(len(s)):
        c_list[i] = (c_list[i-1] + (int(s[-i-1]) * power)) % p
        power *= 10
        power = power % p
    c_list.append(0)
    counter = [0] * p
    for i in c_list:
        counter[i] += 1
    ret = 0
    for item in counter:
        if item >= 2:
            ret = ret + (item * (item - 1) // 2)
    print(ret)

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

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

def MS(i,s,pre):
  return (s*i +pre)%p
 
M = [0]*p
M[0] = 1
t = 1
now = 0
for i in S[::-1]:
    i = int(i)
    now += i*t
    now %= p
    M[now] += 1
    t = t*10%p

ans = sum(map(lambda m:(m*(m-1))//2, M))
print(ans)

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

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

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

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

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
ans = 0
now = 0

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

print(ans)

Solution (Python):
import sys
from bisect import *
from heapq import *
from collections import *
from itertools import *
from functools import *

sys.setrecursionlimit(100000000)
input = lambda: sys.stdin.readline().rstrip()

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

if P == 2:
    print(sum(i + 1 for i in range(N) if S[i] % 2 == 0))
elif P == 5:
    print(sum(i + 1 for i in range(N) if S[i] % 5 == 0))
else:
    x = [None] * (N + 1)
    x[N] = 0
    tmp = 1
    for i in reversed(range(N)):
        x[i] = (x[i + 1] + S[i] * tmp) % P
        tmp = tmp * 10 % P
    print(sum(i * (i - 1) // 2 for i in Counter(x).values()))

Solution (Python):


import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

"""
[解法メモ]
各桁(桁数iとする)を10**i mod pの形で持っておく.
それの累積和をとって, 再びmod pをとると, 同じ数のペアの範囲はpの倍数になっていることが分かる.(他の問題でもこの解法あった気がする)
よって, 答えは同じ数のペアの数をすべて足したもの.

pが2や5の場合, *10が付くと必ず割り切れるので注意.
つまり, 1桁目が割り切れたら必ず割り切れる.⇒各桁を見ていってpで割り切れるならそれ以前の数を足せば良い.
(例)p=5, s=100のとき
    1は割り切れないからx
    0は割り切れるからo ⇒ 2桁目なので+2(10,0の場合)
    0は割り切れるからo ⇒ 3桁目なので+3(100,00,0の場合)
    ⇒答えは5
"""

n, p = LI() 
s = list(map(int,list(input())))
t = []
ans = 0
if p == 2 or p == 5:
    for i in range(n):
        if s[i] % p == 0:
            ans += i+1
    print(ans)
    quit()
 
for i in range(n):
    t.append(s[i]*pow(10,n-i-1,p))
t = list(accumulate(t))
u = [i % p for i in t]
u = list(Counter(u).items())
ans = 0
for i,j in u:
    if i == 0:
        ans += j
    if j >= 2:
        ans += j*(j-1) // 2
print(ans)

Solution (Python):


import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n, p = LI() 
s = list(map(int,list(input())))
t = []
ans = 0
if p == 2 or p == 5:
    for i in range(n):
        if s[i] % p == 0:
            ans += i+1
    print(ans)
    quit()
 
for i in range(n):
    t.append(s[i]*pow(10,n-i-1,p))
t = list(accumulate(t))
u = [i % p for i in t]
u = list(Counter(u).items())
ans = 0
for i,j in u:
    if i == 0:
        ans += j
    if j >= 2:
        ans += j*(j-1) // 2
print(ans)

Solution (Python):
from collections import defaultdict

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

res = 0

if p not in [2,5]:
    crem = 0
    
    crem_10 = [1]
    for i in range(1,n):
        crem_10 += [(crem_10[-1] * (10%p)) % p]
        
    dic_p = defaultdict(lambda : 0)
    for i,subs in enumerate(s[::-1]):
        crem += (int(subs) % p * crem_10[i]) % p
        crem %= p

        if crem == 0:
            res += 1
        res += dic_p[crem]

        dic_p[crem] += 1
        
else:
    for i,subs in enumerate(s[::-1]):
        if int(subs) % p == 0:
            res += n - i
    
print(res)

Solution (Python):
class Solution:

    def solve(self, N: int, P: int, S: str):

        if P == 2 or P == 5:
            answer = 0
            for idx, s in enumerate(S):
                if int(s) % P == 0:
                    answer += idx + 1

        else:
            answer = 0
            U = [0] * P  
            U[0] += 1

            num = 0
            base10_mod_p = 1
            for i in range(N):
                num = (num + int(S[N-i-1]) * base10_mod_p) % P
                base10_mod_p = (base10_mod_p * 10) % P

                U[num] += 1

            for u in U:
                answer += u * (u-1) // 2

        return answer


if __name__ == '__main__':

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

    
    solution = Solution()
    answer = solution.solve(N, P, S)
    print(answer)

Solution (Python):
from sys import stdin 
from collections import defaultdict, Counter


N, P = map(int, stdin.readline().split())
S, = stdin.readline().split()

ans = 0 



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

else:
	
	count = Counter()
	prefix = []
	ten = 1
	mod = 0
	for i in range(N):
		x = (int(S[N - i - 1])*ten + mod) % P 
		prefix.append(x)
		count[x] += 1
		ten = (ten * 10) % P 
		mod = x
	prefix.append(0)
	count[0] += 1
	for val in count.values():
		ans += val*(val - 1)//2


print (ans)

Solution (Python):
n, p = (int(i) for i in input().split());

s = input();

if p == 2 or p == 5:
    res = 0;
    for i in range(len(s)):
        if int(s[i]) % p == 0:
            res += i + 1;
    print(res);
    exit(0);

h = [0 for i in range(len(s) + 1)];
st = 1;

for i in range(len(s) - 1,-1,-1):
    
    h[i] = (st * int(s[i]) + h[i + 1]) % p;
    st = (st * 10) % p;



h.sort();



i = 0;
res = 0;

while i <= n:
    j = i;
    while j + 1 <= n and h[i] == h[j + 1]:
        j += 1;
    l = j - i + 1;
    res += (l * (l - 1)) // 2;
    i = j + 1;

print(res);

Solution (Python):
def main():
    n, mod = map(int, input().split())
    s = input().rstrip()
    a = [int(c)%mod for c in s]
    ans = 0
    if mod == 2 or mod == 5:
        for i in range(n):
            if a[i] == 0:
                ans += i + 1
    else:
        mul = 10 % mod
        for i in reversed(range(n-1)):
            a[i] = (a[i]*mul + a[i+1]) % mod
            mul = mul*10 % mod
        b = [0] * mod
        b[0] = 1
        for i in reversed(range(n)):
            ans += b[a[i]]
            b[a[i]] += 1
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]
[n,p]=i2()
s=input()

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

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


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