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):
import sys 
import collections
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N,P = map(int,readline().split())
S = list(map(int,readline().rstrip().decode()))

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

print(solve(S))

Solution (Python):
import math

import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit


ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n,p = 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 d.values():
            ans += i*(i-1)//2
        ans += d[0]
        print(ans)
    return

if __name__ == '__main__':
    main()

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

if __name__ == '__main__':
    main()

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

if __name__ == '__main__':
    main()

Solution (Python):
from collections import Counter

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

def check(n):
    ans = 0
    for i in range(1, N+1):
        v = int(S[-i])
        if v%n==0:
            ans += N-(i-1)
    return ans

ans = 0
if P==2:
    ans = check(2)
elif P==5:
    ans = check(5)
else:
    ac = [0]*(N+1)
    for i in range(1, N+1):
        ac[i] = (ac[i-1]+int(S[-i])*pow(10, i-1, P))%P
    c = Counter(ac)
    for i in c.values():
        ans += i*(i-1)//2

print(ans)

Solution (Python):
from collections import Counter

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

ans = 0

if P==2:
    for i in range(1, N+1):
        v = int(S[-i])
        if v%2==0:
            ans += N-(i-1)
elif P==5:
    for i in range(1, N+1):
        v = int(S[-i])
        if v%5==0:
            ans += N-(i-1)
else:
    ac = [0]*(N+1)
    for i in range(1, N+1):
        ac[i] = (ac[i-1]+int(S[-i])*pow(10, i-1, P))%P
    c = Counter(ac)
    for i in c.values():
        ans += i*(i-1)//2

print(ans)

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

count = 0

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

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

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

    print(ans)
    exit()


mods=[0]*p
mods[0]=1
num=0
fac=1

for i in range(n):
    num+=(int(s[n-i-1])*fac)
    num%=p

    fac=(fac*10)
    fac%=p
    mods[num]+=1


ans=0
for item in mods:
    ans+=(item*(item-1))//2



print(ans)

Solution (Python):


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


remainder = [0] * P
tmp = 0
rad = 1 

'''
if(P == 2 or P == 5):
    for i in range(N):
        r = int(S[i])
        tmp += r * rad
        tmp %= P
        remainder[tmp] += 1
        rad *= 10
'''
if(P == 2):
    ans = 0
    for i in range(N):
        r = int(S[i])
        if(r % 2 == 0):
            ans += N-i
    print(ans)
elif(P == 5):
    ans = 0
    for i in range(N):
        r = int(S[i])
        if(r % 5 == 0):
            ans += N-i
    print(ans)
else:
    for i in range(N):
        r = int(S[i])
        tmp += r * rad
        tmp %= P
        remainder[tmp] += 1
        rad *= 10
        rad %= P
    remainder[0] += 1

    

    ans = 0
    for i in range(P):
        e = remainder[i]
        ans += e*(e-1)/2
    print(int(ans))

Solution (Python):
from collections import defaultdict
n,p = map(int,input().split())
s = list(map(int,list(input())))[::-1]
ans = 0
if p == 2 or p == 5:
    for i in range(n):
        if s[i]%p==0:
            ans += n-i
    print(ans)
else:
    d = defaultdict(int)
    check = 0
    ten = 1
    for i in range(n):
        check += s[i]*ten
        check %= p
        ans += d[check]
        if check == 0:
            ans+=1
        d[check] += 1
        ten *= 10
        ten %= p
    print(ans)

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

t = [0 for i in range(n+1)]
P = [0 for i in range(p)]
P[0] += 1
d = 1
for i in range(1, n+1):
    t[i] = (t[i-1]+int(s[n-i])*d) % p
    P[t[i]] += 1
    d = d*10 % p
ans = 0
for c in P:
    ans += c*(c-1)//2

print(ans)

Solution (Python):
from collections import Counter
n,p=map(int,input().split())
s=input()
DP=[0]
ans=0

if p==2 or p==5:
    for i,j in enumerate(s):
        if int(j)%p==0:
            ans +=i+1
else:
    num,point=0,1
    for i in s[::-1]:
        num +=int(i)*point
        num %=p
        DP.append(num)
        point *=10
        point %=p

    DP=Counter(DP)
    for v,m in DP.items():
        if m>=2:ans +=m*(m-1)//2
