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,os
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    XLMIIS = lambda x: [LMIIS() for _ in range(x)]
    YN = lambda c : print('Yes') if c else print('No')
    MOD = 10**9+7

    N,P = LMIIS()
    S = input()[::-1]
    R = [0]*P
    R[0] = 1
    b = 1
    r = 0


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

    for c in S:
        r += b * int(c)
        r %= P
        R[r] += 1
        b *= 10
        b %= P
    ans = 0

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

if __name__ == '__main__':
    main()

Solution (Python):
n,k=map(int,input().split())
s=map(int,list(input()))
ans=0
if k==2 or k==5:
    for i,p in enumerate(s):
        if p%k==0:
            ans+=i+1
else:
    inv10=pow(10,k-2,k)
    inv=10
    total=0
    S=[0]*k
    S[0]=1
    for i,p in enumerate(s):
        inv*=inv10
        inv%=k
        total+=p*inv
        total%=k
        ans+=S[total]
        S[total]+=1
print(ans)

Solution (Python):

N, P = map(int, input().split())
S = input()
ans = 0
if P == 2:
    for i in range(N):
        if int(S[i]) % 2 == 0:
            ans += i+1
elif P == 5:
    for i in range(N):
        if int(S[i]) == 0 or int(S[i]) == 5:
            ans += i+1
else:
    cnt = [0 for _ in range(P)]
    cnt[0] = 1
    bai = 1
    v = 0
    for i in range(N)[::-1]:
        v = (v + int(S[i]) * bai) % P
        bai *= 10
        bai %= P
        cnt[v] += 1
    for i in range(P):
        ans += ((cnt[i] - 1 ) * cnt[i]) // 2
print(ans)

Solution (Python):
def main():
    N,P = map(int,input().split())
    S = input()[::-1]
    ans = 0
    if P == 2 or P == 5:
        for i,s in enumerate(S):
            if int(s) % P == 0:
                ans += N - i
    else:
        mods = [0] * P
        mods[0] = 1
        current = 0
        x = 1
        for s in S:
            current = (current + x * int(s)) % P
            ans += mods[current % P]
            mods[current % P] += 1
            x = x * 10 % P
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):

import sys
from collections import defaultdict

N,P=map(int, sys.stdin.readline().split())
S=sys.stdin.readline().strip()
S=S[::-1]

ans=0
if P in (2,5):
    len_S=len(S)
    for i,x in enumerate(S):
        x=int(x)
        if x%P==0:
            ans+=(len_S-i)
    print ans
else:
    L=[0] 
    val=0
    for i,x in enumerate(S):
        x=int(x)
        val+=pow(10,i,P)*x
        L.append(val%P)

    C=defaultdict(lambda: 0)
    for x in L:
        ans+=C[x]
        C[x]+=1
    print ans

Solution (Python):

import sys
from collections import defaultdict

N,P=map(int, sys.stdin.readline().split())
S=sys.stdin.readline().strip()
S=S[::-1]

ans=0
if P in (2,5):
    len_S=len(S)
    for i,x in enumerate(S):
        x=int(x)
        if x%P==0:
            ans+=(len_S-i)
    print ans
else:
    L=[0] 
    val=0
    for i,x in enumerate(S):
        x=int(x)
        val+=pow(10,i,P)*x
        L.append(val%P)

    C=defaultdict(lambda: 0)    
    for x in L:
        ans+=C[x]   
        C[x]+=1     
    print ans

Solution (Python):
n,p=map(int,input().split())
S=input()[::-1]
ans=0
if p==2:
    for i,s in enumerate(S):
        if int(s)%2==0:
            ans+=(n-i)
    print(ans)
    exit()

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


sd=0
d=1
count=[0]*(p+1)
count[0]+=1
for s in S:
    sd+=int(s)*d
    d*=10
    sd%=p
    d%=p
    count[sd]+=1

for cnt in count:
    ans+=cnt*(cnt-1)//2

print(ans)

Solution (Python):
from collections import defaultdict

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

if P in [2, 5]:
    ans = 0
    for r in range(N):
        if int(S[r]) % P == 0:
            ans += N - r
    print(ans)
    exit()

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

cnt = defaultdict(int)
for _cum in cum:
    cnt[_cum] += 1

ans = 0
for k, v in cnt.items():
    ans += v * (v - 1) // 2

print(ans)

Solution (Python):
from collections import defaultdict

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

