Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**8)

K = input()
N = len(K)
D = int(input())
MOD = 10 ** 9 + 7

memo = [[[-1 for k in range(2)] for j in range(D)] for i in range(N)]

def f(digit, current_sum, flag):
    if digit == -1:
        if current_sum % D == 0:
            return 1
        else:
            return 0

    #if memo[digit][current_sum][flag] != -1:
    #    return memo[digit][current_sum][flag]

    ret = 0
    for i in range(10):
        if flag or i < int(K[N-1-digit]):
            if memo[digit-1][(current_sum+i)%D][1] != -1:
                ret += memo[digit-1][(current_sum+i)%D][1]
            else:
                ret += f(digit-1, (current_sum+i)%D, 1)
        elif i == int(K[N-1-digit]):
            if memo[digit-1][(current_sum+i)%D][0] != -1:
                ret += memo[digit-1][(current_sum+i)%D][0]
            else:
                ret += f(digit-1, (current_sum+i)%D, 0)
        
    memo[digit][current_sum][flag] = ret % MOD
    return ret

#substract 0 case
ans = (f(N-1, 0, 0) - 1) % MOD
print(ans)


Fixed submission:
K = input()
N = len(K)
D = int(input())
MOD = 10 ** 9 + 7

dp = [[[0 for k in range(2)] for j in range(D)] for i in range(N+1)]

dp[0][0][0] = 1
for i, n in enumerate(K):
    n = int(n)
    for j in range(D):
        for k in range(2):
            for d in range(10 if k else n+1):
                dp[i+1][(j+d) % D][k or d < n] += dp[i][j][k]
                dp[i+1][(j+d) % D][k or d < n] %= MOD

print((dp[N][0][0] + dp[N][0][1] - 1) % MOD)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**8)

K = input()
N = len(K)
D = int(input())
MOD = 10 ** 9 + 7

memo = [[[-1 for k in range(2)] for j in range(D)] for i in range(N)]

def f(digit, current_sum, flag):
    if digit == -1:
        if current_sum % D == 0:
            return 1
        else:
            return 0

    if memo[digit][current_sum][flag] != -1:
        return memo[digit][current_sum][flag]

    ret = 0
    for i in range(10):
        if flag or i < int(K[N-1-digit]):
            ret += f(digit-1, (current_sum+i)%D, 1)
            ret %= MOD
        elif i == int(K[N-1-digit]):
            ret += f(digit-1, (current_sum+i)%D, 0)
            ret %= MOD

    memo[digit][current_sum][flag] = ret
    return ret

#substract 0 case
ans = (f(N-1, 0, 0) - 1) % MOD
print(ans)


Fixed submission:
K = input()
N = len(K)
D = int(input())
MOD = 10 ** 9 + 7

dp = [[[0 for k in range(2)] for j in range(D)] for i in range(N+1)]

dp[0][0][0] = 1
for i, n in enumerate(K):
    n = int(n)
    for j in range(D):
        for k in range(2):
            for d in range(10 if k else n+1):
                dp[i+1][(j+d) % D][k or d < n] += dp[i][j][k]
                dp[i+1][(j+d) % D][k or d < n] %= MOD

print((dp[N][0][0] + dp[N][0][1] - 1) % MOD)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**8)

K = input()
N = len(K)
D = int(input())
MOD = 10 ** 9 + 7

memo = [[[-1 for k in range(2)] for j in range(D)] for i in range(N)]

def f(digit, current_sum, flag):
    if digit == -1:
        if current_sum % D == 0:
            return 1
        else:
            return 0

    if memo[digit][current_sum][flag] != -1:
        return memo[digit][current_sum][flag]

    ret = 0
    for i in range(10):
        if flag or i < int(K[N-1-digit]):
            ret += f(digit-1, (current_sum+i)%D, 1)
            ret %= MOD
        elif i == int(K[N-1-digit]):
            ret += f(digit-1, (current_sum+i)%D, 0)
            ret %= MOD

    memo[digit][current_sum][flag] = ret
    return ret

