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


def solve(N: int, P: int, S: str):
    if P == 2 or P ==5:
        answer = 0
        for i in range(N):
            if int(S[i])%P == 0:
                answer += i+1
        print(answer)
        return

    amari = [0]*N
    amari[N-1] = int(S[N-1])%P
    keta = 1
    for i in range(N-2,-1,-1):
        num = pow(10,keta,P)*int(S[i])
        amari[i]=(amari[i+1]+num)%P
        keta += 1
    from collections import Counter
    counter = Counter(amari)
    answer = 0
    for _,value in counter.items():
        answer += (value*(value-1))//2
    answer += amari.count(0)
    print(answer)  
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    P = int(next(tokens))  
    S = next(tokens)  
    solve(N, P, S)

if __name__ == '__main__':
    main()

Solution (Python):
from collections import Counter
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): 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 LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    n,p=MI()
    s=SI()
    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()
    aa=[int(c) for c in s[::-1]]
    cc=[0]
    ten=1
    for a in aa:
        cc.append((cc[-1]+a*ten)%p)
        ten=ten*10%p
    cnt=Counter(cc)
    ans=0
    for v in cnt.values():
        ans+=v*(v-1)//2
    print(ans)

main()

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

answer=0
if P==2 or P==5:
  for i in range(N):
    si=int(S[i])
    if si%P==0:
      answer+=i+1
else:
  mod_table=[0]*P
  mod_table[0]=1
  revS=S[::-1]
  
  modp=0
  mod10=1
  for i in range(N):
    mod10=(mod10*10)%P
    
    modp=(modp+mod10*int(revS[i]))%P
    mod_table[modp]+=1
    
  
  for i in range(P):
    answer+=mod_table[i]*(mod_table[i]-1)//2
  
print(answer)

Solution (Python):


import sys
from itertools import accumulate
from collections import Counter

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N, P = MAP()
A = list(map(int, input()))

if P == 2 or P == 5:
    ans = 0
    for i, a in enumerate(A):
        if a % P == 0:
            ans += i + 1
    print(ans)
    exit()

acc = [0] * N
cur = A[-1] % P
acc[-1] = cur
k = 1
for i in range(N-2, -1, -1):
    cur += pow(10, k, P) * A[i]
    cur %= P
    acc[i] = cur
    k += 1
acc = acc + [0]

C = Counter(acc)
ans = 0
for v in C.values():
    ans += v * (v-1) // 2
print(ans)

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

N, P = map(int, input().split())
S = list(map(int, list(input().rstrip())))
ans = 0
if P == 2 or P == 5:
    for i in range(N):
        if S[i] % P == 0:
            ans += i + 1
else:
    U = [0] * (N+1)
    count = [0] * P
    count[0] = 1
    factor = 10
    for i in range(N)[::-1]:
        U[i] = (S[i] * factor + U[i+1]) % P
        factor = factor * 10 % P
        ans += count[U[i]]
        count[U[i]] += 1
print(ans)

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

ans=0
if 10%P==0:
    for r in range(N):
        if int(S[r])%P==0:
            ans+=r+1
