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

u = [ 0 for i in range(n+1)]

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



def solve(u, s):
    if p == 2 or p == 5:
        return solve1(s)
    else:
        return solve2(u)


def solve1(s):
    ans = 0
    for i in range(n):
        if s[i] % p == 0:
            ans += i+1
    return ans

def solve2(u):
    ans = 0
    cnt = [0 for i in range(p)]
    for i in range(n+1):
        cnt[u[i]] += 1
    for i in range(p):
        q = cnt[i]
        ans += (q * (q-1)) // 2
    return ans

print(solve(u, s))

Solution (Python):
N, P = map(int, input().split())
S = input()
ans = 0
if P in [2, 5]:
    for l, s in enumerate(S, 1):
        if int(s) % P == 0: ans += l
else:
    counter = [0] * P
    counter[0] = 1
    prev = 0
    temp = 1
    for i, s in reversed(list(enumerate(S))):
        num = (int(s) * temp + prev) % P
        ans += counter[num]
        counter[num] += 1
        prev = num
        temp = (temp * 10) % P
print(ans)

Solution (Python):



N, P = map(int, input().split())
S = list(map(int,list(input())))
U = [0 for i in range(N+1)]

d = 1
for i in range(N):
    U[N-(i+1)] = (U[N-i] + S[N-1-i] * d) % P
    d = 10 * d % P
    
def solve(U,S):
    if P == 2 or P == 5:
        return solve1(S)
    else:
        return solve2(U)
    
def solve1(S):
    ans = 0
    for i in range(N):
        if S[i] % P == 0:
            ans += i+1
    return ans

def solve2(U):
    ans = 0
    cnt = [0 for i in range(P)]
    for i in range(N+1):
        cnt[U[i]] += 1
    for i in range(P):
        p = cnt[i]
        ans += (p * (p-1)) // 2
    return ans

print(solve(U,S))

Solution (Python):
import sys
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

S.reverse()

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

else:
    cummod = [0] * P

    d = 1
    prev = 0
    for i in range(N):
        m = (S[i] * d) % P
        m += prev
        m %= P
        cummod[m] += 1
        d *= 10
        d %= P
        prev = m

    

    for n in cummod:
        if n <= 1:
            continue
        ans += n * (n - 1) // 2

    ans += cummod[0]

print(ans)

Solution (Python):
import sys
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

S.reverse()

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

else:
    cummod = [0] * P

    d = 1
    prev = 0
    for i in range(N):
        m = (S[i] * d) % P
        m += prev
        m %= P
        cummod[m] += 1
        d *= 10
        d %= P
        prev = m

    cummod[0] += 1

    for n in cummod:
        if n <= 1:
            continue
        ans += n * (n - 1) // 2

    

print(ans)

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

count=0
if p==2:
    for i in range(n):
        if int(s[i])%2==0:
            count+=i+1
elif p==5:
    for i in range(n):
        if int(s[i])%5==0:
            count+=i+1
else:
    lis=[1]
    for i in range(n-1):
        lis.append((lis[i]*10)%p)
    lis.reverse()
    for i in range(n):
        lis[i]=(int(s[i])*lis[i])%p
    unum=[1]
    for i in range(p-1):
        unum.append(0)
    num=0
    for i in range(n):
        num=(num+lis[n-i-1])%p
        unum[num]+=1
    for i in range(p):
        unumi=unum[i]
        count+=(unumi*(unumi-1))*0.5
print(round(count))

Solution (Python):

N,P=map(int,input().split())
S=input()
ans=0
if P in (2,5):
    for i,s in enumerate(S):
        if int(s)%P==0:
            ans+=i+1
else:
    cnt=[0 for _ in range(P)]
    CS=0
    PLC=1
    for s in S[::-1]:
        tmp=(int(s)*PLC)%P
        CS=(CS+tmp)%P
        cnt[CS]+=1
        PLC=(PLC*10)%P
        
        
    for c in cnt:
        ans+=c*(c-1)//2
    ans+=cnt[0]
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(100000000)