print(ans)

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

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

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

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)

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

Solution (Python):


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


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


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


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


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


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


if __name__ == "__main__":
    main()

Solution (Python):
from collections import defaultdict
N, P = map(int,input().split())
S = input()

if P==5:
    ans = 0
    for i,m in enumerate(S):
        if m == '5' or m == '0':
            ans += i+1
elif P==2:
    ans = 0
    for i,m in enumerate(S):
        if int(m) % 2 ==0:
            ans += i+1
else:
    S = S[::-1]
    primdic = defaultdict(int)
    before = 0
    for i in range(0,N):
        now = (int(S[i])*pow(10,i,P)+before)%P
        primdic[now] += 1
        before = now
    
    primdic[0] += 1
    ans = 0
    for value in primdic.values():
        ans += value*(value-1)//2
print(ans)

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

if P == 5:
    ans = 0
    for i in range(N):
        if S[i] == '5' or S[i] == '0':
            ans += i+1
elif P == 2:
    ans = 0
    for i in range(N):
        if int(S[i]) % 2 == 0:
            ans += i+1
else:
    M = defaultdict(int)
    before = 0
    S = S[::-1]
    for i in range(N):
        now = (int(S[i])*(pow(10, i+1, P)) + before) % P
        before = now
        M[now] += 1
    M[0] += 1
    ans = 0
    for value in M.values():
        ans += value*(value-1)//2
print(ans)

Solution (Python):
N,P = map(int,input().split())
S = map(int,input())
S_li = [0]*(N+1)
S_rev = reversed(tuple(S))

tmp = 0
count= 0
from  collections import Counter

if 10%P==0:
    counter = 0
    for i,num in enumerate(S_rev):
        if num%P==0:
            counter += N-i
    print(counter)

else:
    ctr = [0] * P
    ctr[0] = 1
    ret = 0
    t = 0
    c = 1
    for x in S_rev:
        t = (t + c * x) % P
        ret += ctr[t]
        ctr[t] += 1
        c = c * 10 % P
 
    print(ret)

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

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


if __name__ == '__main__':
    main()

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

ans = 0  
for i in dic.values():
  if i != 1:
    ans += i*(i-1)//2
print(ans)

Solution (Python):
n, p = map(int, input().split())
s = input()
if p==2 or p==5:
    ans = 0
    for i in range(n):
        if int(s[i])%p==0:
            ans += i+1
    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)

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

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

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)

Solution (Python):
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)
    quit()
d = defaultdict(int)
now = 0
d[0] += 1

for i,x in enumerate(t):
    tmp = (pow(10,i,p) * int(x)) % p
    now += tmp
    now %= p
    d[now] += 1

for va in d.values():
    res += va*(va-1)//2
print(res)

Solution (Python):
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)
    quit()
elif mod == 5:
    ans = 0
    for i in range(n-1,-1,-1):
        if int(s[i]) % 5 == 0:
            ans += i+1
    print(ans)
    quit()

l = [0]*(n+1)
for i in range(n-1,-1,-1):
    l[i] = (l[i+1]+int(s[i])*pow(10,n-1-i,mod))%mod

c = Counter(l)

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

