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

    TF = 2, 5
    if p in TF:
        answer = 0
        for i, char in enumerate(s):
            if int(char) % p == 0:
                answer += i + 1
        print(answer)
        return

    
    remainders = []
    t = 0
    for i, char in enumerate(s[::-1]):
        t += pow(10, i, p) * int(char)
        remainders.append(t % p)
    remainders = remainders[::-1]
    remainders.append(0)
    
    
    
    d = {}
    for remainder in remainders:
        if remainder not in d:
            d[remainder] = 1
        else:
            d[remainder] += 1
    answer = 0
    for count in d.values():
        if count > 1:
            answer += count * (count - 1) // 2
    print(answer)

main()

Solution (Python):
N, P = map(int, input().split())
S = list(map(int,list(input())))
mod = P
Cum = []
S.reverse()

if 10%P!=0: 
    temp = 0
    power = 1
    for i in range(N):
        temp += (S[i]*power)%mod
        temp %= mod
        power *= 10
        power %= mod
        Cum.append(temp)

    from collections import Counter

    counter=Counter(Cum)

    counter[0]+=1

    ans = 0
    for i in counter:
        ans += int(counter[i]*(counter[i]-1)/2)
    print(ans)    

else:
    ans = 0
    S.reverse()
    for i in range(N):
        if S[i]%P==0:
            ans += (i+1)          
    print(ans)

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

sum = 0
cnt = [0] * p
cnt[0] = 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(n):
        d = s[i] * pow(10, i, p)
        sum = (sum + d) % p
        cnt[sum] += 1
    for i in range(p):
        ans += cnt[i] * (cnt[i]-1) // 2
print(ans)

Solution (Python):
from collections import Counter

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

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

t = 1
for i in reversed(range(N)):
    tmp = int(S[i]) * t % P
    rui[i] = (rui[i + 1] + tmp) % P
    t *= 10
    t %= P

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

Solution (Python):
from collections import defaultdict as dd
N,p=map(int,input().split())
s=input()
res=0
dic=dd(int)
c = [0]*(N+1)

if p==2 or p==5:
    for i in range(N):
        now = int(s[N-i-1])%p
        if now==0:
            res += N-i
    print(res)
    exit()

for i in range(N):
    now = int(s[N-i-1])%p
    c[i+1] = (c[i]+pow(10,i,p)*now)%p
for val in c:
    dic[str(val)] += 1
    if dic[str(val)] >= 2:
        res += dic[str(val)]-1
print(res)

Solution (Python):
def main():
  N,P = map(int,input().split())
  S = list(map(int,list(input())))
  S=S[::-1]
  ans = 0
  if P==2:
    l = [0,2,4,6,8]
    for i,s in enumerate(S):
      if s in l:
        ans+=N-i
  elif P==5:
    l=[0,5]
    for i,s in enumerate(S):
      if s in l:
        ans+=N-i

  else:
    l = [0]*P
    a=0
    for i in range(N):
      b = pow(10,i,P)
      b *= S[i]
      b %= P
      a+=b
      a%=P
      l[a]+=1
    ans+=l[0]
    for i in l:
      ans+=i*(i-1)//2

  print(ans)
  
main()

Solution (Python):
def main():
  N,P = map(int,input().split())
  S = list(map(int,list(input())))
  S=S[::-1]
  ans = 0
  if P==2:
    l = [0,2,4,6,8]
    for i,s in enumerate(S):
      if s in l:
        ans+=N-i
  elif P==5:
    l=[0,5]
    for i,s in enumerate(S):
      if s in l:
        ans+=N-i

  else:
    l = [0]*P
    a=0
    for i in range(N):
      b = pow(10,i,P)
      b *= S[i]
      b %= P
      a+=b
      a%=P
      l[a]+=1
    ans+=l[0]
    for i in l:
      ans+=i*(i-1)//2

  print(ans)
  
main()

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

N, P = map(int, input().split())
S=input().strip()
if P in {2, 5}:
    r=0
    for i in range(N):
        if not int(S[i])%P:
            r+=i+1
    print(r)