def main():
    n,p=map(int,input().split())
    s=list(map(int,list(input())))
    
    if p==2 or p==5:
        cnt=0
        for i in range(n):
            if s[i]%p==0:
                cnt+=i+1
        print(cnt)

    else:
        pmod=[0]*p
        cummod=0
        ten=1
        for i in range(n):
            cummod+=s[-i-1]*ten
            cummod%=p
            pmod[cummod]+=1
            ten*=10
            ten%=p
        
        ans=pmod[0]
        for i in range(p):
            k=pmod[i]
            if k >=2 :
                ans+=k*(k-1)//2
        print(ans)
if __name__=='__main__':
    main()

Solution (Python):
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True  and False
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

n,p = inm()
acc = [0]*(n+1)
a = [0]*(n+1)
ss = ins()
s = ss[::-1]
if p in [2,5]:
    x = 0
    for i in range(n):
        if int(s[i])%p==0:
            x += n-i
    print(x)
    exit()

q = 1
for i in range(n):
    x = int(s[i])
    r = q*x
    acc[i+1] = (acc[i]+r)%p
    
    q = (q*10)%p
ddprint(acc)
h = [0]*p
for i in range(n+1):
    h[acc[i]] += 1
ddprint(h)
sm = 0
for i in range(p):
    x = h[i]
    sm = (sm+x*(x-1)//2)
print(sm)

Solution (Python):
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):
    ans = 0
    last_mod=0
    mods = [0]*p
    mods[0] = 1 
    digit = 1
    for i in range(n-1,-1,-1): 
        last_mod = (last_mod + int(s[i])*digit)%p 
        ans += mods[last_mod] 
        mods[last_mod] += 1 
        digit=digit*10%p 
    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 defaultdict
n,p = map(int,input().split())
s = input()

sur1 = [int(s[0]) % p]
sur2 = [int(s[-1]) % p]
sur10 = [1 % p]
for i in range(n-1):
    sur1 += [(sur1[i] * 10 + int(s[i+1])) % p]
    sur10 += [(sur10[i] * 10) % p]
    sur2 += [(sur2[i] + sur10[i+1] * int(s[-i-2])) % p]

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

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

d = defaultdict(int)
for x in sur2:
    d[x] += 1

for k,v in d.items():
    if k == 0:
        ans += v * (v+1) // 2
    else:
        ans += v * (v-1) // 2
print(ans)

Solution (Python):
from sys import stdin
def main():
    readline=stdin.readline
    N,P=map(int,readline().split())
    S=readline().strip()
    r=[0]*(N+1)

    if P!=2 and P!=5:
        now=1
        for i in range(N):
            a=(int(S[N-i-1])*now)%P
            r[i+1]=(a+r[i])%P
            now*=10
            now%=P
        
        d=dict()
        for n in range(P):
            d[str(n)]=0
        d["0"]=1

        ans=0
        for i in range(1,N+1):
            ans+=d[str(r[i])]
            d[str(r[i])]+=1
            
        print(ans)

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

        print(ans)

if __name__=="__main__":
    main()

Solution (Python):
import sys

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

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

last_mod = 0
keta_mod = 1
mod_array = [0] * p
mod_array[0] = 1



for i in reversed(range(len(s))):
  tmp = int(s[i]) * keta_mod
  last_mod = (last_mod + tmp) % p
  keta_mod = (keta_mod * 10) % p
  mod_array[last_mod] += 1
  
ans = 0
for v in mod_array:
  ans += v * (v-1) // 2
  
print(ans)

Solution (Python):

N,P=map(int,input().split())
S=input()
ans=0
if P in (2,5):
    for i,s in enumerate(S):
        if int(s)%P==0:
            ans+=i+1