Solution (Python):
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 d.keys(): output += (d[i] * (d[i]-1) // 2)
    print(output)

    return

if __name__ == '__main__':
    main()

Solution (Python):
from collections import Counter

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

if P == 2 or P == 5:
    ans = 0
    for i, S in enumerate(Ss):
        if int(S)%P == 0:
            ans += i+1
else:
    As = [0]
    A = 0
    D = 1
    for S in Ss[::-1]:
        S = int(S)
        A = (A + S*D) % P
        As.append(A)
        D = D*10 % P

    cnt = Counter()
    ans = 0
    for A in As:
        ans += cnt[A]
        cnt[A] += 1

print(ans)

Solution (Python):
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:  
    ans = 0
    for i in range(N):
        if S[i] % P == 0:
            ans += i+1
    print(ans)
    exit()

A = [0]  
for i in range(1,N+1):
    A.append((A[i-1]+pow(10,i,P)*S[N-i]) % P)

from collections import Counter

c = Counter(A)
B = c.values()

ans = 0

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

print(ans)

Solution (Python):
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:  
    ans = 0
    for i in range(N):
        if S[i] % P == 0:
            ans += i+1
    print(ans)
    exit()

A = [0]  
for i in range(1,N+1):
    A.append((A[i-1]+pow(10,i,P)*S[N-i]) % P)

from collections import Counter

c = Counter(A)
B = c.values()

ans = 0

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

print(ans)

Solution (Python):
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  
def LS2(): return list(sys.stdin.readline().rstrip())  

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

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

A = [0]  
for i in range(1,N+1):
    A.append((A[i-1]+pow(10,i,P)*S[N-i]) % P)

from collections import Counter

c = Counter(A)
B = c.values()

ans = 0

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

print(ans)

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

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

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


else:

	count = Counter()
	ten = 1
	mod = 0
	for i in range(N):
		x = (int(S[N - i - 1])*ten + mod) % P
		ten = ten*10 % P 
		mod = x
		count[x] += 1

	count[0] += 1


	for i in count.values():
		ans += i*(i - 1)//2

print (ans)

Solution (Python):

from collections import defaultdict


N,P = map(int, input().split())
S = input()
ans = 0
if P in [2,5]:
    
    for i in range(N):
        if int(S[i]) % P == 0:
            ans += i + 1

else:
    d = defaultdict(int)
    d[0] = 1
    curr = 0
    for i in range(N):
        curr = curr + int(S[N-1-i]) * pow(10, i, P)
        curr %= P
        ans += d[curr]
        d[curr] += 1

print(ans)

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

ans = 0
d = [0]*(N+1)
cnt = [0]*P
ten = 1

for i in range(N-1,-1,-1):
    a = int(S[i]) * ten % P
    d[i] = (d[i+1]+a) % P
    ten *= 10
    ten %= P



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

print(ans)

Solution (Python):
from collections import Counter

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

total = 0
if p in [2, 5]:
    for i in range(n-1, -1, -1):
        if int(s[i]) % p == 0:
            total += i + 1
else:
    dp = [0] * (n + 1)
    fac = 1
    for i in range(n-1, -1, -1):
        dp[i] = (dp[i + 1] + int(s[i]) * fac) % p
        fac = (fac * 10) % p

    c = Counter(dp)

    for k, v in c.items():
        if v >= 2:
            total += v * (v - 1) // 2

print(total)

Solution (Python):
def main():
    N,p = map(int, input().split())
    S = input()
    S = S[::-1]

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

main()

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

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

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

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

print(ans)

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

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

Solution (Python):





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


"""
たとえばSが 123456789 だとすると
3456 = (3456789 - 789) // 1000
と表せる。
これがPで割り切れる場合、基本的には 3456789 と 789 がPで割り切れるとよい。
これはPと 10**x が互いに素の場合。
なので、10**x とPが互いに素の場合は、
・S[l:]をPで割った時余りがXXXになるものが何個、という情報を、Sの右端から集めていく。ただし、
・あるindexのlのS[l:]を見ているときに、その部分をPで割って余りがKになるなら、そのlに対してlより右にあるrについて、
　S[r:]をPで割った余りがKになるようにrを選んでS[l:r]を作ると、Pで割り切れる数字が得られる。その時点でのmod P = Kの個数に対応する。
　ただし、rに何も選ばない場合（lから端までを数字にする場合）もあるので、これも考慮に入れる。

Pが10と互いに素でない場合は、2と5がありうる。
これについて、それぞれ末尾が2の倍数か5の倍数であれば割り切れるので、
Sを左から見ていって、その数字が見つかれば、そのindexをふくむ左の位置で数字を作ればPで割れる数字ができる
"""

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

else:
    mod_P = [0] * P
    mod_P[0] += 1
    
    
    
    
    curr = 0
    for i in range(N):
        curr = curr + int(S[N-1-i]) * pow(10, i, P)
        curr %= P
        ans += mod_P[curr]
        mod_P[curr] += 1

print(ans)

Solution (Python):
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 c.values():
        if i > 1:
            a += i * (i-1) // 2


print(a)

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

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

if __name__ == '__main__':
    main()

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

Solution (Python):
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
from collections import deque, defaultdict
from itertools import combinations, permutations, combinations_with_replacement
from itertools import accumulate
from math import ceil, sqrt, pi

MOD = 10 ** 9 + 7
SIZE = 10 ** 6

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

answer = 0
if P == 2 or P == 5:
    for i, s in enumerate(S):
        if int(s) % P == 0:
            answer += i + 1
else:
    S = S[::-1]
    cnt = defaultdict(int)
    tmp = 0
    for i, s in enumerate(S):
        tmp += int(s) * pow(10, i, P)
        if tmp % P == 0:
            answer += 1
        answer += cnt[tmp % P]
        cnt[tmp % P] += 1

print(answer)

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

S = input()[::-1]

d = {}

ans = 0
if p == 2:
    for i in range(N):
        if S[i] in ['0','2','4','6','8']:
            ans += N-i
elif p==5:
    for i in range(N):
        if S[i] in ['0','5']:
            ans += N-i
else:
    d = defaultdict(lambda:0)
    n = 0
    for i in range(N):
        n += pow(10,i,p)*int(S[i])
        n %= p
        d[n] += 1
    ans += d[0]
    for k in d:
        ans += d[k]*(d[k]-1)//2
print(ans)

Solution (Python):
import sys
import math
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
from collections import deque
from bisect import bisect_left
from itertools import product
def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def LSI(): return list(map(int, list(sys.stdin.readline().rstrip())))
def LSI2(N): return [list(map(int, list(sys.stdin.readline().rstrip()))) for i in range(N)]
def S(): return sys.stdin.readline().rstrip()
def LS(): return sys.stdin.readline().split()
def LS2(N): return [sys.stdin.readline().split() for i in range(N)]
def FILL(i,h): return [i for j in range(h)]
def FILL2(i,h,w): return [FILL(i,w) for j in range(h)]
def FILL3(i,h,w,d): return [FILL2(i,w,d) for j in range(h)]
def FILL4(i,h,w,d,d2): return [FILL3(i,w,d,d2) for j in range(h)]
def sisha(num,digit): return Decimal(str(num)).quantize(Decimal(digit),rounding=ROUND_HALF_UP)

MOD = 998244353
INF = float("inf")
sys.setrecursionlimit(10**6+10)
input = sys.stdin.readline

N,P = MI()
S = S()
mod = 0
ans = 0
dic = {0:1}
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-1,-1,-1):
        mod = (mod+pow(10,(N-1-i),P)*int(S[i]))%P
        dic[mod] = dic.get(mod,0)+1
    for i in dic.values():
        ans += int(i*(i-1)/2)