else:
    S = S[::-1]
    r=0
    from collections import defaultdict
    d=defaultdict(int)
    d[0] += 1
    R=0
    X=1
    for i in range(N):
        r += int(S[i])*X
        R += d[r%P]
        X = (X*10)%P
        d[r%P]+=1
    print(R)

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:
    mod = [-1 for i in range(p)]
    mod[0] = 0
    mp = 0
    m10 = 1
    
    for i in range(n-1, -1, -1):
        mp = (mp + int(s[i]) * m10) % p
        mod[mp] += 1
        m10 = (10 * m10) % p

    for m in mod:
        ans += m*(m+1)//2

print(ans)

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

ans = 0
mod = [-1 for i in range(p)]
mod[0] = 0

if p == 2 or p == 5:
    for i in range(n):
        if int(s[i]) % p == 0:
            ans += i+1
else:
    mp = 0
    m10 = 1
    for i in range(n-1, -1, -1):
        mp = (mp + int(s[i]) * m10) % p
        m10 = (10 * m10) % p
        mod[mp] += 1

    for m in mod:
        ans += m*(m+1)//2

print(ans)

Solution (Python):
N, P = map(int, input().split())
S = input()
ans = 0
mod = [0]*P
if P==2 or P==5:
    for i in range(N):
        if int(S[i])%P==0:
            ans+=i+1
    print(ans)
else:
    un1 = 0
    un = 0
    for i in range(N-1, -1, -1):
        
        a =int(S[i])*pow(10,un,P)+(un1)%P
        un += 1
        un1 = a
        mod[a%P]+=1
    ans += mod[0]  
    for i in range(P):
        ans += mod[i]*(mod[i]-1)/2
    print(int(ans))

Solution (Python):

import sys
import math

import itertools
from collections import Counter

n,p = (int(i) for i in input().split())

s = [int(i) for i in list(input())] 

answer = 0

q=0
x=[]
if p == 2 or p == 5:
    for i in range(n-1,-1,-1):
        if s[i]%p == 0:
            answer += i+1
else:
    d=1
    for i in range(n-1,-1,-1):
        q = (d*s[i]+q)%p
        x.append(q)
        d = (d * 10)%p
    
    counter = Counter(x)
    

    for k in counter:
    
        if k==0:
            answer += counter[k] * (counter[k]+1) // 2
        else:
            answer += counter[k] * (counter[k]-1) // 2

print(answer)

Solution (Python):



def main():
  n, p = map(int, input().strip().split())
  s = input().strip()
  ans = 0
  if 10 % p == 0:
    for r in range(n):
      if int(s[r]) % p == 0:
        ans += r+1
    print(ans)
    return
  
  remains = [0] * (n+1)
  counts = [0] * p
  counts[0] += 1
  x = 1
  for r in range(n):
    remain = (int(s[-(r+1)]) * x) % p
    remains[-(r+1)] = (remains[-r] + remain) % p
    counts[remains[-(r+1)]] += 1
    x = (x * 10) % p
  for count in counts:
    ans += (count * (count - 1)) // 2
  print(ans)

if __name__=='__main__':
  main()

Solution (Python):



def main():
  n, p = map(int, input().strip().split())
  s = input().strip()
  ans = 0
  if 10 % p == 0:
    for r in range(n):
      if int(s[r]) % p == 0:
        ans += r+1
    print(ans)
    return
  
  remains = [0] * (n+1)
  counts = [0] * p
  counts[0] += 1
  x = 1
  for r in range(n):
    remain = (int(s[-(r+1)]) * x) % p
    remains[-(r+1)] = (remains[-r] + remain) % p
    counts[remains[-(r+1)]] += 1
    x = (x * 10) % p
  for count in counts:
    ans += (count * (count - 1)) // 2
  print(ans)

if __name__=='__main__':
  main()

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

ans = 0
mod = [-1 for i in range(p)]
mod[0] = 0

if p == 2 or p == 5:
    for i in range(n):
        if int(s[i]) % p == 0:
            ans += i+1
else:
    mp = 0
    m10 = 1
    for i in range(n-1, -1, -1):
        m10 = (10 * m10) % p
        mp = (mp + int(s[i]) * m10) % p
        mod[mp] += 1

    for m in mod:
        ans += m*(m+1)//2