else:
    cnt=[0 for _ in range(P)]
    CS=0
    PLC=1
    for s in S[::-1]:
        tmp=(int(s)*PLC)%P
        CS=(CS+tmp)%P
        cnt[CS]+=1
        PLC=(PLC*10)%P
        
        
    for c in cnt:
        ans+=c*(c-1)//2
    ans+=cnt[0]
print(ans)

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

ans = 0

if P in (2, 5):
    for i, s in enumerate(S):
        if int(s) % P == 0:
            ans += i + 1
else:
    count = [0] * P
    count[0] = 1
    u = 0
    for i, s in enumerate(reversed(S)):
        u = (int(s) * pow(10, i, P) + u) % P
        ans += count[u]
        count[u] += 1

print(ans)

Solution (Python):
def main():
  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:
    
    
    
    
    
    
    
    d = {}
    r = 0
    for i in range(N):
      
      
      r = (r + int(S[N-1-i])*pow(10,i,P))%P
      if r in d:
        d[r] += 1
      else:
        d[r] = 1
    if 0 in d:
      d[0] += 1
    for k,v in d.items():
      ans += v*(v-1)//2
  
  print(ans)

if __name__ == '__main__':
  main()

Solution (Python):
n,p=map(int,input().split())
rem=[0]*n
cnt=[0]*p
s=input()[::-1]
if p==5:
    s=s[::-1]
    ans=0
    for i in range(n):
        if int(s[i])%5==0:
            ans+=i+1
    print(ans)
    exit()
if p==2:
    s=s[::-1]
    ans=0
    for i in range(n):
        if int(s[i])%2==0:
            ans+=i+1
    print(ans)
    exit()
kake=1
for i in range(n):
    rem[i]=rem[i-1]+int(s[i])*kake
    rem[i]%=p
    cnt[rem[i]]+=1
    kake*=10
    kake%=p
    
ans=0
for i in range(p):
    ans+=cnt[i]*(cnt[i]-1)//2
print(ans+cnt[0])

Solution (Python):
def main():
  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:
    
    
    
    
    
    
    
    d = {}
    r = 0
    for i in range(N):
      r = (r+int(S[N-1-i])*pow(10,i,P))%P
      if r in d:
        d[r] += 1
      else:
        d[r] = 1
    if 0 in d:
      d[0] += 1
    for k,v in d.items():
      ans += v*(v-1)//2
  
  print(ans)

if __name__ == '__main__':
  main()

Solution (Python):
n,p = map(int, input().split())
s = list(map(int, list(input())))
if p in (2, 5):
  print(sum(i+1 for i in range(n) if s[i]%p == 0))
  exit(0) 
ans = g = 0
d = [0]*p
d[0] = 1
t = 1
for i in range(n-1,-1,-1):
    g = (g + s[i]*t)%p
    ans += d[g]
    d[g] += 1
    t = (t*10)%p
print(ans)

Solution (Python):
import math
import collections

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

ans = 0
juu = 1
S = S[::-1]
amari = 0
amaris = [0] * (P) 
if P == 2 or P == 5:
    for i,c in enumerate(S):
        n = int(c)
        if n % P == 0:
            ans += N - i
else:


    for c in S:
        i = int(c)
        amari += (i * juu)
        amari %= P
        amaris[amari] += 1
        juu *= 10
        juu %= P


    amaris[0] += 1
    for temp in amaris:
        ans += temp * (temp - 1) //2
print(ans)

Solution (Python):
def main():
    N, P = map( int ,input().split())
    S = [ int(s) for s in list(input().strip())][::-1]
    if P == 2 or P == 5:
        ans = 0
        for i in range(N):
            if S[i]%P == 0:
                ans += N-i
        print(ans)
        return
    L = [0]*P
    L[0] = 1
    t = 0
    s = 1
    for z in S:
        t = (z*s+t)%P
        L[t] += 1
        s = s*10%P
    ans = 0
    for l in L:
        ans += l*(l-1)//2
    print(ans)
    