if P in [2, 5]:
    ans = 0
    for r in range(N):
        if int(S[r]) % P == 0:
            ans += N - r
    print(ans)
    exit()

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

cnt = defaultdict(int)
for _cum in cum:
    cnt[_cum] += 1

ans = 0
for k, v in cnt.items():
    ans += v * (v - 1) // 2

print(ans)

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

if P in [2, 5]:
    ans = 0
    for r in range(N):
        if int(S[r]) % P == 0:
            ans += N - r
    print(ans)
    exit()

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

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

print(ans)

Solution (Python):
N, P = map(int, input().split())
S = input()
ans = 0
if P == 2:
    for i, d in enumerate(S):
        if d in "02468":
            ans += i + 1
elif P == 5:
    for i, d in enumerate(S):
        if d in "05":
            ans += i + 1
else:
    x = 1
    curr = 0
    mods = [0] * P
    mods[0] = 1
    for d in reversed(S):
        curr = (curr + x * int(d)) % P
        ans += mods[curr % P]
        mods[curr % P] += 1
        x = x * 10 % P
print(ans)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from collections import Counter

N, P = map(int, readline().split())
S = list(map(int, read().rstrip().decode()))

def solve_2(S):
    ind = (i for i, x in enumerate(S, 1) if x % 2 == 0)
    return sum(ind)

def solve_5(S):
    ind = (i for i, x in enumerate(S, 1) if x % 5 == 0)
    return sum(ind)

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


print(solve(S,P))

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

sum = 0
cnt = [0] * p
cnt[0] = 1
n = len(s)
for i in range(n):
    d = s[i] * pow(10, i, p)
    sum = (sum + d) % p
    cnt[sum] += 1

ans = 0
if p in [2, 5]:
    if p == 2:
        ok_list = [0, 2, 4, 6, 8]
    if p == 5:
        ok_list = [0, 5]

    for i in range(n):
        d = s[i]
        if d in ok_list:
            ans += n - i
           
else:
    for i in range(p):
        ans += cnt[i] * (cnt[i]-1) // 2


print(ans)

Solution (Python):

def main():
    N,P = map(int,input().split())
    s = list(input())[::-1]
    ary_mod = [0] * P
    ary_mod[0] = 1
    now = 0
    digit = 1
    ans = 0
    if P == 2:
        for i, ss in enumerate(s):
            if int(ss) % 2 == 0:
                ans += N-i
        print(ans)
        return
    if P == 5:
        for i, ss in enumerate(s):
            if int(ss) % 5 == 0:
                ans += N-i
        print(ans)
        return

    for i, ss in enumerate(s):
        now += int(ss) * digit % P
        digit *= 10
        digit %= P
        remind = now % P
        ary_mod[remind] += 1
    ans = 0
    for i, n in enumerate(ary_mod):
        ans += (n*(n-1)) // 2
    print(ans)
if __name__=='__main__':
    main()

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 5 + 10)


def input(): return sys.stdin.readline().strip()


def resolve():
    N, P = map(int, input().split())
    S = str(input())

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

        else:
            mods = [0] * P  
            tenfactor = 1
            mod = 0
            mods[mod] += 1

            for i in range(N):
                mod = (mod + int(S[N - i - 1]) * tenfactor) % P
                tenfactor = (tenfactor * 10) % P
                mods[mod] += 1

            res = 0
            for p in range(P):
                res += mods[p] * (mods[p] - 1) // 2

        return res

    print(main())


resolve()

Solution (Python):
from collections import Counter

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:      
  mods = [0]*p
  mods[0] = 1
  m = 0
  d = 1  
  for i in range(n):
    m = (m + int(s[-i-1])*d) % p
    d = (d * 10) % p    
    mods[m] += 1
  
  for i in range(p):
    ans += mods[i]*(mods[i]-1)//2

print(ans)

Solution (Python):


from collections import Counter


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


if P==2 or P==5:
    ans = 0
    for i in range(N-1, -1, -1):
        s = int(S[i])
        if s%P==0:
            ans += i + 1
    
    print(ans)
else:
    p_nums = [0]*(N+1)
    s = 0
    for i in range(N-1, -1, -1):
        s = int(S[i]) * pow(10, N - i - 1, P) + s
        p_nums[N - i] = s%P
    p_counter = [0]*P
    for i in range(N+1):
        p_counter[p_nums[i]] += 1
    ans = 0
    for i in range(P):
        ans += p_counter[i] * (p_counter[i] - 1) // 2
    print(ans)

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

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

    cnt_a = 0
    for s in S[::-1]:
        if int(s) % P == 0:
            cnt_a += 1

        cnt += cnt_a
