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 numpy as np

def a():
  n, p = list(map(int, input().split()))
  num = [int(s) for s in input()]
  
  if(p==2 or p==5):
    count=0
    for i in range(1,n+1):
      if(num[-i]%p == 0):
        count += n-i+1
    print(count)
    return
  
  counts = np.zeros(p)
  tmp = 0
  tens = 1
  for i in range(1,n+1):
    tmp = (tens*num[-i] + tmp) % p
    counts[tmp] += 1
    tens = (tens*10)%p
  ret = int(counts[0] + sum(counts*(counts-1)//2))
  print(ret)
  return
a()

Solution (Python):
N, P = input().split()
p_len = len(P)
N = int(N)
P = int(P)

S = input()


cnt = 0
if P in [2,5]:
    for i in range(N):
        cnt += i+1 if int(S[i]) % P == 0 else 0
else:
    table = [0] * P 
    Ui = 0
    ten = 1
    
    S = S[::-1]
    table[0] = 1 
    
    for i in range(N):
        Ui = (Ui + int(S[i]) * ten) % P 
        
        cnt += table[Ui] 
        
        table[Ui] += 1 
        ten = (ten * 10) % P 
print(cnt)

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

if P == 2 or P == 5:
    print(sum(i for i, s in enumerate(S, 1) if s % P == 0))
    quit()

C = [0] * P
tens = 1
cur = 0
for s in reversed(S):
    cur = (cur + s * tens) % P
    C[cur] += 1
    tens = (tens * 10) % P

print(C[0] + sum(c * (c - 1) // 2 for c in C))

Solution (Python):
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

n,p = mi()
s = input()
srev = s[::-1]

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

acum = []
from collections import defaultdict
d = defaultdict(lambda :0)
d = [0] * p
num = 0
tenpow = 1
for i in range(0,n):
    a = int(srev[i])
    a = num + a *tenpow 
    tenpow = tenpow * 10 % p
    modd = a % p
    num = modd
    d[modd] += 1
    acum.append((modd,d[modd]))
ans = d[0]
for i in range(n):
    ans += d[acum[i][0]] - acum[i][1]
print(ans)

Solution (Python):
import sys
def main():
    input = sys.stdin.readline
    N,P = map(int, input().split())
    S = input().rstrip()
    D = list(map(int, S))
    
    ans = 0
    if P == 2:
        for i, d in enumerate(D):
            if d&1 == 0: ans += i + 1
        return ans

    if P == 5:
        for i, d in enumerate(D):
            if d == 0 or d == 5: ans += i + 1
        return ans

    A = [0] * P
    num = Mint(0, P)
    for i in range(N):
        num += Mint(D[-1-i], P) * pow(10, i, P)
        A[num.value] += 1
    for a in A:
        ans += a * (a-1) // 2
    ans += A[0]
    return ans

class Mint:
    def __init__(self, value=0, mod=10**9+7):
        self.value = ((value % mod) + mod) % mod
        self.mod = mod

    @staticmethod
    def get_value(x): return x.value if isinstance(x, Mint) else x

    def inverse(self):
        a, b = self.value, self.mod
        u, v = 1, 0
        while b:
            t = a // b
            b, a = a - t * b, b
            v, u = u - t * v, v
        return (u + self.mod) % self.mod

    def __repr__(self): return str(self.value)
    def __eq__(self, other): return self.value == other.value
    def __neg__(self): return Mint(-self.value, self.mod)
    def __hash__(self): return hash(self.value)
    def __bool__(self): return self.value != 0

    def __iadd__(self, other):
        self.value = (self.value + Mint.get_value(other)) % self.mod
        return self
    def __add__(self, other):
        new_obj = Mint(self.value, self.mod)
        new_obj += other
        return new_obj
    __radd__ = __add__

    def __isub__(self, other):
        self.value = (self.value - Mint.get_value(other) + self.mod) % self.mod
        return self
    def __sub__(self, other):
        new_obj = Mint(self.value, self.mod)
        new_obj -= other
        return new_obj
    def __rsub__(self, other):
        new_obj = Mint(Mint.get_value(other), self.mod)
        new_obj -= self
        return new_obj

    def __imul__(self, other):
        self.value = self.value * Mint.get_value(other) % self.mod
        return self
    def __mul__(self, other):
        new_obj = Mint(self.value, self.mod)
        new_obj *= other
        return new_obj
    __rmul__ = __mul__

    def __ifloordiv__(self, other):
        other = other if isinstance(other, Mint) else Mint(other, self.mod)
        self *= other.inverse
        return self
    def __floordiv__(self, other):
        new_obj = Mint(self.value, self.mod)
        new_obj //= other
        return new_obj
    def __rfloordiv__(self, other):
        new_obj = Mint(Mint.get_value(other), self.mod)
        new_obj //= self
        return new_obj

if __name__ == '__main__':
    ans = main()
    print(ans)

Solution (Python):

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


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

else:
    cnt = [0]*P 
    num = 0
    tenPow = 1
    for i in reversed(range(N)):
        num = (num + int(S[i])*tenPow)%P
        tenPow = tenPow*10%P
        cnt[num] += 1

    ans += cnt[0]
    for c in cnt:
        ans += c*(c-1)//2 


print(ans)

Solution (Python):
from collections import defaultdict
N,P = map(int, input().split())
S = list(input()[::-1])
ans = 0
if P == 2:
    for i,s in enumerate(S):    
        if int(s) in [2,4,6,8,0]:
            ans += N - i
elif P == 5:
    for i,s in enumerate(S):    
        if int(s) in [0,5]:
            ans += N - i
else:
    d = defaultdict(int)
    cnt = 0
    d[0] = 1
    for i,s in enumerate(S):
        cnt = (cnt + pow(10,i,P)*int(s))%P
        d[cnt] += 1
    for k in d.keys():
        if d[k] > 1:
            ans += d[k]*(d[k]-1)//2 
print(ans)

Solution (Python):
def main():
	N, P = map(int, input().split())
	S = [int(c) for c in input()]

	if 10 % P == 0:
		ans = 0
		for i in range(N):
			if S[i] % P == 0:
				ans += (i + 1)

		print(ans)
		return


	M = [0] * (N + 1) 

	t = 1
	for i in range(N - 1, -1, -1):
		M[i] = (M[i + 1] + t % P * S[i]) % P
		t = (t * 10) % P

	C = [0] * 10000

	for v in M:
		C[v] += 1

	ans = 0
	for v in C:
		if v > 0:
			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()))) 

def solve():
    if p in [2,5]: 
        ret = 0
        for i in range(n): 
            lsd = s[n-1-i] 
            if lsd % p == 0: ret += n - i 
        return ret

    ten = 1 
    cnt = [0]*p 
    r = 0 
    cnt[r] += 1 
    for i in range(n): 
        msd = s[n-1-i] 
        r = (msd * ten + r) % p 
        ten = ten * 10 % p 
        cnt[r] += 1 

    ret = 0
    for r in range(p): 
        ret += cnt[r] * (cnt[r] - 1) // 2 
    return ret

print(solve())

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

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

    l = [0]*p
    l[0] += 1
    s1 = s[::-1]
    ten = 1
    mod = 0
    for i in range(n):
        mod += int(s1[i])*ten%p
        mod %= p
        ten = ten*10%p
        l[mod] += 1
    ans = 0

    for i in l:
        ans += (i-1)*i//2
    print(ans)
if __name__ == "__main__":
    main()

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

def solve():
    if p in [2,5]:
        ret = 0
        for i in range(n):
            if int(s[n-1-i]) % p == 0: ret += n-i
        return ret
    val = [0]*p
    ten = 1
    cur = 0
    val[cur] += 1
    for i in range(n):
        cur = (cur + int(s[n-1-i]) * ten) % p
        ten = ten * 10 % p
        val[cur] += 1
    ret = 0
    for i in range(p):
        ret += val[i] * (val[i] - 1) // 2
    return ret

print(solve())

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

def solve():
    if p in [2,5]:
        ret = 0
        for i in range(n):
            d = ord(s[n-1-i])-ord('0')
            if d % p == 0: ret += n-i
        return ret
    val = [0]*p
    ten = 1
    cur = 0
    val[cur] += 1
    for i in range(n):
        d = ord(s[n-1-i])-ord('0')
        cur = (cur + d * ten) % p
        ten = ten * 10 % p
        val[cur] += 1
    ret = 0
    for i in range(p): ret += val[i] * (val[i]-1)//2
    return ret

print(solve())

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

a = [0] * (N + 1)

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

    ans = 0
    from collections import Counter
    C=Counter(a)
    for v,i in C.items():
        ans += (i * (i - 1) // 2)
elif 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

print(ans)

Solution (Python):
def main():

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

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

    ans = 0
    count = [0] * P
    count[0] = 1
    for i in range(N):
        ans += count[sum_rem[i]]
        count[sum_rem[i]] += 1
    print(ans)


if __name__ == '__main__':
    main()

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

if P in (2,5):
    ans = 0
    for i,c in enumerate(S):
        c = int(c)
        if c%P==0:
            ans += (i+1)
    print(ans)
else:
    ans = 0
    a = [0]
    j = 1
    for c in S[::-1]:
        c = int(c)
        a.append((a[-1] + j*c) % P)
        j *= 10
        j %= P
    from collections import Counter
    ctr = Counter(a)
    for k,v in ctr.items():
        ans += v*(v-1)//2
    print(ans)

Solution (Python):
from collections import defaultdict

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

if p in (2, 5):
    if p == 2:
        ok_list = [i for i in range(10)][::2]
    else:
        ok_list = [0, 5]
    ans = 0
    for i in range(n):
        if int(s[i]) in ok_list:
            ans += i+1
    print(ans)
else:
    dd = defaultdict(int)
    dd[0] = 1
    prev = 0

    for i in range(n-1, -1, -1):
        d = int(s[i]) * pow(10, n-i, p)
        prev = (prev + d) % p
        dd[prev] += 1

    print(sum(v*(v-1)//2 for v in dd.values()))

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

Solution (Python):
from collections import Counter
def mpow(a,b,mod):
  ret=1
  while b>0:
    if b&1:
      ret=(ret*a)%mod
    a=(a*a)%mod
    b>>=1
  return ret
n,p=map(int,input().split())
s=[int(i) for i in input()]
if p==2 or p==5:
  ans=0
  for i in range(n):
    if s[i]%p==0:
      ans+=i+1
  print(ans)
else:
  ans=0
  d=Counter()
  d[0]+=1
  num=0
  for i in range(n-1,-1,-1):
    num=(num+s[i]*mpow(10,n-1-i,p))%p
    ans+=d[num]
    d[num]+=1
  print(ans)

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


def solve1(s, p):
    v = 0
    pow10 = 1
    ans = 0
    cnt = [0] * p
    cnt[0] = 1

    for i in range(n - 1, -1, -1):
        v = (pow10 * int(s[i]) + v) % p
        pow10 = (pow10 * 10) % p
        ans += cnt[v]
        cnt[v] += 1
    return ans


def solve25(s, p):
    cnt = 0
    ans = 0
    for i in range(len(s) - 1, -1, -1):
        if int(s[i]) % p == 0:
            cnt += 1
        ans += cnt
    return ans



if p in (2,5):
    print(solve25(s, p))
else:
    print(solve1(s, p))

Solution (Python):
from collections import defaultdict

def main():
    n, p = [int(e) for e in input().split()]
    s = input()

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

            cnt += cum

    else:
        D = {n: 0}
        exp = 1
        for i in range(n - 1, -1, -1):
            D[i] = (D[i + 1] + (int(s[i]) * exp % p)) % p
            exp *= 10
            exp %= p

        Di = defaultdict(int)
        Di[0] = 1
        for i in range(n - 1, -1, -1):
            Di[D[i]] += 1
            cnt += Di[D[i]] - 1

    print(cnt)

if __name__ == "__main__":
    main()

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def main():
	N, P = MAP()
	S = list(map(int, list(input())))

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

		for i, s in enumerate(S):
			if int(s)%P == 0:
				ans += i+1
		print(ans)

	else:
		tmp = 0

		mod_cnt = [0]*P

		z = 1
		for i, n in enumerate(S[::-1]):
			tmp += n*z
			z = z * 10 % P
			mod_cnt[int(tmp)%P] += 1
		ans = 0
		for v in mod_cnt:
			ans += v*(v-1)//2
		print(ans+mod_cnt[0])


if __name__ == '__main__':
	main()

Solution (Python):
n,p = map(int,input().split())
s = input()
num = 0
s1 = [0]*(n+1)
ans = 0
if p == 2 or p == 5:
	for i in range(len(s)):
		if int(s[i])%p == 0:
			ans += i+1	
	print(ans)
	exit()
ans = 0
arr = [0]*p
s = s[::-1]
z = 1
for i in range(n):
	s1[i+1] = s1[i] + int(s[i])*z
	z = z * 10 %p
	s1[i+1] %=p
	arr[s1[i]] += 1
arr[s1[n]]+=1

for i in range(p):
	ans += arr[i] * (arr[i] - 1) // 2
print(ans)

Solution (Python):
def main():
	n,p = map(int,input().split())
	s = input()
	num = 0
	s1 = [0]*(n+1)
	ans = 0
	if p == 2 or p == 5:
		for i in range(len(s)):
			if int(s[i])%p == 0:
				ans += i+1	
		print(ans)
		exit()
	ans = 0
	arr = [0]*p
	s = s[::-1]
	z = 1
	for i in range(n):
		s1[i+1] = s1[i] + int(s[i])*z
		z = z * 10 %p
		s1[i+1] %=p
		arr[s1[i]] += 1
	arr[s1[n]]+=1
	
	for i in range(p):
		ans += arr[i] * (arr[i] - 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().strip())][::-1]
	num = 0
	ans = 0
	if P == 2 or P == 5:
		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
	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().strip())][::-1]
	num = 0
	ans = 0
	if P == 2 or P == 5:
		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
	for l in L:
		ans += l * (l - 1) // 2
	print(ans)

if __name__ == '__main__':
	main()

Solution (Python):
from collections import Counter

N, P = map(int, input().split())
S = [int(s) for s in input()]
S.reverse()

ans = 0

if P != 2 and P != 5:
    prime10 = [1] * N
    for n in range(1, N):
        prime10[n] = (prime10[n-1] * 10) % P
    S = [(s * prime10[n]) % P for n, s in enumerate(S)]
    for n in range(1, N):
        S[n] = (S[n-1] + S[n]) % P

    S = Counter(S)
    for p in range(P):
        if p == 0:
            ans += S[p]
        ans += (S[p] * (S[p]-1)) // 2

else:
    for n in range(N):
        if S[n] % P == 0:
            ans += N - n

print(ans)

Solution (Python):
def main():
    N, P = map(int, input().split())
    S = input()
    if P == 2 or P == 5:
        r = 0
        for i, v in enumerate(S):
            if int(v) % P == 0:
                r += i + 1
        return r
    l = [0] * P
    l[0] = 1
    p = 0
    r = 0
    for i, v in enumerate(reversed(S)):
        p = (p + int(v) * pow(10, i, P)) % P
        r += l[p]
        l[p] += 1
    return r
print(main())

Solution (Python):
import sys
from itertools import combinations, permutations, product, combinations_with_replacement, accumulate
from heapq import heapify, heappop, heappush, heappushpop
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from math import sqrt, log, floor, ceil, factorial, cos, sin, pi
from fractions import gcd
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
INF = float('inf')
LINF = 2**63-1
NIL = -LINF
MOD = 10**9+7
MGN = 4
def II(): return int(input())
def IF(): return float(input())
def IS(): return input().replace('\n', '')
def ILCI(n: int): return [II() for _ in range(n)]
def ILCF(n: int): return [IF() for _ in range(n)]
def ILI(): return list(map(int, input().split()))
def ILLI(n: int): return [[int(j) for j in input().split()] for i in range(n)]
def ILF(): return list(map(float, input().split()))
def ILLF(n: int): return [[float(j) for j in input().split()] for i in range(n)]
def LTOS(lst: list, sep: str = ' '): return sep.join(map(str, lst))
def DEC(lst: list): return list(map(lambda x: x-1, lst))
def INC(lst: list): return list(map(lambda x: x+1, lst))


def stoli(s, sep = ''):
    """ 文字列と区切り文字(列)を受け取り、
    整数のリストにして返す """
    if sep == None or sep == '':
        return list(map(int, list(s)))

    ls = []
    for e in s.split(sep):
        if e is None or e == '':
            continue
        else:
            ls.append(e)

    return list(map(int, ls))


def seg_count_all(A: list) -> dict:
    """ 整数リスト A を受け取り、
    リスト中の任意の整数 A[i] で挟まれた区間の数を辞書として返す """
    assert A is not None, "S は None でない"
    N = len(A)
    cnt = {}  
    res = {}  
    for i in range(N):
        if A[i] in cnt:
            res[A[i]] += cnt[A[i]]  
            cnt[A[i]] += 1
        else:
            res[A[i]] = 0
            cnt[A[i]] = 1

    return res


def main():
    N, P = ILI()
    S = IS()

    d = stoli(S)
    
    
    d.reverse()

    if 10%P == 0:
        assert P == 2 or P == 5
        ans = 0
        for l in range(N):
            
            if d[l] % P == 0:
                ans += N-l  
        print(ans)
        return 0

    
    
    md = [0] * N
    ten = 1
    for i in range(N):
        md[i] = (d[i] * ten) % P
        ten *= 10
        ten %= P  
    
    
    sum = [0] * N
    sum[0] = md[0]
    for i in range(1,N):
        sum[i] = (sum[i-1] + md[i]) % P

    
    ans = 0    
    cnt = seg_count_all(sum)  
    for k in cnt:
        ans += cnt[k]
    ans += sum.count(0) 

    print(ans)
    return 0


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    N, P = map(int, input().split())
    S = input()
    if P == 2 or P == 5:
        r = 0
        for i, v in enumerate(S):
            if int(v) % P == 0:
                r += i + 1
        return r
    l = [0] * P
    l[0] = 1
    p = 0
    r = 0
    for i, v in enumerate(reversed(S)):
        p = (p + int(v) * pow(10, i, P)) % P
        r += l[p]
        l[p] += 1
    return r
print(main())

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

ans = 0
if P in [2, 5]:
    for i, c in enumerate(S):
        if int(c) % P == 0:
            ans += i + 1
else:
    ct = Counter()
    ct[0] = 1
    prevmod = 0
    mods = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
    for i in range(N-1, -1, -1):
        n = int(S[i])
        mod = (mods[n] + prevmod) % P
        ans += ct[mod]
        ct[mod] += 1
        prevmod = mod
        mods = [10 * a % P for a in mods]
print(ans)

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

cnt = 0
if 10 % p == 0:
    for i, c in enumerate(s):
        if int(c) % p == 0:
            cnt += n - i
else:
    accmod = [0] * p
    accmod[0] = 1
    num = 0
    for i in range(n):
        num = (num + s[i] * pow(10, i, p)) % p
        accmod[num] += 1
    for v in accmod:
        if v > 1:
            cnt += v * (v - 1) // 2
print(cnt)

Solution (Python):
n, p = map(int, input().split())
s = [int(x) for x in input()]

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

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


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

for i in range(n):
    s[i] *= po10[n-1-i]
    s[i] %= p

ss = [0]

for i in range(n):
    ss.append(ss[-1]+s[i])
    ss[-1] %= p


ss = sorted(ss)

ll = len(ss)

ans = 0
tmp = [0,0]
for i in range(ll):
    if ss[i] != tmp[0]:
        ans += (i-tmp[1])*(i-tmp[1]-1) //2
        tmp[0] = ss[i]
        tmp[1] = i

ans += (ll-tmp[1])*(ll-tmp[1]-1)//2

print(ans)

Solution (Python):
import collections
import math

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

n,p= map(int, input().split())
s=list(input())
mod=0
ans=[]
count=0

if p==2 or p==5:
    for i in range(n):
        if p==2 and s[n-1-i] in {'0', '2' ,'4','6' ,'8'}:
            count+=n-i
        elif p==5 and s[n-1-i] in {'0','5'}:
            count+=n-i
    print(count)
    exit()

s+='0'

for i in range(n+1):
    if s[n-i]!=0:
        mod+=(pow(10,i,p)*int(s[n-i]))%p
        mod%=p
    ans.append(mod)

ans = collections.Counter(ans)
ans=ans.most_common()
for i in range(len(ans)):
    if ans[i][1]>=2:
        count+=combinations_count(ans[i][1],2)

print(count)

Solution (Python):

import sys
from collections import defaultdict

def solve(N: int, P: int, S: str):
    if 10%P == 0:
        sum = 0
        for i in range(1,N+1):
            if int(S[-i]) % P == 0:
                sum += (N-i)+1
        print(sum)
        return
    else:
        current = 0
        C = 1
        counts = defaultdict(int)
        for i in range(1,N+1):
            if i == 1:
                current = int(S[-1])%P
            else:
                current = (int(S[-i])*C + current)%P
            counts[current]+=1
            C=C*10%P
        sum = 0
        for k in counts:
            c = counts[k]
            sum += int((c*(c-1)/2))
        sum += counts[0]
        print(sum)

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

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

n,p= map(int, input().split())
s=list(input())
mod=0
ans=[]
count=0

if p==2 or p==5:
    for i in range(n):
        if p==2 and s[n-1-i] in ('0', '2' ,'4','6' ,'8'):
            count+=n-i
        elif p==5 and s[n-1-i] in ('0','5') :
            count+=n-i
    print(count)
    exit()

s+='0'

for i in range(n+1):
    if s[n-i]!=0:
        mod+=(pow(10,i,p)*int(s[n-i]))%p
        mod%=p
    ans.append(mod)

ans = collections.Counter(ans)
ans=ans.most_common()
for i in range(len(ans)):
    if ans[i][1]>=2:
        count+=combinations_count(ans[i][1],2)

print(count)

Solution (Python):
from collections import Counter
n,p=map(int,input().split())
s=input()[::-1]
a=0
t=0
d=1
m=[0]*p
m=[0]
for i in range(n):
  x=int(s[i])*d%p
  m.append((m[-1]+x)%p)
  d=(d*10)%p
c=Counter(m)
for i,j in c.items():
  a+=j*(j-1)//2

if p==2 or p==5:
  a=0
  for i in range(n):
    x=int(s[i])
    if x%p==0:
      a+=n-i
  print(a)
else:
  print(a)

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


tot = 0

if P in [2,5]:
  for i in range(1,N+1):
    if int(S[-i]) % P == 0:
      tot += N-i+1
else:
  S_mod = [0] * P
  S_mod[0] = 1 
  mod = 0
  mod10 = 10 % P
  mod_power10 = 1
  for i in range(N-1, -1, -1):
    mod = (int(S[i]) % P * mod_power10 + mod % P) % P
    
    tot += S_mod[mod]
    S_mod[mod] += 1
    mod_power10 = (mod_power10 * mod10) % P
print(tot)

Solution (Python):
import collections
import math

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

n,p= map(int, input().split())
s=list(input())
mod=0
ans=[]
count=0

if p==2 or p==5:
    for i in range(n):
        if p==2 and (s[n-1-i]=='0' or s[n-1-i]=='2' or s[n-1-i]=='4' or s[n-1-i]=='6' or s[n-1-i]=='8'):
            count+=n-i
        elif p==5 and (s[n-1-i]=='0' or s[n-1-i]=='5'):
            count+=n-i
    print(count)
    exit()

s+='0'

for i in range(n+1):
    if s[n-i]!=0:
        mod+=(pow(10,i,p)*int(s[n-i]))%p
        mod%=p
    ans.append(mod)

ans = collections.Counter(ans)
ans=ans.most_common()
for i in range(len(ans)):
    if ans[i][1]>=2:
        count+=combinations_count(ans[i][1],2)

print(count)

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

def nC2(n):
    if n == 0:
        return 0
    return n*(n-1)//2

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

if p != 2 and p != 5:
    u = []
    r = int(s[n-1])%p
    for i in range(1,n):
        u.append(r)
        j = n-i-1
        r = (r + int(s[j])*p_joyo[i])%p
    u.append(r)
    onaji = {}
    for i in u:
        if not i in onaji:
            onaji[i] = 1
        else:
            onaji[i] += 1
    ans = 0
    for key, r in onaji.items():
        ans += nC2(r)
        if key == 0:
            ans += r
    print(ans)

elif p == 2:
    ans = 0
    for i in range(n):
        if int(s[i]) in [0,2,4,6,8]:
            ans += i+1
    print(ans)

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

Solution (Python):
N,P=map(int,input().split())
S=[int(i) for i 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)
else:   
    X=[0 for i in range(N+1)]
    tmp=1
    for i in range(N):
        X[i+1]=X[i]+tmp*S[i]
        X[i+1]%=P
        tmp=tmp*10
        tmp%=P
    
    D=dict()
    for i in range(N+1):
        if X[i] in D:
            D[X[i]]+=1
        else:
            D[X[i]]=1
    ans=0
    for k in D:
        ans+=(D[k]*(D[k]-1))//2
    
    print(ans)

Solution (Python):
import sys
from itertools import combinations, permutations, product, combinations_with_replacement, accumulate
from heapq import heapify, heappop, heappush, heappushpop
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from math import sqrt, log, floor, ceil, factorial, cos, sin, pi
from fractions import gcd
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
INF = float('inf')
LINF = 2**63-1
NIL = -LINF
MOD = 10**9+7
MGN = 4
def II(): return int(input())
def IF(): return float(input())
def IS(): return input().replace('\n', '')
def ILCI(n: int): return [II() for _ in range(n)]
def ILCF(n: int): return [IF() for _ in range(n)]
def ILI(): return list(map(int, input().split()))
def ILLI(n: int): return [[int(j) for j in input().split()] for i in range(n)]
def ILF(): return list(map(float, input().split()))
def ILLF(n: int): return [[float(j) for j in input().split()] for i in range(n)]
def LTOS(lst: list, sep: str = ' '): return sep.join(map(str, lst))
def DEC(lst: list): return list(map(lambda x: x-1, lst))
def INC(lst: list): return list(map(lambda x: x+1, lst))


def stoli(s, sep = ''):
    """ 文字列と区切り文字(列)を受け取り、
    整数のリストにして返す """
    if sep == None or sep == '':
        return list(map(int, list(s)))

    ls = []
    for e in s.split(sep):
        if e == None or e == '':
            continue
        else:
            ls.append(e)

    return list(map(int, ls))


def main():
    N, P = ILI()
    S = IS()

    d = stoli(S)
    
    d.reverse()

    if 10%P == 0:
        ans = 0
        for l in range(N):
            if d[l] % P == 0:
                ans += N-l
        print(ans)
        return 0

    md = [0] * N
    ten = 1
    for i in range(N):
        md[i] = (d[i] * ten) % P
        ten *= 10
        ten %= P
    
    sum = [0] * N
    sum[0] = md[0]
    for i in range(1,N):
        sum[i] = (sum[i-1] + md[i]) % P

    ans = 0
    cnt = [0] * P
    for i in range(N):
        ans += cnt[sum[i]]
        cnt[sum[i]] += 1
    ans += cnt[0]

    print(ans)
    return 0


if __name__ == '__main__':
    main()

Solution (Python):


iim = lambda: map(int, input().rstrip().split())

def resolve():
    N, P = iim()
    S = list(map(int, input().rstrip()))

    if P == 2 or P == 5:
        cnt = 0
        for i, si in enumerate(S):
            if si % P == 0:
                cnt += i + 1
        print(cnt)
        return

    T = [0] * P
    T[0] = 1

    ss, p10 = 0, 1
    for s1 in S[::-1]:
        ss += p10 * s1
        ss %= P
        T[ss] += 1
        p10 = 10 * p10 % P

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

if __name__ == "__main__":
    resolve()

Solution (Python):
def main():
    from collections import Counter
    N, P = (int(i) for i in input().split())
    S = [int(s) for s in input()]

    ans = 0
    if P == 5 or P == 2:
        for i, s in enumerate(S, start=1):
            
            if s % P == 0:
                ans += i
    else:
        acc = [0]*(N+1)
        d = 1
        for i, s in enumerate(S[::-1], start=1):
            
            acc[i] = (s * d + acc[i-1]) % P
            d *= 10
            d %= P
        c = Counter(acc)
        
        ans = sum(v*(v-1)//2 for v in c.values())
    print(ans)


if __name__ == '__main__':
    main()