if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline
def main():
    N, P = map( int ,input().split())
    S = [ int(s) for s in list(input().strip())][::-1]
    if P == 2 or P == 5:
        ans = 0
        for i in range(N):
            if S[i]%P == 0:
                ans += N-i
        print(ans)
        return
    L = [0]*P
    L[0] = 1
    t = 0
    s = 1
    for i in range(N):
        t = (S[i]*s+t)%P
        L[t] += 1
        s = s*10%P
    ans = 0
    for l in L:
        ans += l*(l-1)//2
    print(ans)
    
if __name__ == '__main__':
    main()

Solution (Python):
def main():
    N, P = map( int ,input().split())
    S = [ int(s) for s in list(input())][::-1]
    if P == 2 or P == 5:
        ans = 0
        for i in range(N):
            if S[i]%P == 0:
                ans += N-i
        print(ans)
        return
    L = [0]*P
    L[0] = 1
    t = 0
    s = 1
    for i in range(N):
        t = (S[i]*s+t)%P
        L[t] += 1
        s = s*10%P
    ans = 0
    for l in L:
        ans += l*(l-1)//2
    print(ans)
    
if __name__ == '__main__':
    main()

Solution (Python):
def main():
    N, P = map( int ,input().split())
    S = [ int(s) for s in list(input())][::-1]
    if P == 2 or P == 5:
        ans = 0
        for i in range(N):
            if S[i]%P == 0:
                ans += N-i
        print(ans)
        return
    L = [0]*P
    L[0] = 1
    t = 0
    s = 1
    for i in range(N):
        t = (S[i]*s+t)%P
        L[t] += 1
        s *= 10
        s %= P
    ans = 0
    for l in L:
        ans += l*(l-1)//2
    print(ans)
    
if __name__ == '__main__':
    main()

Solution (Python):
def main():
    N, P = map( int ,input().split())
    S = [ int(s) for s in list(input())][::-1]
    if P == 2 or P == 5:
        ans = 0
        for i in range(N):
            if S[i]%P == 0:
                ans += N-i
        print(ans)
        return
    L = [0]*P
    L[0] = 1
    t = 0
    for i in range(N):
        t = (S[i]*pow(10,i,P)+t)%P
        L[t] += 1
    ans = 0
    for l in L:
        ans += l*(l-1)//2
    print(ans)
    
if __name__ == '__main__':
    main()

Solution (Python):
import sys
import math
import copy
import queue
def LI(): return [int(x) for x in input().split()]
n,p = LI()
s = input()
cnt = 0
if p == 2 or p == 5:
    for i in range(n-1,-1,-1):
       if int(s[i]) % p == 0:
           cnt += (i+1)
else:
    num = 0
    p10 = 1
    p_cnt = [1] + [0 for _ in range(p-1)]
    for i in range(n-1,-1,-1):
        num = (num + p10 * int(s[i])) % p
        p_cnt[num] += 1
        p10 = (p10 * 10) % p
    for i in range(p):
        cnt += p_cnt[i] * (p_cnt[i]-1) // 2
print (cnt)

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

d = [0]*(N+1)


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

    
    counter = [0]*P

    for j in range(N, -1, -1):
        ans += counter[d[j]]

        counter[d[j]] += 1

    print(ans)

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


def mod_pow(a, n, mod):
  res = 1
  while  n > 0:
    if n & 1:
      res = (res * a ) % mod
    a = a * a  % mod
    n = n >> 1
  return res

if P == 2 or P == 5:

  count = 0
  for n in range(N):
    if int(S[n]) % P==0:
      count += (n + 1)
  print(count)
else:    
  Pa = [0 for _ in range(P)]
  number = 0
  for i in range(N, 0, -1):
    number = (number + int(S[i-1])*mod_pow(10, N - i, P)) % P
    Pa[number] += 1
  count = 0
  if Pa[0] > 0:
    count += Pa[0]
  for p in range( P):
    pmod = Pa[p]
    if pmod > 0:
      count += (pmod * (pmod - 1))//2
  print(count)

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

s = input()

