Problem:
 Score : 100 points    Problem Statement Find the number of integers between 1 and K (inclusive) satisfying the following condition, modulo 10^9 + 7 :   The sum of the digits in base ten is a multiple of D .       Constraints  All values in input are integers.  1 \leq K < 10^{10000}  1 \leq D \leq 100         Input Input is given from Standard Input in the following format:  K  D       Output Print the number of integers satisfying the condition, modulo 10^9 + 7 .        Sample Input 1 30
4      Sample Output 1 6  Those six integers are: 4, 8, 13, 17, 22 and 26 .       Sample Input 2 1000000009
1      Sample Output 2 2  Be sure to print the number modulo 10^9 + 7 .       Sample Input 3 98765432109876543210
58      Sample Output 3 635270834

Solution (Python):
from itertools import accumulate

k = input()
d = int(input())
dp = [0] * (d + 10)
dp2 = 0
MOD = 10 ** 9 + 7
for c in k:
    c = int(c)
    for e in range(d - 1, -1, -1):
        dp[e + 10] -= dp[e]
    dp[dp2] += 1
    dp[dp2 + c] -= 1
    dp = list(accumulate(dp))
    for e in range(9, -1, -1):
        dp[e] += dp[d + e]
        dp[d + e] = 0
    for e in range(d):
        dp[e] %= MOD
    dp2 = (dp2 + c) % d
ans = dp[0] - 1
if dp2 == 0:
    ans += 1
print(ans % MOD)

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

S = [[0, 0] for i in range(D)]
S[0][0] = 1
for i in range(N):
    c = int(K[i])
    T = [[0, 0] for i in range(D)]
    for d in range(D):
        w0, w1 = S[d]
        w0 %= MOD
        w = S[d][0] % MOD
        for v in range(c):
            T[(d+v)%D][1] += w0
        T[(d+c)%D][0] += w0

        w1 %= MOD
        for v in range(10):
            T[(d+v)%D][1] += w1
    S = T
print((sum(S[0])-1) % MOD)

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


MOD = 10**9 + 7
K = [int(elem) for elem in fin()[:-1]]
D = int(fin())

dp = [[0] * 2 for _ in range(D)]
dp[0][1] = 1

for bound in K:
    next_dp = [[0] * 2 for _ in range(D)]
    for num in range(10):
        for d in range(D):
            next_reminder = (num + d) % D
            if num < bound:
                next_dp[next_reminder][0] += (dp[d][0] + dp[d][1])
            elif num == bound:
                next_dp[next_reminder][0] += dp[d][0]
                next_dp[next_reminder][1] += dp[d][1]
            else:
                next_dp[next_reminder][0] += dp[d][0]
            next_dp[next_reminder][0] %= MOD
            next_dp[next_reminder][1] %= MOD
    
    dp = next_dp

res = dp[0][0] + dp[0][1] - 1
print(res) if res >= 0 else print(res + MOD)

Solution (Python):
a = input()
dd = int(input())
mod = 10**9 + 7
n = len(a)
dp = [[[0 for j in range(dd)] for k in range(2)] for i in range(n+1)]
dp[0][0][0] = 1
for i in range(n):
  for j in range(2):
    for k in range(dd):
      lim = 9 if j else int(a[i]) - 0
      for d in range(lim+1):
        dp[i+1][(j or d) <lim][(k+d)%dd] += dp[i][j][k]
        dp[i+1][(j or d) <lim][(k+d)%dd] %= mod
ans = 0
for j in range(2):
  ans += dp[n][j][0]
print((ans-1)%mod)

Solution (Python):
N=input()
D=int(input())

s = len(N)
mod=10**9+7

dp=[[[0]*(s+1) for i in range(D)] for i in range(2)]
dp[0][0][0]=1
for i in range(s):
    for j in range(D):
        for k in range(10):
            dp[1][(j+k)%D][i+1]+=dp[1][j][i]
            dp[1][(j+k)%D][i+1]%=mod
        for k in range(int(N[i])):
            dp[1][(j+k)%D][i+1]+=dp[0][j][i]
            dp[1][(j+k)%D][i+1]%=mod
        dp[0][(j+int(N[i]))%D][i+1]+=dp[0][j][i]
        dp[0][(j+int(N[i]))%D][i+1]%=mod
print((dp[0][0][s]+dp[1][0][s]-1)%mod)