print(ans)

Solution (Python):
N, P = map(int, input().split())
S = [int(_) for _ in list(input())]
if P == 2 or P == 5:
    ans = 0
    for n in range(N):
        if S[n] % P == 0:
            ans += n + 1
    print(ans)
else:
    S = [(S[n] * pow(10, N - n - 1, P)) % P for n in range(N)]
    S.reverse()
    T = [0]
    for s in S:
        T.append((T[-1] + s) % P)
    lst = {i: 0 for i in range(P)}
    ans = 0
    for t in T:
        ans += lst[t]
        lst[t] += 1
    print(ans)

Solution (Python):



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

ans = 0
mod_P = [0] * P
mod_P[0] += 1

if P in [2,5]:
    
    for i in range(N):
            """
            今見ているiかそれより左側にある物をU_iとして選択する場合に割り切れるようになるので、
            いまのiを含む左にあるものの個数を足す
            """
            if int(S[i]) % P == 0:
                ans += i+1
    
    print(ans)

else:
    """
    右端から見て、
    ([右端からi番目までの数字] - [右端からj番目までの数字]) % Pが0になるならOK
    [右端からi番目までの数字] % P = X となるなら、[右端からj番目までの数字] % P = X であれば割り切れる
    なので、i番目までを見ているときに、そこより右側で、余りがi番目までをPで割った時と同じになる個数が分かればよい。

    毎回律義にi番目までを数値化して、mod P をとってるとTLEになるので、
    右からi番目の数字 10 ** i + それまで
    の形で積み重ねていく。
    また、余りの問題なので、余りの世界で現在値を保存しておく(今回みたいな大きな値について毎回modをとるとめちゃくちゃ遅い)

    例１の3543と3のときのように、
    うしろから最後まで見切って3543について考えるとする。
    このとき、、
    ・端までとるU_5：U=3543
    ・右端の3だけのU_4：U=354
    ・543のU_1：U=3
    の３パターンで余りを0にしうる
    みたいなかたち
    """
    curr = 0
    for i in range(N):
        curr = int(S[N-1-i]) * pow(10, i, P) + curr
        curr %= P
        ans += mod_P[curr]
        mod_P[curr] += 1
    print(ans)

Solution (Python):
from collections import Counter
n,p=map(int,input().split())
A=list(map(int,input()))
def U(x):
    return int(A[x:])
if p in [2,5]:
    keta=0
    ans=0
    for i in range(n):
        keta+=1
        if int(A[i])%p==0:
            ans+=keta
    print(ans)
    exit()
    
acc = [0 for i in range(n)] 
cur = A[-1] % p
acc[-1] = cur
k = 1
for i in range(n-2, -1, -1):
    cur += pow(10, k, p) * A[i]
    cur %= p
    acc[i] = cur
    k += 1
acc = acc + [0]
 
C = Counter(acc)
ans = 0
for v in C.values():
    ans += v * (v-1) // 2
print(ans)

Solution (Python):

from collections import Counter
n,p=map(int,input().split())
s=input()
cnt=0

if p==2 or p==5:
    for i in range(n):
        if int(s[i])%p==0:
            cnt+=i+1
else:
    U=[0]*(n+1)
    for i in range(n,0,-1):
        U[i-1]=(int(s[i-1])*pow(10,n-i,p)+U[i])%p
    
    C=Counter(U)
    for c in C.values():
        cnt+=c*(c-1)//2

print(cnt)

Solution (Python):
import sys


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


def _ia(): return map(int, sys.stdin.readline().strip().split())


n, p = _ia()
u = [1 if i == 0 else 0 for i in range(p)]
s = _s()
cnt = 0
if p == 2 or p == 5:
    for i, c in enumerate(s):
        if int(c) % p == 0:
            cnt += i + 1
else:
    b = 1
    m10 = 10 % p
    prev = 0
    for c in s[::-1]:
        ui = prev = (prev + int(c) * b) % p
        b = (b*m10) % p
        cnt += u[ui]
        u[ui] += 1
print(cnt)