if 10 % p == 0:
    ans = sum(i + 1 for i, x in enumerate(s) if int(x) % p == 0)
    print(ans)
else:
    counter = [0] * p
    counter[0] = 1
    cur = 0
    p10 = 1
    ans = 0
    for x in s[::-1]:
        cur = (cur + int(x) * p10) % p
        ans += counter[cur]
        counter[cur] += 1
        p10 *= 10
        p10 %= p
    print(ans)

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

def main():
    N, P = map(int, input().split())
    S = list(map(int, list(input())))
    ans = 0
    if P == 2:
        for i in range(N-1,-1,-1):
            if S[i] % 2 == 0:
                ans += i + 1
        print(ans)
        exit()
    if P == 5:
        for i in range(N-1,-1,-1):
            if S[i] % 5 == 0:
                ans += i + 1
        print(ans)
        exit()
    
    ten = 1
    d = defaultdict(int)
    C = [0] * (N + 1)
    for i in range(N-1,-1,-1):
        tmp = (S[i] * ten) % P
        idx = N - 1 - i
        C[idx + 1] = (C[idx] + tmp) % P
        ten *= 10
        ten %= P

    for c in C:
        d[c] += 1

    for i, j in d.items():
        ans += j * (j - 1) // 2

    print(ans)    


if __name__ == "__main__":
    main()

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:
    mp = [0]*P
    mp[0] = 1
    cur = 0
    p10 = 1
    for c in S[::-1]:
        cur = (cur + int(c)*p10) % P
        res += mp[cur]
        mp[cur] += 1
        p10 *= 10
        p10 %= P

print(res)

Solution (Python):
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))



from bisect import bisect_left

N,P = LI()
S = list(map(int,list(str(input()))))

ans = 0
if P == 2:
    for i in range(N):
        if S[i]%2 == 0:
            ans += i+1
elif P == 5:
    for i in range(N):
        if S[i]%5 == 0:
            ans += i+1
else:
    M = [0]*(N+1)
    now = 0
    for i in range(N):
        now += pow(10,i,P)*S[N-1-i]
        now %= P
        M[N-1-i] = now
    d = defaultdict(list)
    for i in range(N+1):
        d[M[i]].append(i)
    for i in range(N):
        p = bisect_left(d[M[i+1]],i+1)
        ans += p

print(ans)

Solution (Python):
import sys
from collections import deque


def input():
    return sys.stdin.readline()[:-1]


def solve():
    N, P = map(int, input().split())
    S = input()
    if (10 % P == 0):
        ans = 0
        for i in range(N):
            if int(S[N - i - 1]) % P == 0:
                ans += N - i
        return ans
    ten = 1
    cur = 0
    val = [0] * P
    val[cur] += 1
    for i in range(N):
        cur = (cur + int(S[N - i - 1]) * ten) % P
        ten *= 10
        ten %= P  
        val[cur] += 1
    ans = 0
    for p in range(P):
        ans += val[p] * (val[p] - 1) // 2
    return ans


if __name__ == "__main__":
    print(solve())

Solution (Python):
import sys
from collections import deque

def input():
    return sys.stdin.readline()[:-1]

def solve():
    N, P = map(int, input().split())
    S = input()
    if 10%P == 0:
        ans = 0
        for i in range(N):
            if int(S[N-i-1]) % P == 0:
                ans += N - i
        
        return ans
    
    ten = 1
    cur = 0
    val = [0] * P
    val[cur] += 1
    for i in range(N):
        cur = (cur + int(S[N-i-1])*ten) % P
        ten *= 10
        ten %= P
        val[cur] += 1
    ans = 0
    for p in range(P):
        ans += val[p] * (val[p] - 1) // 2
    
    return ans

if __name__ == "__main__":
    print(solve())

Solution (Python):
import sys
from collections import deque


def input():
    return sys.stdin.readline()[:-1]


