Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict
n, p = map(int, input().split())
s = input()
s = list(map(int, s))

# dp[i][j] = (s[i]で終わる部分文字列で、pで割ったあまりがjな数の個数)
dp = [defaultdict(int), defaultdict(int)]

ans = 0
for i in range(n):
    i0, i1 = (i + 0) % 2, (i + 1) % 2

    dp[i1] = defaultdict(int)
    for j in dp[i0]:
        dp[i1][(j * 10 + s[i]) % p] += dp[i0][j]
    dp[i1][s[i] % p] += 1

    ans += dp[i1][0]
    # print(dp[i1])

print(ans)


Fixed submission:
from collections import defaultdict


def comb(n, k):
    if n < k or n < 0 or k < 0:
        return 0
    k = min(k, n - k)
    ans = 1
    for i in range(1, k + 1):
        ans *= n - i + 1
        ans //= i
    return ans


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

if p == 2:
    ans = 0
    for i in range(n):
        if int(s[i]) % 2 == 0:
            ans += i + 1
elif p == 5:
    ans = 0
    for i in range(n):
        if int(s[i]) in [0, 5]:
            ans += i + 1
else:
    mod_list = [0] * (n + 1)
    d = 1
    for i in reversed(range(n)):
        mod_list[i] = int(s[i]) * d + mod_list[i + 1]
        mod_list[i] %= p
        d = (d * 10) % p

    mod_dict = defaultdict(int)
    for i in range(n + 1):
        mod_dict[mod_list[i]] += 1

    # print(mod_list)
    # print(mod_dict)

    ans = 0
    for c in mod_dict:
        ans += comb(mod_dict[c], 2)

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict
n, p = map(int, input().split())
s = input()

# dp[i][j] = (s[i]で終わる部分文字列で、pで割ったあまりがjな数の個数)
dp = [defaultdict(int), defaultdict(int)]

ans = 0
for i in range(n):
    i0, i1 = (i + 0) % 2, (i + 1) % 2
    dp[i1] = defaultdict(int)
    for j in dp[i0]:
        dp[i1][(j * 10 + int(s[i])) % p] += dp[i0][j]
    dp[i1][int(s[i]) % p] += 1

    ans += dp[i1][0]
    # print(dp[i1])

print(ans)


Fixed submission:
from collections import defaultdict


def comb(n, k):
    if n < k or n < 0 or k < 0:
        return 0
    k = min(k, n - k)
    ans = 1
    for i in range(1, k + 1):
        ans *= n - i + 1
        ans //= i
    return ans


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

if p == 2:
    ans = 0
    for i in range(n):
        if int(s[i]) % 2 == 0:
            ans += i + 1
elif p == 5:
    ans = 0
    for i in range(n):
        if int(s[i]) in [0, 5]:
            ans += i + 1
else:
    mod_list = [0] * (n + 1)
    d = 1
    for i in reversed(range(n)):
        mod_list[i] = int(s[i]) * d + mod_list[i + 1]
        mod_list[i] %= p
        d = (d * 10) % p

    mod_dict = defaultdict(int)
    for i in range(n + 1):
        mod_dict[mod_list[i]] += 1

    # print(mod_list)
    # print(mod_dict)

    ans = 0
    for c in mod_dict:
        ans += comb(mod_dict[c], 2)

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n, p = map(int, input().split())
s = input()

# dp[i][j] = (s[i]で終わる部分文字列で、pで割ったあまりがjな数の個数)
dp = [[0] * p for _ in range(2)]

ans = 0
for i in range(n):
    i0, i1 = (i + 0) % 2, (i + 1) % 2
    dp[i1] = [0] * p
    for j in range(p):
        dp[i1][(j * 10 + int(s[i])) % p] += dp[i0][j]
    dp[i1][int(s[i]) % p] += 1

    ans += dp[i1][0]
    # print(dp[i1])

print(ans)


Fixed submission:
from collections import defaultdict


def comb(n, k):
    if n < k or n < 0 or k < 0:
        return 0
    k = min(k, n - k)
    ans = 1
    for i in range(1, k + 1):
        ans *= n - i + 1
        ans //= i
    return ans


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

if p == 2:
    ans = 0
    for i in range(n):
        if int(s[i]) % 2 == 0:
            ans += i + 1
elif p == 5:
    ans = 0
    for i in range(n):
        if int(s[i]) in [0, 5]:
            ans += i + 1
else:
    mod_list = [0] * (n + 1)
    d = 1
    for i in reversed(range(n)):
        mod_list[i] = int(s[i]) * d + mod_list[i + 1]
        mod_list[i] %= p
        d = (d * 10) % p

    mod_dict = defaultdict(int)
    for i in range(n + 1):
        mod_dict[mod_list[i]] += 1

    # print(mod_list)
    # print(mod_dict)

    ans = 0
    for c in mod_dict:
        ans += comb(mod_dict[c], 2)

print(ans)