Solution (Python):





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

    ret = 0
    if P in {2, 5}:
        for i, x in enumerate(S, 1):
            if x % P == 0:
                ret += i
        print(ret)
        return

    else:
        curr_num = 0
        counter = [0] * P
        counter[0] = 1
        mul = 1
        for i, x in enumerate(reversed(S)):
            curr_num = (curr_num + x * mul) % P
            counter[curr_num] += 1
            mul = (mul * 10) % P

        def choose_2(x):
            return x * (x - 1) // 2

        ret = sum(choose_2(cnt) for cnt in counter)
        print(ret)
        return


if __name__ == '__main__':
    main()

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

    ret = 0
    if P in {2, 5}:
        for i, x in enumerate(S, 1):
            if x % P == 0:
                ret += i
        print(ret)
        return

    else:
        curr_num = 0
        counter = [0] * P
        counter[0] = 1
        mul = 1
        for i, x in enumerate(reversed(S)):
            curr_num = (curr_num + x * mul) % P
            ret += counter[curr_num]
            counter[curr_num] += 1
            mul = (mul * 10) % P
        print(ret)
        return


if __name__ == '__main__':
    main()

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:
    s_inv = s[::-1]
    lst = [0 for i in range(n+1)]
    n_amari = [0 for i in range(p)]
    amari = 1
    ans = 0
    for i in range(n):
        amari = (amari * 10) % p
        lst[i+1] = (amari * int(s_inv[i]) + lst[i]) % p
        if lst[i+1] != 0:
            ans += n_amari[lst[i+1]]
            n_amari[lst[i+1]] += 1
        else:
            n_amari[lst[i+1]] += 1
            ans += n_amari[lst[i+1]]
    print(ans)

Solution (Python):
N,P = map(int,input().split())
s = list(input())
S = [0]*N

for i in range(N):
    S[i] = int(s[i])

count = 0

if P != 2 and P != 5:
    now = 0
    remainder = []
    for i in range(1,N+1):
        now += S[N-i] * (pow(10,(i-1),P) )
        remainder.append(now % P)

    result={}
    for i in range (0,len(remainder)):
        item = remainder[i]
        if item in result:
            result[item] = result[item]+1
        else:
            result[item] = 1

    for k in result.keys():
        if k == 0:
            if result[0] >= 2:
                count += result[0] + result[0]*(result[0]-1)//2
            else:
                count += result[0]
        else:
            count += result[k]*(result[k]-1)//2

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

print(count)

Solution (Python):
import sys
from collections import Counter

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, P = lr()
S = sr()

remain = [0] * N
cur = 0
answer = 0
S_rev = S[::-1]
power = 1
for i in range(N):
    if i >= 1:
        power *= 10
        power %= P
    num = cur + power * int(S_rev[i])
    cur = num % P
    remain[i] = cur

if P == 2 or P == 5:
    ind = (i for i, x in enumerate(S, 1) if int(x) % P == 0)
    answer = sum(ind)

else:
    counter = Counter(remain)
    answer += counter[0]
    for k, v in counter.items():
        answer += v * (v-1) // 2

print(answer)

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

    ret = 0
    if P in {2, 5}:
        for i, x in enumerate(S, 1):
            if x % P == 0:
                ret += i
        print(ret)
        return

    else:
        curr_num = 0
        counter = [0] * P
        counter[0] = 1
        for i, x in enumerate(reversed(S)):
            curr_num = (curr_num + x * pow(10, i, P)) % P
            ret += counter[curr_num]
            counter[curr_num] += 1
        print(ret)
        return


if __name__ == '__main__':
    main()

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[-1-i]) % p == 0:
            ans += n-i
    print(ans)
    exit()
else:
  s = s[::-1]
  cnt = [0]*p 
  cnt[0] = 1 
  modp = 0
  for i,c in enumerate(map(int,s)):
    modp = (c*pow(10,i,p) + modp)%p
    cnt[modp] += 1
  for i in range(p):
    ans += cnt[i]*(cnt[i]-1) //2
  print(ans)

Solution (Python):
import sys
import collections
n,p=map(int,input().split())
s=list(input())
s.reverse()
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])%5==0:
      ans+=n-i
  print(ans)
  sys.exit()