else:
    d=[0 for _ in range(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=(ten*10)%P
    cnt=[0 for _ in range(P)]
    for i in range(N, -1, -1):
        ans+=cnt[d[i]]
        cnt[d[i]]+=1
print(ans)

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

mod = p
l = 100

M = [1]  
m = 1
for i in range(1, l):
    m = (m * i) % mod
    M.append(m)

def pow(x, y, mod):  
    ans = 1
    while y > 0:
        if y % 2 == 1:
            ans = (ans * x) % mod
        x = (x**2) % mod
        y //= 2
    return ans

def inv(x, mod):  
    return pow(x, mod-2, mod)

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

P = [0] * p
P[0] = 1

ans = 0
v = 0
S = [int(s[i]) for i in range(n-1,-1,-1)]

if p==2 or p==5:
    for i in range(n):
        ans += (int(s[i]) % p == 0) * (i+1)
else:
    for i in range(n):
        v = (v + T[i]*S[i]) % p
        ans += P[v]
        P[v] += 1
        

print(ans)

Solution (Python):
from collections import defaultdict
n,p=map(int,input().split())
S=input()
ans=0
if p==5:
    for i in range(n):
        if int(S[i])==5 or int(S[i])==0:
            ans+=i+1
elif p==2:
    for i in range(n):
        if int(S[i])%2==0:
            ans+=i+1
else:
    kouho=defaultdict(int)
    s=0
    ruijo=1
    for i in range(n):
        ruijo%=p
        s+=int(S[-(i+1)])*(ruijo)
        a=s%p
        kouho[a]+=1
        ruijo*=10
    for j in range(p):
        z=kouho[j]
        ans+=z*(z-1)//2
    ans+=kouho[0]
print(ans)

Solution (Python):
from itertools import accumulate
def main():
    N,P=map(int, input().split())
    S=input()
    B=[(ord(c)-ord("0"))%P for c in S]
    ans=0
    if P==2 or P==5:
        for i,b in enumerate(B,1):
            if b==0:
                ans+=i
    else:
        D={0:1}
        x=0
        y=1
        for b in B[::-1]:
            x=(x+(b*y))%P
            D.setdefault(x,0)
            ans+=D[x]
            D[x]+=1
            y=(y*10)%P
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
from collections import defaultdict

def answer():
    n, p = map(int, input().split())
    s = input()
    m = defaultdict(int)
    ans = 0
    if p == 2 or p == 5:
        for i, ss in enumerate(s):
            if int(ss) % p == 0:
                ans += i + 1
        return ans
    sss = 0
    for i, ss in enumerate(s[::-1]):
        sss = (sss + pow(10, i, p) * int(ss)) % p
        m[sss] += 1
    m[0] += 1
    for i in range(p):
        if m[i] >= 2:
            ans += m[i] * (m[i] - 1) // 2
    return ans

print(answer())

Solution (Python):
from collections import *
from itertools import *
from bisect import *
from heapq import *
import copy
import math
from fractions import gcd

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

if P in [2,5]:
    count=0
    for i in range(N):
        if int(S[i])%P==0:
            count+=i+1
    print(count)
    exit()
S=list(S)
S.reverse()
nlst=[0,int(S[0])%P]
for i in range(1,N):
    nlst.append((nlst[i]+int(S[i])*pow(10,i,P))%P)

count=0
for i,n in Counter(nlst).most_common():
    count+=n*(n-1)//2

print(count)

Solution (Python):
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
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()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n,p = inpl()
s = input()[::-1]
res = 0
if p == 2 or p == 5:
    s = s[::-1]
    for i,t in enumerate(s):
        if int(t)%p == 0: 
            res += i+1
    print(res)
    quit()
now = 0
d = [0] * p
d[0] = 1
for i,t in enumerate(s):
    now += int(t) * pow(10,i,p)
    now %= p
    d[now] += 1
for i in range(p):
    v = d[i]
    res += v*(v-1)//2
print(res)

Solution (Python):

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

S = input()


if P not in [2,5]:

    dic = {}
    dic[0] = 1
    now = 0
    ans = 0

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

    print (ans)

elif P == 2:

    ans = 0
    for i in range(N):

        if int(S[i]) % 2 == 0:
            ans += i+1

    print (ans)

else:

    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()
ans = 0
C = [0] * P
C[0] = 1
a = 0
if P in (2, 5):
    print(sum([i+1 for i, s in enumerate(S) if int(s) % P == 0]))
    exit()
    
for i, s in enumerate(S[::-1]):
    a = (a + int(s) * pow(10, i, P)) % P
    ans += C[a]
    C[a] += 1
print(ans)

Solution (Python):
import collections

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)
else:
    S = S[::-1]
    a, temp = [int(S[0]) % P], 1
    for i in range(1, N):
        temp *= 10
        temp %= P
        a.append((a[i-1] + (int(S[i]) % P * temp) % P) % P)

    c = collections.Counter(a)
    if 0 in c:
        ans += c[0]
        ans += c[0] * (c[0] - 1) // 2
        del c[0]
    for x in c.keys():
        ans += c[x] * (c[x]-1) // 2 
    print(ans)

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

ans = 0

d = {i:0 for i in range(p)}
d[0] = 1

ap = 1
if p not in [2, 5]:
    pre = 0
    for si in s[::-1]:
        si = int(si)
        a = (si * ap + pre) % p
        ans += d[a]
        d[a] += 1
        pre = a
        ap = (ap * 10) % p
else:
    for i, si in enumerate(s):
        if int(si) % p == 0:
            ans += i+1
print(ans)

Solution (Python):
import sys

from collections import Counter

def main():
    N,P = map(int,input().split())
    s = input()
    l = len(s)
    ans = 0
    if 10%P == 0:
        for i,st in enumerate(s[::-1]):
            num = int(st)
            if num%P == 0:
                ans += l-i
    else:
        rest = [0]
        t = 1
        for st in s[::-1]:
            num = int(st)%P
            rest.append(num*t%P)
            t = t*10%P
            
        for i in range(l):
            rest[i+1] += rest[i]

        for i in range(l):
            rest[i+1] %= P
            
        c = Counter(rest)
        c = list(c.values())
        for num in c:
            ans += num*(num-1)//2
    
    print(ans)
    
if __name__ == "__main__":
    main()

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

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

else:
    data = [0] * P
    s = int(S)
    x = 1 
    y = 0 
    for i in range(N):
        y += int(S[N-i-1]) * x
        y %= P
        data[y] += 1
        x *= 10
        x %= P
    
    ans = data[0]
    for i in range(P):
        ans += (data[i]*(data[i]-1))//2

print(ans)

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
import pprint
sys.setrecursionlimit(10 ** 9)


INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n, p = LI()
D = defaultdict(int)
D[0] += 1
s = S()
ans = 0
rem = 0
if p == 2 or p == 5:
    for i in range(n - 1, -1, -1):
        if int(s[i]) % p == 0:
            ans += i + 1
    print(ans)
    exit()


k = 1
for i in range(n - 1, -1, -1):
    d = int(s[i])
    rem = (k * d + rem) % p
    k = k * 10 % p
    ans += D[rem]
    D[rem] += 1


print(ans)

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

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

if mod == 2 or mod == 5:
    ans = 0
    for i, s in enumerate(S):
        if int(s)%mod==0:
            ans += i+1
else:
    dp = [0]
    t = 1
    for s in reversed(S):
        dp.append((dp[-1]+int(s)*t)%mod)
        t = t*10%mod

    ans = 0
    C = Counter(dp)
    for v in C.values():
        ans += v*(v-1)//2

print(ans)

Solution (Python):
from collections import defaultdict
def main():
    n,p=map(int,input().split())
    S=[int(x) for x in tuple(input().strip())]
    if p==2 or p==5:
        ans=0
        for i,s in enumerate(S):
            if s%p==0:
                ans+=(i+1)
        return ans
    d=defaultdict(int)
    tmp=0
    digit=1
    ans=0
    for i,s in enumerate(reversed(S)):
        tmp+=s*digit
        digit*=10
        digit%=p
        r=tmp%p
        ans+=d[r]
        d[r]+=1
    ans+=d[0]
    return ans
    
if __name__=='__main__':
    print(main())

Solution (Python):
N, P = map(int, input().split())
S = input()
ans = 0
C = [0] * P
C[0] = 1
a = 0
if P in (2, 5):
    for i, s in enumerate(S):
        if int(s) % P == 0:
            ans += i + 1
    print(ans)
else:
    for i, s in enumerate(S[::-1]):
        a = (a + int(s) * pow(10, i, P)) % P
        ans += C[a]
        C[a] += 1
    print(ans)

Solution (Python):
n, p = map(int, input().split())
s = input()
count = 0
if p == 2 or p == 5:
  for i in range(n):
    if int(s[i]) % p == 0:
      count += i + 1
  print(count)
else:
  mod = [0] * p
  mod[0] = 1
  tmp = 0
  ten = 1
  for i in s[::-1]:
    ten = ten * 10 % p
    tmp = (tmp + int(i) * ten) % p
    mod[tmp] += 1
  for m in mod:
    count += m * (m - 1) // 2
  print(count)

Solution (Python):
import sys
from collections import defaultdict as dd
input = sys.stdin.readline
N, P = map(int, input().split())
S = list(map(int, list(input())[: -1]))
rcs = [0] * (N + 1)
for i in range(N, 0, -1): rcs[i - 1] = (rcs[i] + S[i - 1] * pow(10, N - i, P)) % P

d = dd(list)
for i in range(N + 1):d[rcs[i]].append(i)
res = 0
if P == 2 or (P == 5):
  for i in range(N - 1, -1, -1):
    res += (S[i] % P == 0) * (i + 1)
  print(res)
  exit(0)
table = [0] * P
for i in range(N, -1, -1):
  x = rcs[i]
  res += table[x]
  table[x] += 1
print(res)

Solution (Python):
NN = 2020202
MOD = 10**9+7
INF = float("inf")

n, p = map(int, input().split())
S = input()
pl = len(str(p))

if p == 2 or p == 5:
    count = 0
    for i in range(len(S)):
        if int(S[i])%p == 0:
            count += i+1
            

    print(count)

else:
    d = [0] * p
    d[0] = 1
    val = 0
    dec = 1

    for i in range(len(S)-1, -1, -1):
        val = (int(S[i])*dec+val)%p
        dec = (dec*10)%p
        d[val] += 1

    
    ans = 0
    for e in d:
        ans += (e*(e-1))//2
    print(ans)

Solution (Python):
import sys
input=sys.stdin.readline
n,p=map(int,input().split())
s=input().rstrip()
if p==2:
    ans=0
    for i in range(n):
        if int(s[i])%2==0:
            ans+=i+1
elif p==5:
    ans=0
    for i in range(n):
        if int(s[i])==0 or int(s[i])==5:
            ans+=i+1
else:
    count=[0]*p
    x=0
    y=1
    count[0]=1
    for i in range(n-1,-1,-1):
        x=x+y*int(s[i])
        x=x%p
        count[x]+=1
        y=(y*10)%p
    ans=0
    for i in count:
        ans+=i*(i-1)//2
print(ans)

Solution (Python):
from collections import Counter

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

if p == 2 or p == 5:
    d = {2: "02468", 5: "05"}
    ans = 0
    for i, e in enumerate(s, 1):
        if e in d[p]:
            ans += i

    print(ans)

else:
    li = [0]
    power = 1
    for e in s[::-1]:
        power *= 10
        power %= p
        li.append((li[-1] + int(e) * power) % p)

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

    print(ans)

Solution (Python):

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    N,P=MI()
    s=input()
    ans=0
    if P==2 or P==5:
        for i in range(N):
            t=int(s[i])
            if t%P==0:
                ans+=i+1
            
    else:
        ans=0
        t=0
        mod=[0]*P
        mod[0]=1
        for i in range(N):
            t=t+int(s[N-i-1])*pow(10,i,P)
            t=t%P
            mod[t]+=1
            if mod[t]>=2:
                ans+=mod[t]-1
                

            

    print(ans)   
        
    
            
    
        
    

main()

Solution (Python):
def main():
    n, p = map(int, input().split())
    s = list(map(int, list(input())))
    now = 1
    now2 = 0

    dp = [0]*p
    cnt = 0
    if p != 5:
        for i in s:
            now2 = (now2*10+i) % p
            dp[((i-now2) % p)*pow(now, p-2, p) % p] += 1
            cnt += dp[((-now2) % p)*pow(now, p-2, p) % p]
            now = (now*10) % p
    else:
        for j, i in enumerate(s):
            if i in [0, 5]:
                cnt += j+1
    print(cnt)


main()

Solution (Python):
def solve(n, p, s):
    res = 0
    if p == 2 or p == 5:
        for i in range(n):
            if int(s[i]) % p == 0:
                res += i + 1
        return res

    mod_count = [0] * p
    temp = 0
    pow_10_i_p = [0] * n
    pow_10_i_p[0] = 1
    for i in range(1, n):
        pow_10_i_p[i] = pow_10_i_p[i - 1] * 10 % p
    for i in range(n):
        temp = (temp + pow_10_i_p[i] * int(s[-(i + 1)])) % p
        mod_count[temp] += 1
    res += mod_count[0]
    for i in range(p):
        res += mod_count[i] * (mod_count[i] - 1) // 2
    return res


def main():
    n, p = map(int, input().split())
    s = input()
    res = solve(n, p, s)
    print(res)


def test():
    assert solve(4, 3, "3543") == 6
    assert solve(4, 2, "2020") == 10
    assert solve(20, 11, "33883322005544116655") == 68


if __name__ == "__main__":
    test()
    main()

Solution (Python):
from collections import defaultdict

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

if P == 2 or P == 5 :
  ret = 0
  for i, v in enumerate(S) :
    if int(v) % P == 0 :
      ret += i + 1
  print(ret)

else :
  mem = defaultdict(int)
  mem[0] += 1

  T = [0]
  dec = 1
  x = 0
  for s in S[::-1] :
    s = int(s)
    x = (dec * s + x) % P
    dec = dec * 10 % P
    T.append(x)
    mem[x] += 1

  ret = 0
  for i, t in enumerate(T) :
    ret += mem[t] - 1
    mem[t] -= 1
    
  print(ret)

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

  ans = 0

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

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

  rem_list = [0] * p
  cof = 1
  prev_rem = 0
  
  for i in range(n):
    rem = (int(s[n-1-i]) * cof + prev_rem) %  p
    ans += rem_list[rem]
    if rem == 0:
      ans += 1      
    rem_list[rem] += 1

    prev_rem = rem
    cof *= 10
    cof %= p

  print(ans)

if __name__ == "__main__":
  main()

Solution (Python):
from collections import Counter

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

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

    print(ans)

else:
    li = [0]
    for i, e in enumerate(s[::-1], 1):
        li.append((li[-1] + int(e) * pow(10, i, p)) % p)

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

    print(ans)

Solution (Python):

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

rem=[0]*p
remls=[0]*n
remnow=0
for i in range(n-1,-1,-1):
    remnow = (remnow+int(s[i])*pow(10, n-1-i, p))%p
    rem[remnow]+=1
    remls[i]=remnow

ans=0
remnow2=0
remdiff=1
for i in range(n-1,-1,-1):
    remdiff2=(remdiff-remnow2)%p
    idx=-remnow2*pow(remdiff2,p-2,p)%p
    ans+=rem[idx]
    remnow2-=int(s[i])
    remnow2%=p
    remnow2*=pow(10,p-2,p)
    remnow2%=p
    remdiff-=int(s[i])
    remdiff%=p
    remdiff*=pow(10,p-2,p)
    remdiff%=p
    rem[remls[i]]-=1

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

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


print(ans)

Solution (Python):
n,p=map(int,input().split())
s=input()[::-1]
A=[0]*n
A[0]=int(s[0])%p
t=10
for i in range(1,n):
  A[i]=(int(s[i])*t+A[i-1])%p
  t=(t*10)%p
ans=0
import collections
D=collections.defaultdict(int)
D[0]=1
if p!=2 and p!=5:
  for i in range(n):
    ans+=D[A[i]]
    D[A[i]]+=1
  print(ans)
else:
  s=s[::-1]
  ans=0
  for i in range(n):
    if int(s[i])%p==0:
      ans+=i+1
  print(ans)

Solution (Python):
def main():
    N, P = list(map(int, input().split()))
    S = map(int, input())
    if P == 2 or P == 5:
        r = 0
        for i, s in enumerate(S):
            if s % P == 0:
                r += (i + 1)
        return r

    g1 = [1, 1]
    g2 = [1, 1]
    inverse = [0, 1]
    mod = P
    for i in range(2, P):
        g1.append((g1[-1] * i) % mod)
        inverse.append((-inverse[mod % i] * (mod // i)) % mod)
        g2.append((g2[-1] * inverse[-1]) % mod)

    H = [0] * N
    h = 0
    for i, s in enumerate(S):
        h = (h * 10 + s) % P
        H[i] = h
    K = [0] * P
    K[0] = 1
    shift = 1
    r = 0
    for i, h in enumerate(H):
        t = (h * inverse[shift]) % P
        r += K[t]
        K[(h * inverse[shift]) % P] += 1
        shift = (shift * 10) % P

    return r
   

print(main())

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

n,p = map(int,input().split())
s = list(input())
for i in range(n):
    s[i] = int(s[i])


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

else:
    d = 1
    q = [0]
    for i in range(n-1,-1,-1):
        q.append((q[-1]+s[i]*d)%p)
        d = d*10%p
    q.sort()
    res = 0
    i = 0
    while i < n+1:
        k = bisect.bisect_right(q,q[i])
        c = k-i
        res += c*(c-1)//2
        i = k
    print(res)

Solution (Python):
import sys

stdin = sys.stdin

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

n,p = nm()
s = list(map(int, list(ns())))
ans = 0
if p == 2:
  for i in range(n):
    if s[i]%2 == 0:
      ans += i+1
  print(ans); exit(0)
if p == 5:
  for i in range(n):
    if s[i]%5 == 0:
      ans += i+1
  print(ans); exit(0)
   
g = [0]*(n+1)
d = [0]*p
d[0] = 1
t = 1
for i in range(n-1,-1,-1):
    g[i] = (g[i+1] + s[i]*t)%p
    ans += d[g[i]]
    d[g[i]] += 1
    t = (t*10)%p
print(ans)

Solution (Python):
n, p = map(int, input().split())
s =list(str(input()))
s = [int(c) for c in s]
s.reverse()

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









def power(a, n, mod):
  bi=str(format(n,"b")) 
  res=1
  for i in range(len(bi)):
    res=(res*res) %mod
    if bi[i]=="1":
      res=(res*a) %mod
  return res

temp = 0
cum = [0]*n
for i in range(n):
    temp += s[i]*power(10, i, p)
    temp = temp%p
    cum[i] = temp
cum = [0]+cum



d = {}
ans = 0
for i in range(n+1):
  if cum[i] not in d:
    d[cum[i]] = 1
  else:
    ans += d[cum[i]]
    d[cum[i]] += 1
print(ans)

Solution (Python):
N, P = map(int, input().split())
S = input()
l = list(reversed(list(S)))
each = [0]*N
ten = 1
for i in range(N):
    each[i] = int(l[i])*ten%P
    ten = ten*10%P
Sum = [0]*N
num = 0
for i in range(N):
    num = (num + each[i])%P
    Sum[i] = num
Sum.sort()
fac = Sum[0]
ans = 0
cnt = 0
for i in range(N):
    if Sum[i] == 0:
        ans += 1
    if Sum[i] == fac:
        cnt += 1
    else:
        ans += cnt*(cnt-1)//2
        cnt = 1
        fac = Sum[i]
ans += cnt*(cnt-1)//2
if P != 5 and P != 2:
    print(ans)
else:
    ans = 0
    for i in range(N):
        if int(l[i])%P == 0:
            ans += N-i
    print(ans)

Solution (Python):
from collections import deque

import numpy as np

n, p = map(int, input().split())
d = deque(input())

ans = 0
if p == 2 or p == 5:
  for i in range(n):
    k = int(d.popleft())
    if k % p == 0:
      ans += i + 1
else:
  sub = [0 for i in range(n)]
  wk = 0
  for i in range(n):
    k = int(d.pop())
    wk = (wk + k * pow(10, i, p)) % p
    sub[i] = wk
  ans = 0
  dic = {}
  for i in range(n):
    if sub[i] == 0:
      ans += 1
    if sub[i] in dic.keys():
      ans += dic[sub[i]]
      dic[sub[i]] = dic[sub[i]] + 1
    else:
      dic[sub[i]] = 1

print(ans)

Solution (Python):
n,p=map(int,input().split())
S=input()[::-1]
if p==2 or p==5:
    ans=0
    for i in range(n):
        if int(S[i])%p==0:
            ans+=n-i
    print(ans)
    exit()
mod=[0]*(n+1)
mod_l=[0]*p
mod_10=[1]*n
for i in range(n-1):
    mod_10[i+1]=mod_10[i]*10%p
for i in range(n):
    mod[i+1]=(mod[i]+int(S[i])*mod_10[i])%p
for i in range(n+1):
    mod_l[mod[i]]+=1
ans=0
for i in range(p):
    ans+=mod_l[i]*(mod_l[i]-1)//2
print(ans)

Solution (Python):
from itertools import accumulate
from collections import Counter

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

if P == 2 or P == 5:
    s_can = [1 if i % P == 0 else 0 for i in S]
    
    
    answer = 0
    for idx, i in enumerate(s_can[::-1]):
        if i:
            answer += N - idx
    print(answer)
else:
    s = []
    t = 1
    for i in S[::-1]:
        r = i % P
        s.append(r * t % P)
        t = t * 10 % P

    s = list(accumulate([0] + s))
    s = [i % P for i in s]
    c = Counter(s)
    answer = 0
    for i in c.values():
        answer += i * (i - 1) // 2

    print(answer)

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

import sys
if p==2 or p==5:
    count=0
    for i in range(n):
        if int(s[i])%p==0:
            count+=i+1
    print(count)

    sys.exit()
def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0

def modinv(a, m):
    g, x, y = xgcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m
inv=modinv(10,p)
pmod=[0]*p
pmod[0]=0
buf=0
count=0
for i in range(n):
    buf*=10
    buf+=int(s[i])
    buf%=p
    idx=buf*pow(inv,i,p)
    idx%=p
    count+=pmod[idx]
    pmod[idx]+=1

print(count+pmod[0])

Solution (Python):
N ,P= map(int,input().split())
S = input()
ten = [0] * len(S)
for i in range(len(S)):
    if i == 0:
        ten[i] = 1
    else:
        ten[i] = (ten[i-1] * 10) %P
if P != 2 and P != 5:
    mod_dic ={}
    mod_dic[0] = 1
    mod = 0
    for i in range(len(S)):
        mod +=  int(S[N-1-i]) * ten[i]
        mod = mod%P
        if mod not in mod_dic:
            mod_dic[mod] = 1
        else:
            mod_dic[mod] += 1
        ans = 0
    a = list(mod_dic.values())
    for i in range(len(a)):
            ans += a[i] * (a[i]-1) //2
    print(ans)
elif P == 2:
    ans = 0
    for i in range(len(S)):
        if int(S[len(S)-1-i])%2 == 0:
            ans += N-i
    print(ans)
else:
    ans = 0
    for i in range(len(S)):
        if int(S[len(S)-1-i])%5 == 0:
            ans += N-i
    print(ans)

Solution (Python):
n,p = (int(num) for num in input().split())
s = input()
s = s[::-1]

if p != 2 and p != 5:
    dec = [1] * n
    for i in range(1,n):
        dec[i] = (dec[i - 1] * 10) % p
    s_mod = [0] * n
    for i in range(n):
        s_mod[i] = (int(s[i]) * dec[i]) % p

    
    

    cumsum = [0] * (n + 1)
    cnt = [1] + [0] * (p - 1)
    for i in range(n):
        cumsum[i + 1] = (cumsum[i] +  s_mod[i]) % p
        cnt[cumsum[i + 1]] += 1
    
    

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

Solution (Python):
import sys, collections
range = xrange
input = raw_input

n, p = [int(x) for x in input().split()]
A = [ord(x) - 48 for x in input()]


if p == 2 or p == 5:
    ans = 0
    for i in range(n):
        if A[i]%p == 0:
            ans += i + 1
    print ans
    sys.exit()


DP = [0]*p
ans = 0
POW = 1
ind0 = 0
for a in reversed(A):
    DP[ind0] += 1
    
    ind0 = (a * POW + ind0) % p
    ans += DP[ind0]
    POW = POW * 10 % p
print ans

Solution (Python):
def power(a, b, P):
	if b == 0:
		return 1
	elif b == 1:
		return a % P
	elif b % 2 == 0:
		return (power(a, b//2, P) ** 2) % P
	else:
		return (power(a, b//2, P) ** 2 * a) % P
 

N, P = (int(i) for i in input().split())
S = input()
l = [0]*N
ls = [0]*(N+1)
if P != 2 and P != 5:
    po = [1]*N
    for i in range(N-1):
        po[i+1] = (po[i]*10)%P
    d = [0]*P
    d[0] = 1
    b = 0
    for i in range(N):
        a = int(S[N-1-i]) * po[i]
        l[i] = a%P
        b += l[i]
        b %= P
        d[b] += 1
    ans = 0
    for a in d:
        ans += (a-1)*a//2
    print(ans)
else:
    ans = 0
    for i in range(N):
        if int(S[i]) % P == 0:
            ans += (i+1)
    print(ans)