print(ans)

Solution (Python):

import sys
from collections import defaultdict
N,P=map(int, sys.stdin.readline().split())
S=sys.stdin.readline().strip()

if P in (2,5):
    ans=0
    for i,x in enumerate(S):
        if int(x)%P==0:
            ans+=i+1
    print ans
else:
    L=[int(S)%P]
    for i,x in enumerate(S):
        L.append((L[-1]-int(x)*pow(10,N-1-i,P))%P)
    ans=0
    D=defaultdict(lambda: 0)
    for i in range(N,-1,-1):
        x=L[i]
        ans+=D[x]
        D[x]+=1
    print ans

Solution (Python):

import sys
from collections import defaultdict
N,P=map(int, sys.stdin.readline().split())
S=sys.stdin.readline().strip()

if P in (2,5):
    ans=0
    for i,x in enumerate(S):
        if int(x)%P==0:
            ans+=i+1
    print ans
else:
    S=S[::-1]   
    L=[0]
    for i,x in enumerate(S):
        x=int(x)
        L.append( (L[-1]+x*pow(10,i,P))%P ) 
    ans=0
    D=defaultdict(lambda: 0)
    for i in range(N,-1,-1):
        x=L[i]
        ans+=D[x]
        D[x]+=1
    print ans

Solution (Python):




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

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):
        now = (10 * now + int(S[i])) % p
        k = now * pow(10, (p - 2) * i, p) % p
        res += counter[k]
        counter[k] += 1
    print(res)
resolve()