l=[0,int(s[0])%p]
x=int(s[0])
y=1
for i in range(1,n):
  y*=10
  y%=p
  x+=(y*int(s[i]))%p
  x%=p
  l.append(x)
L=collections.Counter(l)
for j in L.values():
  ans+=j*(j-1)//2
print(ans)

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

n,p = map(int,input().split())
s = list(input())
for i in range(n):
    s[i] = int(s[i])
    
if p == 2 or p == 5:
    res = 0
    for i in range(n):
        if s[i]%p == 0:
            res += i+1
    print(res)
else:
    d = 1
    q = [0]
    for i in range(n-1,-1,-1):
        q.append((q[-1]+s[i]*d)%p)
        d = d*10%p
    q.sort()
    res = 0
    q.append(-1)
    f = 1
    for i in range(n+1):
        if q[i]==q[i+1]:
            f += 1
        else:
            res += f*(f-1)//2
            f=1
    print(res)

Solution (Python):
import sys
import collections
n,p=map(int,input().split())
s=list(input())
s.reverse()
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])%5==0:
      ans+=n-i
  print(ans)
  sys.exit()

l=[0,int(s[0])%p]
x=int(s[0])
y=1
for i in range(1,n):
  y*=10
  y%=p
  x+=(y*int(s[i]))%p
  x%=p
  l.append(x)
L=collections.Counter(l)
for j in L.values():
  ans+=int(j*(j-1)/2)
print(ans)

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

r_circ = []
v = 1
while True:
    r = v % P
    if r in r_circ:
        break
    r_circ.append(r)
    v *= 10

ans = 0
if P in (2, 5):
    for i, s in enumerate(S):
        if int(s) % P == 0:
            ans += i+1
else:
    pr = 0
    rcntmap = [0] * P
    rcntmap[0] = 1  
    for i in reversed(range(len(S))):
        d = int(S[i])
        r = (d * r_circ[(len(S)-1-i) % len(r_circ)] + pr) % P
        
        ans += rcntmap[r]
    
        rcntmap[r] += 1
        pr = r

print(ans)

Solution (Python):






import math
from functools import lru_cache





MOD = 10**9 +7
INF = float('inf')





kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])
    return arr





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


mods = [0 for _ in range(P)]
count = 0

loop = 0
mod = 0

if P != 2 and P != 5: 
  for digit in S[::-1]:
    loop += 1
    digit = int(digit)
    mod = (mod + digit*pow(10,loop-1,P))%P
    count += mods[mod]
    mods[mod] += 1
    if mod == 0:
      count += 1
else:
  for digit in S:
    loop += 1
    if int(digit)%P == 0:
      count += loop


  

print(count)

Solution (Python):
import sys

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

if P in [2, 5]:
    ans = 0
    if P == 2:
        ok = [0, 2, 4, 6, 8]
    else:
        ok = [0, 5]
        
    for i in range(N):
        if S[i] in ok:
            ans += N - i
    print(ans)
    sys.exit()

cnt = [0] * P
cnt[0] = 1

s = 0
for i in range(N):
    d = S[i] * pow(10, i, P)
    s += d
    s %= P
    cnt[s] += 1

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

print(ans)

Solution (Python):
N,P = map(int,input().split(" "))
S = input()
ans = 0
if P in [2,5]:
    for i in range(N):
        if int(S[i])%P==0:
            ans += i+1
else:
    lis = [0 for _ in range(N+1)]
    ten = 1
    for i in reversed(range(N)):
        tmp = int(S[i])*ten%P
        lis[i] = (lis[i+1]+tmp)%P
        ten *= 10
        ten %= P
    cnt = [0 for _ in range(P)]
    for i in reversed(range(N+1)):
        ans += cnt[lis[i]]
        cnt[lis[i]] += 1

print(ans)

Solution (Python):
n,p=map(int,input().split());s,n,N,c,d=map(int,list(input())),1,0,0,[0]*p
if p!=5:
 for i in s:N,a=(N*10+i)%p,pow(n,p-2,p);d[(i-N)*a%p]+=1;c+=d[-N*a%p];n=n*10%p
else:c=sum([j+1 for j,i in enumerate(s)if i%5==0])
print(c)