else:
    r_lst = [0] * P
    r_lst[0] = 1

    cnt = 0
    num = 0

    for i, s in enumerate(S[::-1]):
        num  = (num + int(s) * pow(10, i, P)) % P
        cnt += r_lst[num]

        r_lst[num] += 1


print(cnt)

Solution (Python):

import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=2019
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N,P=map(int,input().split())
    A=list(map(int,list(input())[::-1]))
    ans=0
    if P==2 or P==5:
        if P==2:
            s=set([i*2 for i in range(5)])
        else:
            s=set([i*5 for i in range(2)])
        for i,x in enumerate(A[::-1],1):
            if x in s:
                ans+=i
    else:
        S=[0]*(N+1)
        for i in range(N):
            S[i+1]=(S[i]+A[i]*pow(10,i,P))%P
        l=[0]*P
        for i in range(N+1):
            ans+=l[S[i]]
            l[S[i]]+=1
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
"""
s=1817181712114 なら
4
10
100
2000
10000
700000
1000000
80000000
100000000
7000000000
10000000000
800000000000
1000000000000
の数列とみて, 各々%Pを取ってzero sum range
P=2,5がコーナー
"""
from collections import Counter
def make_modlist(Len,mod):
    modlist=[0]*Len
    modlist[0]=1
    for i in range(1,Len):
        modlist[i]=10*modlist[i-1]%mod
    return modlist
n,p=map(int,input().split())
a=list(map(int,input()))
ans=0
a.reverse()
if p==2 or p==5:
    for i in range(n):
        if a[i]%p==0:
            ans+=n-i
else:
    d=make_modlist(n,p)
    b=[0]*(n+1)
    for i in range(n):
        b[i+1]=a[i]*d[i]%p
    for i in range(1,n+1):
        b[i]+=b[i-1]
        b[i]%=p
    for i in Counter(b).values():
        ans+=i*(i-1)//2
print(ans)

Solution (Python):
from collections import Counter
N,MOD=map(int,input().split())
S=input()
res=0
if MOD==2 or MOD==5:
    for i in range(N):
        if(int(S[N-i-1])%MOD==0):
            res+=N-i
else:
    Cum=[0]*(N+1)
    for i in range(N):
        Cum[i+1]=(Cum[i]+int(S[N-i-1])*pow(10,i,MOD))%MOD
    c=Counter(Cum).most_common()
    for a,b in c:
        res+=b*(b-1)//2
print(res)

Solution (Python):
import sys

IS = lambda: sys.stdin.readline().rstrip()
II = lambda: int(IS())
MII = lambda: list(map(int, IS().split()))
MIIZ = lambda: list(map(lambda x: x-1, MII()))

INIT_VAL = 0
MD2 = lambda d1,d2: [[INIT_VAL]*d2 for _ in range(d1)]
MD3 = lambda d1,d2,d3: [MD2(d2,d3) for _ in range(d1)]