def solve():
    N, P = map(int, input().split())
    S = input()
    if (10 % P == 0):
        ans = 0
        for i in range(N):
            if int(S[N - i - 1]) % P == 0:
                ans += N - i
        return ans
    ten = 1
    cur = 0
    val = [0] * P
    val[cur] += 1
    for i in range(N):
        cur = (cur + int(S[N - i - 1]) * ten) % P
        ten *= 10
        ten %= P
        val[cur] += 1
    ans = 0
    for p in range(P):
        ans += val[p] * (val[p] - 1) // 2
    return ans


if __name__ == "__main__":
    print(solve())

Solution (Python):
n,p=map(int,input().split())
if p==2 or p==5:
  print(sum(i+1 for i,x in enumerate(input()) if int(x)%p==0))
  exit()
t=1
y=0
c=[0]*p
for x in map(int,input()[::-1]):
  y+=t*x
  y%=p
  c[y]+=1
  t*=10
  t%=p
print(sum(i*(i-1)//2 for i in c)+c[0])

Solution (Python):
p = int(input().split()[1])
s = input()
if 10 % p == 0:
  r = sum(i for i, x in enumerate(s, 1) if int(x) % p == 0)
else:
  d = [1] + [0] * (p - 1)
  t, y = 0, 1
  for x in reversed(s):
    t = (t + int(x) * y) % p
    d[t] += 1
    y = y * 10 % p;
  r = sum(i * (i - 1) for i in d) // 2
print(r)

Solution (Python):
p = int(input().split()[1])
s = input()
if 10 % p == 0:
  r = sum(i for i, x in enumerate(s, 1) if int(x) % p == 0)
else:
  d = [1] + [0] * (p - 1)
  t, y = 0, 1
  for x in reversed(s):
    t = (t + int(x) * y) % p
    d[t] += 1
    y = y * 10 % p;
  r = sum(i * i - i for i in d) // 2
print(r)

Solution (Python):
p = int(input().split()[1])
s = input()
if 10 % p == 0:
  r = sum(i for i, x in enumerate(s, 1) if int(x) % p == 0)
else:
  d = [1] + [0] * (p - 1)
  t, y = 0, 1
  for x in reversed(s):
    t = (t + int(x) * y) % p
    d[t] += 1
    y = y * 10 % p;
  r = sum(i * (i - 1) for i in d) // 2
print(r)

Solution (Python):
p = int(input().split()[1])
s = input()
if 10 % p == 0:
  r = sum(i for i, x in enumerate(s, 1) if int(x) % p == 0)
else:
  d = [1] + [0] * (p - 1)
  t, y = 0, 1
  for x in reversed(s):
    t = (t + int(x) * y) % p
    d[t] += 1
    y = y * 10 % p;
  r = sum(i * (i - 1) // 2 for i in d)
print(r)

Solution (Python):
p = int(input().split()[1])
a = list(map(int, input()))
if 10 % p == 0:
  r = sum(i for i, x in enumerate(a, 1) if x % p == 0)
else:
  d = [1] + [0] * (p - 1)
  s, y = 0, 1
  for x in reversed(a):
    s = (s + x * y) % p
    d[s] += 1
    y = y * 10 % p;
  r = sum(i * (i - 1) // 2 for i in d)
print(r)

Solution (Python):
p = int(input().split()[1])
a = list(map(int, input()))
if 10 % p == 0:
  r = sum(i for i, x in enumerate(a, 1) if x % p == 0)
else:
  d = [1] + [0] * (p - 1)
  t, y = 0, 1
  for i, x in enumerate(reversed(a), 1):
    t = (t + x * y) % p
    d[t] += 1
    y = y * 10 % p;
  r = sum(i * (i - 1) // 2 for i in d)
print(r)

Solution (Python):
N,P=map(int,input().split(' '))
S =list(map(int,list(input()[::-1])))
ans = 0
cnt = [0]*P
cnt[0]=1
tmp = 0
for n,i in enumerate(S):
    d=i*pow(10,n,P)
    tmp =(tmp+d)%P
    cnt[tmp] += 1
if P in [2,5]:
    if P==2:
        check=[0,2,4,6,8]
    else:
        check=[0,5]
    for n,i in enumerate(S):
        if i in check:
            ans += N-n
else:
    for i in cnt:
        ans += i*(i-1)//2
print(ans)

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

def largeSol():
    T = [0] * (N + 1)
    for i, s in enumerate(map(int, S[:: -1])):
        T[i + 1] = (s * pow(10, i, P) + T[i]) % P

    ans = 0
    cnt = Counter(T[1:])
    for p in range(P):
        x = cnt[p]
        ans += x * (x - 1) // 2
    ans += cnt[0]
    return ans

def smallSol():
    dp = [0] * P
    ans = 0
    for s in map(int, S):
        newDp = [0] * P
        newDp[s % P] += 1
        for p in range(P):
            newDp[(p * 10 + s) % P] += dp[p]
        dp = newDp
        ans += dp[0]
    return ans

print(smallSol() if N * P <= 10**7 else largeSol())

Solution (Python):
p = int(input().split()[1])
s = input()
if 10 % p:
  s = reversed(s)
a = enumerate(map(int, s), 1)
if 10 % p == 0:
  r = sum(i for i, x in a if x % p == 0)
else:
  d = [1] + [0] * (p - 1)
  t, y = 0, 1
  for i, x in a:
    t = (t + x * y) % p
    d[t] += 1
    y = y * 10 % p;
  r = sum(i * (i - 1) // 2 for i in d)
print(r)

Solution (Python):
p = int(input().split()[1])
a = list(map(int, input()))
if 10 % p == 0:
  r = sum(i for i, x in enumerate(a, 1) if x % p == 0)
else:
  d = [1] + [0] * (p - 1)
  t, y = 0, 1
  for i, x in enumerate(reversed(a), 1):
    t = (t + x * y) % p
    d[t] += 1
    y = y * 10 % p;
  r = sum(i * (i - 1) // 2 for i in d)
print(r)

Solution (Python):
p = int(input().split()[1])
s = input()
if 10 % p:
  s = reversed(s)
a = enumerate(map(int, s), 1)
if 10 % p == 0:
  r = sum(i for i, x in a if x % p == 0)
else:
  d = [1] + [0] * (p - 1)
  t, y = 0, 1
  for i, x in a:
    t = (t + x * y) % p
    d[t] += 1
    y = y * 10 % p;
  r = sum(i * (i - 1) // 2 for i in d)
print(r)

Solution (Python):
p = int(input().split()[1])
a = list(map(int, input()))
if 10 % p == 0:
  r = sum(i for i, x in enumerate(a, 1) if x % p == 0)
else:
  d = [1] + [0] * (p - 1)
  t, y = 0, 1
  for i, x in enumerate(reversed(a), 1):
    t = (t + x * y) % p
    d[t] += 1
    y = y * 10 % p;
  r = sum(i * (i - 1) // 2 for i in d)
print(r)

Solution (Python):
I = lambda s:map(int, s)

p = int(input().split()[1])
s = input()
if 10 % p == 0:
  r = sum(i for i, x in enumerate(I(s), 1) if x % p == 0)
else:
  d = {0 : 1}
  t, y = 0, 1
  for i, x in enumerate(I(reversed(s)), 1):
    t = (t + x * y) % p
    d[t] = d.get(t, 0) + 1
    y = y * 10 % p;
  r = sum(i * (i - 1) // 2 for i in d.values())
print(r)

Solution (Python):
I = lambda s:map(int, s)

p = int(input().split()[1])
s = input()
if 10 % p == 0:
  r = sum(i for i, x in enumerate(I(s), 1) if x % p == 0)
else:
  d = [1] + [0] * (p - 1)
  t, y = 0, 1
  for i, x in enumerate(I(reversed(s)), 1):
    t = (t + x * y) % p
    d[t] += 1
    y = y * 10 % p;
  r = sum(i * (i - 1) // 2 for i in d)
print(r)

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

I = lambda s:map(int, s)

p = int(input().split()[1])
s = input()
if 10 % p == 0:
  r = sum(i for i, x in enumerate(I(s), 1) if x % p == 0)
else:
  a = accumulate(x * pow(10, i, p) for i, x in enumerate(I(reversed(s)), 1))
  c = Counter(x % p for x in a) 
  c[0] += 1
  r = sum(i * (i - 1) // 2 for i in c.values())
print(r)

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

p = int(input().split()[1])
a = list(map(int, input()))
if 10 % p == 0:
  r = sum(i for i, x in enumerate(a, 1) if x % p == 0)
else:
  a = accumulate(x * pow(10, i, p) for i, x in enumerate(reversed(a), 1))
  c = Counter(x % p for x in a) 
  c[0] += 1
  r = sum(i * (i - 1) // 2 for i in c.values())
print(r)

Solution (Python):
n,p = map(int,input().split())
s = list(map(int,(list(input()))))
def keychange(dic,x):
    newdic = {}
    for k in dic:
        b = (k*10 + x) % p
        newdic[b] = dic[k]
    return newdic
count = 0
if p == 2:
    for i in range(n):
        if s[i] % 2 == 0:
            count += i+1
    print(count)
    exit()
if p == 5:
    for i in range(n):
        if s[i] % 5 == 0:
            count += i+1
    print(count)
    exit()
inv_t = [0]+[1]
for i in range(2,p):
  inv_t += [inv_t[p % i] * (p - int(p / i)) % p]
dic = {}
memory = [1,0]
for i in range(n):
    x = s[i] % p
    memory[0] = 10*memory[0] % p
    memory[1] = (10*memory[1] + x) % p
    xinv = inv_t[memory[0]]*(x-memory[1]+p) % p
    if xinv in dic:
        dic[xinv] += 1
    else:
        dic[xinv] = 1
    zeroinv = (p-memory[1])*inv_t[memory[0]] % p
    if zeroinv in dic:
        count += dic[zeroinv]
print(count)

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




























remain = [0] * P
remain[0] += 1
d = 1
left = 0
for i in range(n):
    
    left = (left + int(S[n - i - 1]) * d) % P
    remain[left] += 1
    d = d * 10 % P

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








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

    

if P == 5:
    ans = 0
    for i in range(n):
      if int(S[i]) % 5 == 0:
          ans += i + 1
    print(ans)
if P != 2 and P != 5:
    print(ans)

Solution (Python):
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=998244353
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n,p=LI()
  s=S()

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

  _s=list(s)
  _s.reverse()

  a=[]
  i=1
  for x in _s:
    b=(i*int(x))%p
    a.append(b)
    i*=10
    i%=p

  b=[0]*p
  b[a[0]%p]=1
  for i in range(n-1):
    a[i+1]+=a[i]
    a[i+1]%=p
    b[a[i+1]]+=1

  for i,x in enumerate(b):
    if i==0:
      ans+=x
    if x>1:
      ans+=x*(x-1)//2

  return ans


print(main())

Solution (Python):
import sys
import itertools
import collections

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    N, P = [int(x) for x in input().split()]
    S = input().strip()

    if P == 2 or P == 5:
        ans = 0
        for i, s in enumerate(S[::-1]):
            if int(s) % P == 0:
                ans += N - i
        print(ans)
        return

    M = [0] * N
    for i, s in enumerate(S[::-1]):
        M[i] = (int(s) * pow(10, i, P)) % P

    MA = []
    MA.append(M[0])
    c = collections.Counter()
    ans = 0
    c[0] += 1
    ans += c[MA[0]]
    c[M[0]] += 1
    for i in range(1, N):
        MA.append((MA[i - 1] + M[i]) % P)
        ans += c[MA[i]]
        c[MA[i]] += 1

    print(ans)


if __name__ == '__main__':
    main()