Solution (Python):
n,p=map(int,input().split())
s=input().rstrip()
ans=0
l=[0]*p
a=[0,1,2,3,4,5,6,7,8,9]
c=0

if p==2 or p==5:
    for i in range(n):
        if int(s[i])%p==0:
            ans+=i+1
else:
    for i in range(n):
        
        mod=(c+a[int(s[-(i+1)])])%p
        ans+=l[mod]
        l[mod]+=1
        if mod==0:
            ans+=1
        c=mod
        
        for j in range(10):
            a[j]=a[j]*10%p
 
print(ans)

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

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

Solution (Python):
from fractions import gcd

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

if gcd(10, P) > 1:
    ans = 0
    for i in range(len(S)):
        s = int(S[i])
        if s % P == 0:
            ans += (i+1)
    print(ans)
else:
    p = [0]*P
    ans = 0
    s = 0
    for i in range(len(S)-1, -1, -1):
        s = (s + int(S[i])*pow(10, N-1-i, P)) % P
        if s == 0:
            p[s] += 1
            ans += p[s]
        else:
            ans += p[s]
            p[s] += 1

    print(ans)

Solution (Python):
from fractions import gcd

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

if gcd(10, P) > 1:
    ans = 0
    for i in range(len(S)):
        s = int(S[i])
        if s % P == 0:
            ans += (i+1)
    print(ans)
else:
    p = [0]*P
    ans = 0
    s = 0
    for i in range(len(S)-1, -1, -1):
        s = (s + int(S[i])*pow(10, N-1-i, P)) % P
        m = s % P
        if m == 0:
            p[m] += 1
            ans += p[m]
        else:
            ans += p[m]
            p[m] += 1

    print(ans)

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

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

    print(ans)
    exit()

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

print(ans)

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

if P == 2 or P == 5:
    for i in range(N):
        if S[i] % P == 0:
            count += i + 1
else:
    mod_count = [0] * P
    mod_count[0] = 1
    revS = S[::-1]

    modp = 0
    mod10 = 1

    for i in range(N):
        mod10 = (mod10 * 10) % P
        modp = (modp + mod10 * revS[i]) % P

        mod_count[modp] += 1

    for i in range(P):
        count += mod_count[i] * (mod_count[i] - 1) // 2
print(count)

Solution (Python):
import sys
n,p=map(int,input().split())
s=input()
x=[0 for i in range(p)]
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:
    tmp1=1
    tmp2=0
    for i in range(n-1,-1,-1):
        tmp2=(tmp1*int(s[i])+tmp2)%p
        x[tmp2]+=1
        tmp1=(tmp1*10)%p

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

Solution (Python):
import sys
n,p=map(int,input().split())
s=input()
x=[0 for i in range(p)]
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:
    tmp1=1
    tmp2=0
    for i in range(n-1,-1,-1):
        tmp2=(tmp1*int(s[i])+tmp2)%p
        x[tmp2]+=1
        tmp1=(tmp1*10)%p

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

Solution (Python):

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

def modinv(a, m):
    g, x, y = xgcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

