Buggy python submission (verdict: Time Limit Exceeded):
# coding: utf-8

from itertools import product as prod
import sys
input = sys.stdin.readline

mod = int(1e9 + 7)

def f2(K, D):
    l = len(K)
    dp = [[[0] * D for _ in range(2)] for _ in range(l + 1)]
    dp[0][0][0] = 1
    dl = list(range(D)) * (10 // D + 2)
    for i, j, d in prod(range(l), range(2), range(D)):
        maxk = 9 if j else int(K[i])
        dpij = dp[i][j]
        dpi1 = dp[i + 1]
        for k in range(maxk + 1):
            dpi1j = dpi1[j or k < maxk]
            d_ = dl[d + k]
            dpi1j[d_] += dpij[d]
            dpi1j[d_] %= mod
    # K = 0 の場合が含まれるので -1
    return((dp[-1][0][0] + dp[-1][1][0] - 1 + mod) % mod)

K = input().rstrip() # 1 <= K <= 10^10000
D = int(input()) # 1 <= D <= 100
print(f2(K, D))


Fixed submission:
# coding: utf-8

import sys
input = sys.stdin.readline

mod = int(1e9 + 7)

def f(K, D):
    l = len(K)
    dp = [[[0] * D for _ in range(2)] for _ in range(l + 1)]
    dp[0][0][0] = 1
    for i in range(l):
        ki = int(K[i])
        for j in range(2):
            uki = 9 if j else ki
            dpij = dp[i][j]
            for d in range(D):
                for k in range(uki + 1):
                    dpij_ = dp[i + 1][j or k < ki]
                    d_ = (d + k) % D
                    dpij_[d_] += dpij[d]
                    dpij_[d_] %= mod
    # K = 0 の場合が含まれるので -1
    return((dp[-1][0][0] + dp[-1][1][0] - 1 + mod) % mod)

K = input().rstrip() # 1 <= K <= 10^10000
D = int(input()) # 1 <= D <= 100

print(f(K, D))

Buggy python submission (verdict: Time Limit Exceeded):
# coding: utf-8

from itertools import product as prod
import sys
input = sys.stdin.readline

mod = int(1e9 + 7)

def f2(K, D):
    l = len(K)
    dp = [[[0] * D for _ in range(2)] for _ in range(l + 1)]
    dp[0][0][0] = 1

    for i, j, d in prod(range(l), range(2), range(D)):
        maxk = 9 if j else int(K[i])
        dpij = dp[i][j]
        dpi1 = dp[i + 1]
        for k in range(maxk + 1):
            dpi1j = dpi1[j or k < maxk]
            d_ = (d + k) % D
            dpi1j[d_] += dpij[d]
            if dpi1j[d_] > mod:
                dpi1j[d_] -= mod
    # K = 0 の場合が含まれるので -1
    return((dp[-1][0][0] + dp[-1][1][0] - 1 + mod) % mod)

K = input().rstrip() # 1 <= K <= 10^10000
D = int(input()) # 1 <= D <= 100
print(f2(K, D))


Fixed submission:
# coding: utf-8

import sys
input = sys.stdin.readline

mod = int(1e9 + 7)

def f(K, D):
    l = len(K)
    dp = [[[0] * D for _ in range(2)] for _ in range(l + 1)]
    dp[0][0][0] = 1
    for i in range(l):
        ki = int(K[i])
        for j in range(2):
            uki = 9 if j else ki
            dpij = dp[i][j]
            for d in range(D):
                for k in range(uki + 1):
                    dpij_ = dp[i + 1][j or k < ki]
                    d_ = (d + k) % D
                    dpij_[d_] += dpij[d]
                    dpij_[d_] %= mod
    # K = 0 の場合が含まれるので -1
    return((dp[-1][0][0] + dp[-1][1][0] - 1 + mod) % mod)

K = input().rstrip() # 1 <= K <= 10^10000
D = int(input()) # 1 <= D <= 100

print(f(K, D))

Buggy python submission (verdict: Runtime Error):
# coding: utf-8

from itertools import product as prod
import sys
input = sys.stdin.readline

mod = int(1e9 + 7)

def f2(K, D):
    l = len(K)
    dp = [[[0] * D for _ in range(2)] for _ in range(l + 1)]
    dp[0][0][0] = 1

    for i, j, d in prod(range(l), range(2), range(D)):
        maxk = 9 if j else int(K[i])
        dpij = dp[i][j]
        dpi1 = dp[i + 1]
        for k in range(maxk + 1):
            dpi1j = dpi1[j or k < maxk]
            d_ = d + k
            if d_ >= D:
                d_ -= D
            dpi1j[d_] += dpij[d]
            if dpi1j[d_] >= mod:
                dpi1j[d_] -= mod
    # K = 0 の場合が含まれるので -1
    return((dp[-1][0][0] + dp[-1][1][0] - 1 + mod) % mod)

K = input().rstrip() # 1 <= K <= 10^10000
D = int(input()) # 1 <= D <= 100

print(f2(K, D))


Fixed submission:
# coding: utf-8

import sys
input = sys.stdin.readline

mod = int(1e9 + 7)

def f(K, D):
    l = len(K)
    dp = [[[0] * D for _ in range(2)] for _ in range(l + 1)]
    dp[0][0][0] = 1
    for i in range(l):
        ki = int(K[i])
        for j in range(2):
            uki = 9 if j else ki
            dpij = dp[i][j]
            for d in range(D):
                for k in range(uki + 1):
                    dpij_ = dp[i + 1][j or k < ki]
                    d_ = (d + k) % D
                    dpij_[d_] += dpij[d]
                    dpij_[d_] %= mod
    # K = 0 の場合が含まれるので -1
    return((dp[-1][0][0] + dp[-1][1][0] - 1 + mod) % mod)

K = input().rstrip() # 1 <= K <= 10^10000
D = int(input()) # 1 <= D <= 100

print(f(K, D))

Buggy python submission (verdict: Runtime Error):
# coding: utf-8

from itertools import product as prod
import sys
input = sys.stdin.readline

mod = int(1e9 + 7)

def f2(K, D):
    l = len(K)
    dp = [[[0] * D for _ in range(2)] for _ in range(l + 1)]
    dp[0][0][0] = 1

    for i, j, d in prod(range(l), range(2), range(D)):
        maxk = 9 if j else int(K[i])
        dpij = dp[i][j]
        dpi1 = dp[i + 1]
        for k in range(maxk + 1):
            dpi1j = dpi1[j or k < maxk]
            d_ = d + k
            if d_ >= D:
                d_ -= D
            dpi1j[d_] += dpij[d]
            if dpi1j[d_] >= mod:
                dpi1j[d_] -= mod
    # K = 0 の場合が含まれるので -1
    return((dp[-1][0][0] + dp[-1][1][0] - 1 + mod) % mod)

K = input().rstrip() # 1 <= K <= 10^10000
D = int(input()) # 1 <= D <= 100
print(f2(K, D))


Fixed submission:
# coding: utf-8

import sys
input = sys.stdin.readline

mod = int(1e9 + 7)

def f(K, D):
    l = len(K)
    dp = [[[0] * D for _ in range(2)] for _ in range(l + 1)]
    dp[0][0][0] = 1
    for i in range(l):
        ki = int(K[i])
        for j in range(2):
            uki = 9 if j else ki
            dpij = dp[i][j]
            for d in range(D):
                for k in range(uki + 1):
                    dpij_ = dp[i + 1][j or k < ki]
                    d_ = (d + k) % D
                    dpij_[d_] += dpij[d]
                    dpij_[d_] %= mod
    # K = 0 の場合が含まれるので -1
    return((dp[-1][0][0] + dp[-1][1][0] - 1 + mod) % mod)

K = input().rstrip() # 1 <= K <= 10^10000
D = int(input()) # 1 <= D <= 100

print(f(K, D))

Buggy python submission (verdict: Time Limit Exceeded):
# coding: utf-8

from itertools import product as prod
import sys
input = sys.stdin.readline

mod = int(1e9 + 7)

def f2(K, D):
    l = len(K)
    dp = [[[0] * D for _ in range(2)] for _ in range(l + 1)]
    dp[0][0][0] = 1

    for i, j, d in prod(range(l), range(2), range(D)):
        maxk = 9 if j else int(K[i])
        dpij = dp[i][j]
        dpi1 = dp[i + 1]
        for k in range(maxk + 1):
            dpi1j = dpi1[j or k < maxk]
            d_ = (d + k) % D
            dpi1j[d_] += dpij[d]
            dpi1j[d_] %= mod
    # K = 0 の場合が含まれるので -1
    return((dp[-1][0][0] + dp[-1][1][0] - 1 + mod) % mod)

K = input().rstrip() # 1 <= K <= 10^10000
D = int(input()) # 1 <= D <= 100

print(f2(K, D))


Fixed submission:
# coding: utf-8

import sys
input = sys.stdin.readline

mod = int(1e9 + 7)

def f(K, D):
    l = len(K)
    dp = [[[0] * D for _ in range(2)] for _ in range(l + 1)]
    dp[0][0][0] = 1
    for i in range(l):
        ki = int(K[i])
        for j in range(2):
            uki = 9 if j else ki
            dpij = dp[i][j]
            for d in range(D):
                for k in range(uki + 1):
                    dpij_ = dp[i + 1][j or k < ki]
                    d_ = (d + k) % D
                    dpij_[d_] += dpij[d]
                    dpij_[d_] %= mod
    # K = 0 の場合が含まれるので -1
    return((dp[-1][0][0] + dp[-1][1][0] - 1 + mod) % mod)

K = input().rstrip() # 1 <= K <= 10^10000
D = int(input()) # 1 <= D <= 100

print(f(K, D))

Buggy python submission (verdict: Time Limit Exceeded):
# coding: utf-8

import sys
input = sys.stdin.readline

mod = int(1e9 + 7)

def f(K, D):
    l = len(K)
    dp = [[[0] * D for _ in range(2)] for _ in range(l + 1)]
    dp[0][0][0] = 1
    for i in range(l):
        ki = int(K[i])
        for j in range(2):
            uki = 9 if j else ki
            dpij = dp[i][j]
            dpi1 = dp[i + 1]
            for d in range(D):
                for k in range(uki + 1):
                    dpi1j_ = dpi1[j or k < ki]
                    d_ = (d + k) % D
                    dpi1j_[d_] += dpij[d]
                    if dpi1j_[d_] > mod:
                        dpi1j_[d_] -= mod
    # K = 0 の場合が含まれるので -1
    return((dp[-1][0][0] + dp[-1][1][0] - 1 + mod) % mod)

K = input().rstrip() # 1 <= K <= 10^10000
D = int(input()) # 1 <= D <= 100

print(f(K, D))


Fixed submission:
# coding: utf-8

import sys
input = sys.stdin.readline

mod = int(1e9 + 7)

def f(K, D):
    l = len(K)
    dp = [[[0] * D for _ in range(2)] for _ in range(l + 1)]
    dp[0][0][0] = 1
    for i in range(l):
        ki = int(K[i])
        for j in range(2):
            uki = 9 if j else ki
            dpij = dp[i][j]
            for d in range(D):
                for k in range(uki + 1):
                    dpij_ = dp[i + 1][j or k < ki]
                    d_ = (d + k) % D
                    dpij_[d_] += dpij[d]
                    dpij_[d_] %= mod
    # K = 0 の場合が含まれるので -1
    return((dp[-1][0][0] + dp[-1][1][0] - 1 + mod) % mod)

K = input().rstrip() # 1 <= K <= 10^10000
D = int(input()) # 1 <= D <= 100

print(f(K, D))

Buggy python submission (verdict: Time Limit Exceeded):
# coding: utf-8

import sys
input = sys.stdin.readline

mod = int(1e9 + 7)

def f(K, D):
    l = len(K)
    dp = [[[0] * D for _ in range(2)] for _ in range(l + 1)]
    dp[0][0][0] = 1
    for i in range(l):
        ki = int(K[i])
        for j in range(2):
            uki = 9 if j else ki
            dpij = dp[i][j]
            for d in range(D):
                for k in range(uki + 1):
                    dpij_ = dp[i + 1][j or k < ki]
                    d_ = (d + k) % D
                    dpij_[d_] += dpij[d]
                    if dpij_[d_] > mod:
                      dpij_[d_] -= mod
    # K = 0 の場合が含まれるので -1
    return((dp[-1][0][0] + dp[-1][1][0] - 1 + mod) % mod)

K = input().rstrip() # 1 <= K <= 10^10000
D = int(input()) # 1 <= D <= 100

print(f(K, D))


Fixed submission:
# coding: utf-8

import sys
input = sys.stdin.readline

mod = int(1e9 + 7)

def f(K, D):
    l = len(K)
    dp = [[[0] * D for _ in range(2)] for _ in range(l + 1)]
    dp[0][0][0] = 1
    for i in range(l):
        ki = int(K[i])
        for j in range(2):
            uki = 9 if j else ki
            dpij = dp[i][j]
            for d in range(D):
                for k in range(uki + 1):
                    dpij_ = dp[i + 1][j or k < ki]
                    d_ = (d + k) % D
                    dpij_[d_] += dpij[d]
                    dpij_[d_] %= mod
    # K = 0 の場合が含まれるので -1
    return((dp[-1][0][0] + dp[-1][1][0] - 1 + mod) % mod)

K = input().rstrip() # 1 <= K <= 10^10000
D = int(input()) # 1 <= D <= 100

print(f(K, D))

Buggy python submission (verdict: Time Limit Exceeded):
# coding: utf-8

import sys
input = sys.stdin.readline

mod = int(1e9 + 7)

def f(K, D):
    l = len(K)
    dp = [[[0] * D for _ in range(2)] for _ in range(l + 1)]
    dp[0][0][0] = 1
    for i in range(l):
        ki = int(K[i])
        for j in range(2):
            uki = 9 if j else ki
            dpij = dp[i][j]
            for d in range(D):
                for k in range(uki + 1):
                    dpij_ = dp[i + 1][j or k < ki]
                    d_ = (d + k) % D
                    dpij_[d_] += dpij[d]
                    dpij_[d_] %= mod
    # K = 0 の場合が含まれるので -1
    return((dp[-1][0][0] + dp[-1][1][0] - 1 + mod) % mod)

K = input().rstrip() # 1 <= K <= 10^10000
D = int(input()) # 1 <= D <= 100

print(f(K, D))


Fixed submission:
# coding: utf-8

import sys
input = sys.stdin.readline

mod = int(1e9 + 7)

def f(K, D):
    l = len(K)
    dp = [[[0] * D for _ in range(2)] for _ in range(l + 1)]
    dp[0][0][0] = 1
    for i in range(l):
        ki = int(K[i])
        for j in range(2):
            uki = 9 if j else ki
            dpij = dp[i][j]
            for d in range(D):
                for k in range(uki + 1):
                    dpij_ = dp[i + 1][j or k < ki]
                    d_ = (d + k) % D
                    dpij_[d_] += dpij[d]
                    dpij_[d_] %= mod
    # K = 0 の場合が含まれるので -1
    return((dp[-1][0][0] + dp[-1][1][0] - 1 + mod) % mod)

K = input().rstrip() # 1 <= K <= 10^10000
D = int(input()) # 1 <= D <= 100

print(f(K, D))