DIVC = lambda x,y: -(-x//y)
DIVF = lambda x,y: x//y

def main():
    n, p = MII()
    s = list(map(int, IS()))
    if 10%p == 0: 
        cnt = 0
        for i, si in enumerate(s):
            if si%p == 0:
                cnt += i+1
        print(cnt)
        return None

    d = [0]*p
    d[0] = 1 
    ss = 0
    x = 1
    for si in s[::-1]:
        ss += x*si
        ss %= p
        d[ss] += 1
        x = (10*x)%p 
    cnt = 0
    for di in d:
        cnt += di*(di-1)//2 
    print(cnt)


if __name__ == "__main__":
    main()

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

ans = 0
ten = 1
d = 0

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

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

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

Solution (Python):
from collections import defaultdict
dd = defaultdict(int)
n,p=map(int, input().split())
S = list(input().rstrip())
tmp = 0
r=1
su=0
dd[0]=1
if p==2 or p==5:
    c=n
    for s in S[::-1]:
        if int(s)%p==0:
            su+=c
        c-=1
    print(su)
else:
    for s in S[::-1]:
        tmp+=int(s)*r
        tmp%=p
        dd[tmp]+=1
        r*=10
        r%=p
    for i in dd.values():
        su += (i*(i-1))//2
    print(su)

Solution (Python):
import sys
n,p=map(int,input().split())
s=list(input())
if p==2 or p==5:
    ans=0
    for i in range(n):
        if int(s[i])%p==0:
            ans+=i+1
    print(ans)
    sys.exit(0)
ans=0
count=[0]*p
count[0]=1
s=s[::-1]
num=0
seki=1
for i in range(n):
    num+=int(s[i])*seki
    num=num%p
    count[num]+=1
    seki=seki*10
    seki=seki%p
for i in range(p):
    N=count[i]
    ans+=N*(N-1)//2
print(ans)

Solution (Python):
import sys

IS = lambda: sys.stdin.readline().rstrip()
II = lambda: int(IS())
MII = lambda: list(map(int, IS().split()))
MIIZ = lambda: list(map(lambda x: x-1, MII()))

INIT_VAL = 0
MD2 = lambda d1,d2: [[INIT_VAL]*d2 for _ in range(d1)]
MD3 = lambda d1,d2,d3: [MD2(d2,d3) for _ in range(d1)]

DIVC = lambda x,y: -(-x//y)
DIVF = lambda x,y: x//y

def main():
    n, p = MII()
    s = list(map(int, IS()))
    if 10%p == 0: 
        cnt = 0
        for i, si in enumerate(s):
            if si%p == 0:
                cnt += i+1
        print(cnt)
        return None

    d = {i: 0 for i in range(p)}
    d[0] = 1
    ss = 0
    x = 1
    for si in s[::-1]:
        ss += x*si
        ss %= p
        d[ss] += 1
        x = 10*x%p
    cnt = 0
    for dv in d.values():
        cnt += dv*(dv-1)//2
    print(cnt)


if __name__ == "__main__":
    main()

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

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

r = [0]*p
r[0] = 1
t = 1
z = 0
for i in reversed(s):
    z = int(i) * t + z
    t *= 10
    t %= p
    z %= p
    r[z] += 1

ans = sum(i*(i-1)//2 for i in r)
print(ans)

Solution (Python):
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    N, P = map(int, readline().split())
    S = [int(i) for i in readline().strip()[::-1]]

    ans = 0
    if P == 2 or P == 5:
        for i, s in enumerate(S):
            if s % P == 0:
                ans += N - i
        print(ans)
        exit()

    a = {}
    a[0] = 1
    t = 0
    x = 1
    for s in S:
        t += s * x
        t %= P
        
        if t in a:
            a[t] += 1
        else:
            a[t] = 1

        x *= 10
        x %= P
    
    ans = 0
    for v in a.values():
        ans += v * (v-1) // 2
    
    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, s in enumerate(S, 1):
    if int(s) % P == 0:
      ans += i
  print(ans)
else:
  dp = [0] * (N+1)
  for i, s in enumerate(S, 1):
    dp[i] = (dp[i-1]*10 + int(s)) % P
  digit = 1
  for i in range(N):
    j = N - i
    dp[j] = (dp[j] * digit) % P
    digit = (digit * 10) % P
  
  d = {}
  ans = 0
  for r in dp:
    if r in d:
      ans += d[r]
      d[r] += 1
    else:
      d[r] = 1
  print(ans)

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

def main():
    N, P = map(int, readline().split())
    S = [int(i) for i in readline().strip()[::-1]]

    ans = 0
    if P == 2 or P == 5:
        for i, s in enumerate(S):
            if s % P == 0:
                ans += N - i
        
        print(ans)
        exit()

    a = [0]
    s = 0
    for i in range(N):
        s += S[i] * pow(10, i, P)
        a.append(s % P)
    
    t = Counter(a)

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

    


if __name__ == "__main__":
    main()

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


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

Solution (Python):

def resolve():
    l, P = map(int, input().split())
    S = input()

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

    cnts = [0] * P
    cnts[0] = 1
    num, d = 0, 1
    for s in S[::-1]:
        s = int(s)
        num = (num + (s * d)) % P
        d = (10 * d) % P
        cnts[num] += 1

    for cnt in cnts:
        ans += cnt * (cnt - 1) // 2
    print(ans)


if __name__ == "__main__":
    resolve()

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

if P%2 == 0 or P%5 == 0:
    ans = 0
    
    for i,j in enumerate(S):
        if int(j)%P == 0:
            ans += i+1
    print(ans)
else:
    tmp = 0
    mod = [0]*P
    mod[0] = 1
    S = S[::-1]
    for i,j in enumerate(S):
        tmp = (tmp + int(j)*pow(10,i,P))%P
        mod[tmp] += 1    
    print(sum([i*(i-1)//2 for i in mod]))

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

from collections import Counter

n, p = map(int, readline().split())
s = readline().rstrip().decode()
cnt = 0
if p == 2 or p == 5:
    for i, ss in enumerate(s):
        if int(ss) % p == 0:
            cnt += (i + 1)
else:
    memo = [0]
    m = 0
    d = 1
    for ss in s[::-1]:
        m += int(ss) * d
        m %= p
        d *= 10
        d %= p
        memo.append(m)
    counter = Counter(memo)
    for i in range(p + 1):
        cnt += counter[i] * (counter[i] - 1) // 2
print(cnt)

Solution (Python):
N, P = map(int, input().split())
S = [int(i) for i in input()]
from collections import Counter
def solve(S,N,P):
    if P==2 or P==5:
        ans = 0
        for i in range(N):
            if S[i]%P==0:
                ans += i+1
        return ans
    cum = [0]*(N+1)
    mods = [0]*N
    mods[0] = 1
    for i in range(1,N):
        mods[i] = mods[i-1]*10%P
    for i in range(N):
        cum[i+1] = (cum[i]+S[N-1-i]*mods[i])%P
    c = Counter(cum)
    ans = 0
    for v in c.values():
        ans += v*(v-1)//2
    return ans
print(solve(S,N,P))

Solution (Python):
N,P=[int(s) for s in input().split()]
S=list(input())
if P!=2 and P!=5:
  ls=[0 for _ in range(N)]
  mod=[0 for _ in range(P)]
  d=10
  ls[0]=int(S[-1])%P
  mod[ls[0]]+=1
  for i in range(1,N):
    ls[i]=(ls[i-1]+d*int(S[-1-i]))%P
    d=(d*10)%P
    mod[ls[i]]+=1
  
  
  ans=mod[0]
  for i in range(N):
    m=ls[i]
    mod[ls[i]]-=1
    ans+=mod[ls[i]]
else:
  ans=0
  for i in range(N):
    if int(S[i])%P==0:
      ans+=i+1
print(ans)

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

count = [0]*p

key = 0
if p%2 and p%5:
  count = [0]*p
  key = 0
  
  mod = 1
  for i in range(n):
    key += (mod*int(s[n-1-i]))%p
    key %= p
    count[key] += 1
    mod *= 10
    mod %= p
  ans = count[0]
  for i in range(p):
    if count[i] >= 2:
      ans += (count[i])*(count[i]-1)//2
else:
  ans = 0
  for i in range(n):
    key = int(s[n-1-i])
    if key%p == 0:
      ans += n-i
print(ans)

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

def solve(S,N,P):
    if P == 2:
        ans = 0
        for i in range(N):
            if int(S[i])%P == 0:
                ans += i+1
        return ans
    if P == 5:
        ans = 0
        for i in range(N):
            if int(S[i])%P == 0:
                ans += i+1
        return ans
    
    S = S[::-1]
    mod_list = [0]*P
    mod_list[0] = 1

    mod = P
    tmp = 0

    for i in range(N):
        tmp = (tmp + int(S[i])*pow(10,i,mod))%mod
        mod_list[tmp] += 1
    
    ans = 0
    for i in mod_list:
        ans += i*(i-1)//2
        
    return ans

print(solve(S,N,P))

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

XX = 0
if P == 2:
    for i in range(N):
        if int(S[i]) % 2 == 0:
            XX += i + 1
    print(XX)
elif P == 5:
    for i in range(N):
        if int(S[i]) % 5 == 0:
            XX += i + 1
    print(XX)
else:
    base = 1
    X = [0 for i in range(N)]
    X[-1] = int(S[-1])
    for i in range(N, 0, -1):
        X[i-1] = (base * int(S[i-1])) % P
        base *= 10
        base %= P
    for i in range(1, N):
        X[i] += X[i-1]
        X[i] %= P
    D = {i: 0 for i in range(P)}
    D[0] = 1
    for i in range(N):
        D[X[i]] += 1
    XX = 0
    for i in D:
        XX += (D[i] * (D[i] - 1)) // 2
    print(XX)

Solution (Python):

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

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

n, p = [int(x) for x in input().split()]
s = input().rstrip()[::-1]
ans = 0
if p == 2:
    for i in range(n):
        if int(s[i]) % 2 == 0:
            ans += (n - i)
    print(ans)
    sys.exit()
if p == 5:
    for i in range(n):
        if int(s[i]) == 0 or int(s[i]) == 5:
            ans += (n - i)
    print(ans)
    sys.exit()
t = [0, int(s[0]) % p]
mul = 10
for i in range(1, n):
    t.append((t[-1] + int(s[i])*mul) % p)
    mul *= 10
    mul %= p
from collections import Counter
c = Counter(t)
for i in c.keys():
    ans += c[i]*(c[i] - 1) // 2
print(ans)

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


revS = S[::-1] 





if(10 % P == 0):
  res = 0

  for index, num in enumerate(revS):
    if(int(num) % P == 0) :
      res += len(revS) - index

  print(res)

else:

  
  cs = 0

  
  counts = [0] * P

  
  
  
  counts[cs] += 1

  
  d = 1

  
  for num in revS:
    m = (int(num) * d) % P
    cs = (cs + m) % P

    counts[cs] += 1

    
    d *= 10

    
    
    d %= P

  res = 0

  for n in counts:
    
    res += n * (n - 1) // 2

  print(res)

Solution (Python):
import sys
sys.setrecursionlimit(10**8)
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 li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for _ in range(j)] for _ in range(k)]




N, mod = mi()
S = list(map(int, list(input())))
ans = 0

if 10 % mod != 0:
    mod_list = [0]
    ten = 1
    for num in S[::-1]:
        yo = (num * ten + mod_list[-1]) % mod
        mod_list.append(yo)
        ten = (ten * 10) % mod

    cnt = [0]*mod
    for yo in mod_list:
        cnt[yo] += 1

    for i in range(mod):
        ans += cnt[i] * (cnt[i]-1) // 2

else:
    for i, num in enumerate(S):
        if num % mod == 0:
            ans += i+1

print(ans)

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

if P == 2 or P == 5:
    ans = 0
    for i in range(N):
        if int(S[i]) % P == 0:
            ans += i+1
    print(ans)
else:
    mod_cnt = [0]*P
    mod_cnt[0] = 1
    k = 0.1
    t = 0
    for i in range(1, N+1):
        k = int(k * 10) % P
        t = (t + k * int(S[-i])) % P
        mod_cnt[t] += 1
    ans = 0
    for cnt in mod_cnt:
        ans += (cnt * (cnt-1)) // 2
    print(ans)

Solution (Python):
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time


def I(): return int(input())


def S(): return input()


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


def MS(): return map(str, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


YNL = {False: 'No', True: 'Yes'}
YNU = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']

show_flg = False



def main():
    N, P = MI()
    s = list(map(int, S()[::-1]))
    ans = 0
    sum_of_d = 0
    cnts = [0] * P
    cnts[0] = 1
    A = [0] * N
    D = [0] * N

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

    for i in range(N):
        d = s[i] * pow(10, i, P)
        A[i] = d % P
        if i == 0:
            D[i] = A[i]
        else:
            D[i] = (D[i-1] + A[i]) % P
        
        

    for d in D:
        cnts[d] += 1

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

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate
import sys
import bisect
import string
import math
import time


def I(): return int(input())


def S(): return input()


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


def MS(): return map(str, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


YNL = {False: 'No', True: 'Yes'}
YNU = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**10
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']

show_flg = False



def main():
    N, P = MI()
    s = list(map(int, S()[::-1]))
    ans = 0
    sum_of_d = 0
    cnts = [0] * P
    cnts[0] = 1
    A = [0] * N
    D = [0] * N

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

    for i in range(N):
        d = s[i] * pow(10, i, P)
        A[i] = d % P
        if i == 0:
            D[i] = A[i]
        else:
            D[i] = (D[i-1] + A[i]) % P
        cnts[D[i]] += 1
        
        

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

    print(ans)


if __name__ == '__main__':
    main()

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

s = input()
rem = [0 for i in range(p)]
total = 0
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:
    for i in range(len(s)-1, -1, -1):
        total += int(s[i])*pow(10, len(s)-i-1, p)
        total %= p
        if total % p == 0:
            ans += 1
        ans += rem[total]
        rem[total] += 1

    print(ans)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


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

        ans = 0
        for v in val:
            ans += v * (v - 1) // 2

    print(ans)


if __name__ == "__main__":
    main()