n,p=map(int,input().split())
ans=0
s=list(input())
import collections
if p!=2 and p!=5:
    modlist=[0 for i in range(n+1)]
    modlist[0]=0
    modlist[1]=int(s[0])%p  
    for i in range(2,n+1):
        modlist[i]=(10*modlist[i-1]+int(s[i-1]))%p
    K=pow(10,p-2,p)
    invlist=[0 for i in range(n+1)]
    invlist[0]=1
    invlist[1]=K
    for i in range(2,n+1):
        invlist[i]=(invlist[i-1]*K)%p
    uselist=[0 for i in range(n+1)]
    for i in range(n+1):
        uselist[i]=(modlist[i]*invlist[i])%p
    ANS=dict(collections.Counter(uselist))
    for some in ANS.values():
        ans+=(some*(some-1)//2)
    print(ans)
else:
    q=0
    for i in range(n):
        q+=1
        if int(s[i])%p==0:
            ans+=q
    print(ans)

Solution (Python):
n,p = map(int,input().split())
s = list(map(int,list(input())))
ans = 0
cnt = [0]*p
cnt[0] = 1

if p == 2:
  for i in range(n):
    if s[i] in [0,2,4,6,8] :
      ans += i + 1
elif p == 5:
  for i in range(n):
    if s[i] in [0,5]:
      ans += i + 1
else:
  sum = 0
  for i in range(n):
    sum = (sum+s[n-i-1]*pow(10,i,p))%p
    cnt[sum] += 1
  for j in range(p):
    cj = cnt[j]
    ans += cj * (cj-1)//2
print(ans)

Solution (Python):

N,P=map(int,input().split())
S=input()
amari=[0 for _ in range(P)]
amari[0]=1
cnt=0
num=0
if (P==5)or(P==2):
    for i in range(N-1,-1,-1):
        
        if int(S[i])%P==0:
            cnt=cnt+i+1
else:
    for i in range(N-1,-1,-1):
        
        num=num+int(S[i])*pow(10,N-1-i,P)
        
        index=num%P
        amari[index]=amari[index]+1
    
    for i in range(P):
        cnt=cnt+(max(0,amari[i])*max(0,amari[i]-1))/2
        
print(int(cnt))

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

if p == 2 or p == 5:
    ans = 0
    s = map(int, s)
    for i, c in enumerate(s):
        if c % p == 0:
            ans += i + 1
    print(ans)
else:
    s = s[::-1]
    cnt = [0] * p
    k = 0
    cnt[k] = 1
    w = 1
    for i, c in enumerate(map(int, s)):
        k = c * w + k
        w *= 10
        while k >= p:
            k -= p
        while w >= p:
            w -= p
        cnt[k] += 1

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

Solution (Python):
import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
def resolve():
    N, P = lr()
    S = list(map(int, list(sr())))
    if P == 2 or P == 5:
        ans = 0
        for i in range(N):
            if S[i]%P == 0:
                ans += i+1
        print(ans)
        return
    S = S[::-1]
    lp = [0]*P
    c = 0
    for i in range(N):
        d = S[i]*pow(10,i,P)
        c = (c+d)%P
        lp[c] += 1
    ans = lp[0]
    for i in range(P):
        ans += lp[i]*(lp[i]-1)//2
    print(ans)
resolve()

Solution (Python):
import sys

n,p=list(map(int,input().split()))
s=sys.stdin.readline().strip()
reslst=[0]*p

cnt=0

if p==2:
    for i in range(n):
        if int(s[i])%2==0:
            cnt+=i+1
elif p==5:
    for i in range(n):
        if s[i]=='5' or s[i]=='0':
            cnt+=i+1
else:
    reslst[0]+=1
    tmp=1
    now=0
    for i in [int(x) for x in s[::-1]]:
        now+=i*tmp
        now%=p
        reslst[now]+=1
        tmp=(tmp*10)%p
    
    for i in range(p):
        cnt+=reslst[i]*(reslst[i]-1)//2

print(cnt)

Solution (Python):
N, P = map(int, input().split())
num = input().strip()
ans = 0
if P == 2:
    for idx, nu in enumerate(num):
        if nu in '24680':
            ans += idx + 1
elif P == 5:
    for idx, nu in enumerate(num):
        if nu in '50':
            ans += idx + 1
else:
    nnum = [0] * N
    base = 1
    for i in range(N-1, -1, -1):
        nnum[i] = (int(num[i]) * base) % P
        base = (base * 10) % P
    for i in range(1, N):
        nnum[i] = (nnum[i] + nnum[i-1]) % P
    dp = [0] * P
    for i in range(N):
        if nnum[i] == 0:
            ans += 1 + dp[nnum[i]]
        else:
            ans += dp[nnum[i]]
        dp[nnum[i]] += 1
print(ans)

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

mod = p
l = 100

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

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

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

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

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

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

import math

if p==2 or p==5:
    for i in range(n):
        ans += (int(s[i]) % p == 0) * (i+1)
elif math.log10(p) in [1,2,3,4]:
    print("Wrong Answer")
else:
    for i in range(n):
        v = (v + T[i]*S[i]) % p
        ans += P[v]
        P[v] += 1
        

print(ans)