#substract 0 case
ans = (f(N-1, 0, 0) - 1) % MOD
print(ans)


Fixed submission:
K = input()
N = len(K)
D = int(input())
MOD = 10 ** 9 + 7

dp = [[[0 for k in range(2)] for j in range(D)] for i in range(N+1)]

dp[0][0][0] = 1
for i, n in enumerate(K):
    n = int(n)
    for j in range(D):
        for k in range(2):
            for d in range(10 if k else n+1):
                dp[i+1][(j+d) % D][k or d < n] += dp[i][j][k]
                dp[i+1][(j+d) % D][k or d < n] %= MOD

print((dp[N][0][0] + dp[N][0][1] - 1) % MOD)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**8)
from functools import lru_cache

K = input()
N = len(K)
D = int(input())
MOD = 10 ** 9 + 7

@lru_cache(maxsize=10000000)
def f(digit, current_sum, flag):
    if digit == -1:
        if current_sum % D == 0:
            return 1
        else:
            return 0

    ret = 0
    for i in range(10):
        if flag or i < int(K[N-1-digit]):
            ret += f(digit-1, (current_sum+i)%D, 1)
        elif i == int(K[N-1-digit]):
            ret += f(digit-1, (current_sum+i)%D, 0)
    
    return ret % MOD

#substract 0 case
ans = (f(N-1, 0, 0) - 1) % MOD
print(ans)


Fixed submission:
K = input()
N = len(K)
D = int(input())
MOD = 10 ** 9 + 7

dp = [[[0 for k in range(2)] for j in range(D)] for i in range(N+1)]

dp[0][0][0] = 1
for i, n in enumerate(K):
    n = int(n)
    for j in range(D):
        for k in range(2):
            for d in range(10 if k else n+1):
                dp[i+1][(j+d) % D][k or d < n] += dp[i][j][k]
                dp[i+1][(j+d) % D][k or d < n] %= MOD

print((dp[N][0][0] + dp[N][0][1] - 1) % MOD)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**7)

K = input()
N = len(K)
D = int(input())
MOD = 10 ** 9 + 7

memo = [[[[-1 for l in range(2)] for k in range(2)] for j in range(D)] for i in range(N)]

def f(digit, current_sum, flagX, flagY): #flagX upper bound, flagY lower bound
    if digit == -1:
        if flagY and current_sum % D == 0:
            return 1
        else:
            return 0

    if memo[digit][current_sum][flagX][flagY] != -1:
        return memo[digit][current_sum][flagX][flagY]

    ret = 0
    for i in range(10):
        if flagX:
            ret += f(digit-1, (current_sum+i)%D, flagX, flagY or (1 if i >= 1 else 0))
        elif i == int(K[N-1-digit]):
            ret += f(digit-1, (current_sum+i)%D, 0, flagY or (1 if i >= 1 else 0))
        elif i < int(K[N-1-digit]):
            ret += f(digit-1, (current_sum+i)%D, 1, flagY or (1 if i >= 1 else 0))
            
    memo[digit][current_sum][flagX][flagY] = ret % MOD
    return ret

print(f(N-1, 0, 0, 0) % MOD)


Fixed submission:
K = input()
N = len(K)
D = int(input())
MOD = 10 ** 9 + 7

dp = [[[0 for k in range(2)] for j in range(D)] for i in range(N+1)]

dp[0][0][0] = 1
for i, n in enumerate(K):
    n = int(n)
    for j in range(D):
        for k in range(2):
            for d in range(10 if k else n+1):
                dp[i+1][(j+d) % D][k or d < n] += dp[i][j][k]
                dp[i+1][(j+d) % D][k or d < n] %= MOD

print((dp[N][0][0] + dp[N][0][1] - 1) % MOD)