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):
def examA():
    N = I()
    H = LI()
    dp = [inf]*(N)
    dp[0] = 0
    for i in range(N-1):
        dp[i+1] = min(dp[i+1],dp[i]+abs(H[i+1]-H[i]))
        if i<N-2:
            dp[i + 2] = min(dp[i + 2], dp[i]+abs(H[i + 2] - H[i]))
    ans = dp[-1]
    print(ans)
    return

def examB():
    N, K = LI()
    H = LI()
    dp = [inf]*N
    dp[0] = 0
    for i in range(N):
        for k in range(1,K+1):
            if i+k>=N:
                break
            if dp[i+k]>dp[i]+abs(H[i+k]-H[i]):
                dp[i+k] = dp[i]+abs(H[i+k]-H[i])
    ans = dp[-1]
    print(ans)
    return

def examC():
    N = I()
    A = [0]*N; B = [0]*N; C = [0]*N
    for i in range(N):
        A[i],B[i],C[i] = LI()
    dp = [[0]*3 for _ in range(N+1)]
    for i in range(N):
        dp[i+1][0] = max(dp[i][1],dp[i][2]) + A[i]
        dp[i + 1][1] = max(dp[i][0], dp[i][2]) + B[i]
        dp[i + 1][2] = max(dp[i][1], dp[i][0]) + C[i]
    ans = max(dp[N])
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    
    S = SI(); N = len(S)
    T = SI(); M = len(T)
    dp = [[0] * (M + 1) for _ in range(N + 1)]
    for i in range(N):
        for j in range(M):
            if S[i] == T[j]:
                dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + 1)
            dp[i+1][j+1] = max(dp[i+1][j+1], dp[i+1][j], dp[i][j+1])

    i = N; j = M
    ans = []
    while i > 0 and j > 0:
        if dp[i][j] == dp[i-1][j]:
            i -= 1
        elif dp[i][j] == dp[i][j-1]:
            j -= 1
        else:
            ans.append(S[i-1])
            i -= 1
            j -= 1
    print("".join(ans[::-1]))
    return

def examG():
    
    
    def topological_sort(n,outs,ins):
        q = deque(v1 for v1 in range(n) if ins[v1] == 0)
        res = []
        while q:
            v1 = q.popleft()
            res.append(v1)
            for v2 in outs[v1]:
                ins[v2] -= 1
                if ins[v2] == 0:
                    q.append(v2)
        return res
    N, M = LI()
    V = [[]for _ in range(N)]
    start = [0]*N
    for _ in range(M):
        x,y = LI()
        x -= 1; y -= 1
        V[x].append(y)
        start[y] += 1
    Order = topological_sort(N, V, start)

    dp = [0]*N
    for i in Order:
        for v in V[i]:
            dp[v] = max(dp[v],dp[i]+1)
    ans = max(dp)
    print(ans)
    return

def examH():
    H, W = LI()
    A = [SI() for _ in range(H)]
    dp = [[0]*W for _ in range(H)]
    dp[0][0] = 1
    for i in range(H):
        for j in range(W):
            if A[i][j]=="
                continue
            dp[i][j] %=mod
            if i+1<H and dp[i+1][j]!="
                dp[i+1][j] +=dp[i][j]
            if j+1<W and dp[i][j+1]!="
                dp[i][j+1] +=dp[i][j]
    ans = dp[-1][-1]
    print(ans)
    return

def examI():
    N = I()
    P = LFI()
    dp = [[0]*(N+1) for _ in range(N+1)]
    dp[0][0] = 1
    for i in range(N):
        for j in range(i+1):
            dp[i+1][j+1] += dp[i][j]*P[i]
            dp[i+1][j] += dp[i][j]*(1-P[i])
    ans = 0
    for v in dp[N][(1+N//2):]:
        ans += v
    print(ans)
    return

def examJ():
    N = I()
    A = LI()
    dp = [[[0]*(N+1) for _ in range(N+1)]for _ in range(N+1)]
    S = Counter(A)
    print(S)
    dp[S[1]][S[2]][S[3]] = 0
    que = deque()
    que.append((S[1],S[2],S[3]))
    used = defaultdict(set)
    while(que):
        n1,n2,n3 = que.popleft()
        if used[(n1,n2,n3)]:
            continue
        used[(n1,n2,n3)] = True
        now = n1+n2+n3
        if n1>0:
            dp[n1-1][n2][n3] += dp[n1][n2][n3] + N/now * n1/now
            que.append((n1-1, n2, n3))
        if n2>0:
            dp[n1+1][n2-1][n3] += dp[n1][n2][n3] + N/now * n2/now
            que.append((n1+1,n2-1,n3))
        if n3>0:
            dp[n1][n2+1][n3-1] += dp[n1][n2][n3] + N/now * n3/now
            que.append((n1,n2+1,n3-1))

    ans = dp[0][0][0]
    print(ans)
    return

def examK():
    N, K = LI()
    A = LI()
    dp = [-1]*(K+1)
    for i in range(1,K+1):
        flag = False
        for a in A:
            if a>i:
                break
            if dp[i-a]==-1:
                flag = True
                break
        if flag:
            dp[i] = 1

    ans = dp[K]
    if ans==1:
        print("First")
    else:
        print("Second")
    return

def examM():
    N, K = LI()
    A = LI()
    dp = [[0]*(K+1) for _ in range(N+1)]
    dp[0][0] = 1
    for i in range(N):
        cum = [0]*(K+1)
        cum[0] = dp[i][0]
        for c in range(K):
            cum[c+1] = cum[c] + dp[i][c+1]
        for j in range(K+1):
            if j<=A[i]:
                dp[i+1][j] = cum[j]
            else:
                dp[i+1][j] = cum[j] - cum[j-A[i]-1]
            dp[i+1][j] %=mod

    ans = dp[N][K]%mod
    print(ans)
    return

def examN():
    N = I()
    A = LI()
    cumA = [0]*(N+1)
    for i in range(N):
        cumA[i+1] = cumA[i]+A[i]
    dp = [[inf]*(N) for _ in range(N)]
    for i in range(N):
        dp[0][i] = 0
    for i in range(N-1):
        for j in range(N-i-1):
            for k in range(i+1):
                cur = dp[i-k][j+k+1]+dp[k][j]+cumA[i+j+2]-cumA[j]
                dp[i+1][j] = min(dp[i+1][j],cur)

    ans = dp[N-1][0]
    print(ans)
    return

def examO():
    N = I()
    A = [LI() for _ in range(N)]
    loop = 2**N
    dp = [[0]*loop for _ in range(N+1)]
    dp[0][0] = 1
    for mask in range(loop):
        cur = 0
        for j in range(N):
            if mask&(1<<j)==(1<<j):
                cur +=1
        for i in range(N):
            if mask&(1<<i)==0 and A[i][cur]==1:
                dp[cur+1][mask|(1<<i)] += dp[cur][mask]
                dp[cur + 1][mask | (1 << i)] %=mod

    ans = dp[N][loop-1]
    print(ans)
    return

def examP():
    def dfs_dp(n,s,fords,visited):
        W = 1; B = 1
        visited[s] = True
        for v in fords[s]:
            if visited[v]:
                continue
            cur = dfs_dp(n, v, fords,visited)
            W *= sum(cur)
            B *= cur[0]
            W %= mod
            B %= mod

        return (W,B)
    N = I()
    V = [[]for _ in range(N)]
    for _ in range(N-1):
        x,y = LI()
        x -=1; y -=1
        V[x].append(y)
        V[y].append(x)
    visited = [False]*N
    ans = dfs_dp(N,0,V,visited)
    print(sum(ans)%mod)
    return

def examQ():
    N = I()
    H = LI()
    maxH = max(H)
    A = LI()
    dp = [0](maxH+1)
    cur = 0
    for i in range(N):
        dp[B[i]] = cur+dp[A[i]]
    return

def examR():
    def list_dot(A1,A2):
        res = [[0]*len(A2) for _ in range(len(A1))]
        for i in range(len(A1)):
            for j in range(len(A2)):
                cur = 0
                for k in range(len(A1[0])):
                    cur += A1[i][k]*A2[k][j]
                res[i][j] = cur%mod
        return res
    N, K = LI()
    A = [LI() for _ in range(N)]
    now = [[1]*N]
    while(K>0):
        if K%2==1:
            now = list_dot(now,A)
        K //=2
        A = list_dot(A,A)
    ans = 0
    for i in now:
        for k in i:
            ans += k
            ans %= mod
    print(ans)
    return

def examS():
    class ModInt:
        def __init__(self, x):
            self.x = x % MOD

        def __str__(self):
            return str(self.x)

        __repr__ = __str__

        def __add__(self, other):
            return (
                ModInt(self.x + other.x) if isinstance(other, ModInt) else
                ModInt(self.x + other)
            )

        def __sub__(self, other):
            return (
                ModInt(self.x - other.x) if isinstance(other, ModInt) else
                ModInt(self.x - other)
            )

        def __mul__(self, other):
            return (
                ModInt(self.x * other.x) if isinstance(other, ModInt) else
                ModInt(self.x * other)
            )

        def __truediv__(self, other):
            return (
                ModInt(
                    self.x * pow(other.x, MOD - 2, MOD)
                ) if isinstance(other, ModInt) else
                ModInt(self.x * pow(other, MOD - 2, MOD))
            )

        def __pow__(self, other):
            return (
                ModInt(pow(self.x, other.x, MOD)) if isinstance(other, ModInt) else
                ModInt(pow(self.x, other, MOD))
            )

        __radd__ = __add__

        def __rsub__(self, other):
            return (
                ModInt(other.x - self.x) if isinstance(other, ModInt) else
                ModInt(other - self.x)
            )

        __rmul__ = __mul__

        def __rtruediv__(self, other):
            return (
                ModInt(
                    other.x * pow(self.x, MOD - 2, MOD)
                ) if isinstance(other, ModInt) else
                ModInt(other * pow(self.x, MOD - 2, MOD))
            )
        def __rpow__(self, other):
            return (
                ModInt(pow(other.x, self.x, MOD)) if isinstance(other, ModInt) else
                ModInt(pow(other, self.x, MOD))
            )
    def ketadp(a,D):
        n = len(a)
        dp = [[[ModInt(0)]*D for _ in range(2)] for _ in range(n+1)]
        dp[0][0][0] = 1
        for i, less, hasD in itertools.product(range(n), (0, 1), range(D)):
            max_d = 9 if less else int(a[i])
            for d in range(max_d + 1):
                less_ = less or d < max_d
                hasD_ = (hasD + d)%D
                dp[i + 1][less_][hasD_] += dp[i][less][hasD]

        ans = sum(dp[n][less][0] for less in (0, 1))
        return ans
    K = SI()
    D = I()
    ans = ketadp(K,D)
    ans = ans-1
    print(ans)
    return

def examT():
    return

def examU():
    N = I()
    A = [LI() for _ in range(N)]
    mask = 2**N
    cst = [0]*mask
    for i in range(mask):
        cur = 0
        for j in range(N):
            for k in range(j+1,N):
                if i&(1<<j)==(1<<j) and i&(1<<k)==(1<<k):
                    cur += A[j][k]
        cst[i] = cur
    dp = [0]*mask
    for m in range(mask):
        maskT = m
        while(maskT > 0):
            cur = dp[m-maskT] + cst[maskT]
            dp[m] = max(dp[m], cur)

            
            maskT = (maskT - 1) & m

    ans = dp[-1]
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LFI(): return list(map(float,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,MOD
mod = 10**9 + 7
mod2 = 998244353
MOD = mod
inf = 10**18
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**6)

if __name__ == '__main__':
    examS()

"""

"""

Solution (Python):
k = input()
d = int(input())

MOD = 10**9 + 7

k_len = len(k)
dp = [[0] * d for _ in range(k_len)]
dp[0][0] = 1









for i in range(1, k_len):
    for j in range(10):
        dp[i][0] += dp[i-1][(0-j)%d]
    dp[i][0] = dp[i][0] % MOD
    for j in range(1,d):
        dp[i][j] = (dp[i][j-1] + dp[i-1][j] - dp[i-1][(j-10)%d]) % MOD

ans = 0
heads = 0
for i in range(k_len):
    pick = int(k[i])
    for j in range(pick):
        ans += dp[k_len - 1 - i][(0 - j - heads) % d]
        ans = ans % MOD
    heads += pick

if(heads % d == 0):
    ans += 1

print((ans - 1)%MOD)

Solution (Python):
K = input()
N = len(K)
D = int(input())
Y = [0] * D
P = 10**9+7
a = 0
for i in range(N):
    nY = [0] * D
    c = int(K[i])
    for j in range(10):
        if j < c:
            nk = (j+a) % D
            nY[nk] = (nY[nk] + 1) % P

        for k in range(D):
            nk = (j+k) % D
            nY[nk] = (nY[nk] + Y[k]) % P
        
    a = (a+c) % D
    Y = nY
print((Y[0] - 1 + (a==0)) % P)

Solution (Python):
k = int(input())
d = int(input())

li = list(map(int,(list(str(k)))))
leng = len(li)
mod = 10**9+7

dp1 = [0 for _ in range(d)]
dp2 = [0 for _ in range(d)]

mm1 = li[0]
for i in range(mm1):
    dp2[i%d] += 1

for i in range(1,leng):
    for j in range(0,10):
        for l in range(d):
            
            dp1[(l+j)%d] += dp2[l]
            dp1[(l+j)%d] %= mod

        
        if j<li[i]:
            dp1[(mm1+j)%d] += 1
            dp1[(mm1+j)%d] %= mod
    
    mm1 = (mm1+li[i])%d
    dp2 = [dp1[i] for i in range(d)]
    dp1 = [0 for _ in range(d)]
dp2[sum(li)%d]+=1
print((dp2[0]-1)%mod)

Solution (Python):











import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,hypot,log 
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')

class ModInt:
    def __init__(self, x):
        self.x = x % mod
    
    def __str__(self):
        return str(self.x)
    
    __repr__ = __str__

    def __add__(self, other):
        if isinstance(other, ModInt):
            return ModInt(self.x + other.x)
        else:
            return ModInt(self.x + other)

    __radd__ = __add__
        
    def __sub__(self, other):
        if isinstance(other, ModInt):
            return ModInt(self.x - other.x)
        else:
            return ModInt(self.x - other)

    def __rsub__(self, other):
        if isinstance(other, ModInt):
            return ModInt(other.x - self.x)
        else:
            return ModInt(other - self.x)

    def __mul__(self, other):
        if isinstance(other, ModInt):
            return ModInt(self.x * other.x)
        else:
            return ModInt(self.x * other)

    __rmul__ = __mul__

    def __truediv__(self, other):
        if isinstance(other, ModInt):
            return ModInt(self.x * pow(other.x, mod-2,mod))
        else:
            return ModInt(self.x * pow(other, mod - 2, mod))
            
    def __rtruediv(self, other):
        if isinstance(other, self):
            return ModInt(other * pow(self.x, mod - 2, mod))
        else:
            return ModInt(other.x * pow(self.x, mod - 2, mod))
            

    def __pow__(self, other):
        if isinstance(other, ModInt):
            return ModInt(pow(self.x, other.x, mod))
        else:
            return ModInt(pow(self.x, other, mod))
            

    def __rpow__(self, other):
        if isinstance(other, ModInt):
            return ModInt(pow(other.x, self.x, mod))
        else:
            return ModInt(pow(other, self.x, mod))

def main():
    K=[int(i) for i in ST()]
    D=I()
    N=len(K)
    dp = [[[ModInt(0)]*D for _ in range(2)] for _ in range(N+1)] 

    dp[0][0][0]+=1
    for i in range(N):
        for less in range(2):
            limit = 10 if less else K[i]+1
            for d in range(D):
                for j in range(limit):
                    if less or j!=limit-1:
                        dp[i+1][1][(d+j)%D] += dp[i][less][d]
                    else:
                        dp[i+1][0][(d+j)%D] += dp[i][less][d]
    print(dp[-1][0][0] + dp[-1][1][0] - 1) 


if __name__ == '__main__':
    main()

Solution (Python):
K, = map(int, input().split())
D, = map(int, input().split())
N = len(str(K))
M = 10**9+7
dp = [[0]*D for _ in range(N+1)]
dp2 = [[0]*D for _ in range(N+1)]
dp[0][0] = 1
dp2[0][0] = 1
for i in range(1, N+1):
    Ki = K%10
    K //= 10
    for j in range(D):
        for k in range(10):
            dp[i][(j+k)%D] += dp[i-1][j]
            dp[i][(j+k)%D] %= M
        for k in range(Ki):
            dp2[i][(j+k)%D] += dp[i-1][j]
            dp2[i][(j+k)%D] %= M
        dp2[i][(j+Ki)%D] += dp2[i-1][j]
        dp2[i][(j+Ki)%D] %= M
print((dp2[N][0]-1)%M)

Solution (Python):
K, = map(int, input().split())
D, = map(int, input().split())
N = len(str(K))
M = 10**9+7
dp = [[0]*D for _ in range(N+1)]
dp2 = [[0]*D for _ in range(N+1)]
dp[0][0] = 1
dp2[0][0] = 1
for i in range(1, N+1):
    Ki = K%10
    K //= 10
    for j in range(D):
        for k in range(10):
            dp[i][(j+k)%D] = (dp[i][(j+k)%D] + dp[i-1][j])%M
        for k in range(Ki):
            dp2[i][(j+k)%D] = (dp2[i][(j+k)%D] + dp[i-1][j])%M
        dp2[i][(j+Ki)%D] = (dp2[i][(j+Ki)%D] + dp2[i-1][j])%M
print((dp2[N][0]-1)%M)

Solution (Python):
K, = map(int, input().split())
D, = map(int, input().split())
N = len(str(K))
M = 10**9+7
dp = [[0]*D for _ in range(N+1)]
dp2 = [[0]*D for _ in range(N+1)]
dp[0][0] = 1
dp2[0][0] = 1
for i in range(1, N+1):
    Ki = K%10
    K //= 10
    for j in range(D):
        for k in range(10):
            dp[i][(j+k)%D] += dp[i-1][j]
            dp[i][(j+k)%D] %= M
        for k in range(Ki):
            dp2[i][(j+k)%D] += dp[i-1][j]
            dp2[i][(j+k)%D] %= M
        dp2[i][(j+Ki)%D] += dp2[i-1][j]
        dp2[i][(j+Ki)%D] %= M
print((dp2[N][0]-1)%M)

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

mod = 10**9+7
N = len(K)
dp0 = [[0]*D for _ in range(N)]
dp1 = [[0]*D for _ in range(N)]

for k in range(int(K[0])):
    dp1[0][k%D] += 1
dp0[0][int(K[0])%D] += 1

for i in range(N-1):
    for j in range(D):
        for k in range(10):
            dp1[i+1][(j+k)%D] += dp1[i][j]
            dp1[i+1][(j+k)%D] %= mod
        for k in range(int(K[i+1])):
            dp1[i+1][(j+k)%D] += dp0[i][j]
            dp1[i+1][(j+k)%D] %= mod
        dp0[i+1][(j+int(K[i+1]))%D] += dp0[i][j]
        dp0[i+1][(j+int(K[i+1]))%D] %= mod

print((dp1[N-1][0]+dp0[N-1][0]-1)%mod)

Solution (Python):
mod = 10**9+7
k = input()
d = int(input())

l = len(k)

dp = [[0 for _ in range(d)] for _ in range(l+1)]
dp2 = [[0 for _ in range(d)] for _ in range(l+1)]

dp[0][0] = 1
dp2[0][0] = 1

for i in range(1, l+1):
    if i == 1:
        for p in range(10):
            if p > int(k[i-1]):
                continue
            for j in range(d):
                if p < int(k[i-1]):
                    dp[i][(j+p) % d] += dp[i-1][j]
                    dp[i][(j+p) % d] %= mod
                elif p == int(k[i-1]):
                    dp2[i][(j+p) % d] += dp2[i-1][j]
                    dp2[i][(j+p) % d] %= mod
        continue

    for p in range(10):
        for j in range(d):
            dp[i][(j+p) % d] += dp[i-1][j]
            dp[i][(j+p) % d] %= mod

        if p > int(k[i-1]):
            continue

        for j in range(d):
            if p < int(k[i-1]):
                dp[i][(j+p) % d] += dp2[i-1][j]
                dp[i][(j+p) % d] %= mod
            elif p == int(k[i-1]):
                dp2[i][(j+p) % d] += dp2[i-1][j]
                dp2[i][(j+p) % d] %= mod

print((dp[l][0]+dp2[l][0]-1) % mod)

Solution (Python):

import sys
INF = float("inf")

MOD = 1000000007  


def array(*args, initial=0):
    def forstr(N):
        return "[{} for _ in range("+str(N)+")]"

    a = args[-1]
    ans = eval(forstr(a).format(initial))
    if len(args) == 1:
        return ans
    else:
        return array(*args[:-1], initial=ans)


def solve(K: int, D: int):
    K = str(K)
    N = len(str(K))
    DP = array(N+1, 2, D, initial=0)
    DP[0][0][0] = 1
    for i in range(N):
        for j in range(2):
            lim = 9 if j else int(K[i])
            for k in range(D):
                for d in range(lim+1):
                    DP[i+1][j or d < lim][(k+d) % D] += DP[i][j][k]
                    DP[i+1][j or d < lim][(k+d) % D] %= MOD
    print((DP[N][0][0]+DP[N][1][0]-1) % MOD)

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    K = int(next(tokens))  
    D = int(next(tokens))  
    solve(K, D)


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    K = input()
    D = int(input())
    L = len(K)
    dp = [[[0, 0] for _ in range(D)] for _ in range(L+1)]
    mod = 10 ** 9 + 7
    dp[0][0][1] = 1
    for i in range(L):
        d = int(K[i])
        for j in range(D):
            for k in range(10):
                dp[i+1][(j + k) % D][0] += dp[i][j][0]
                dp[i+1][(j + k) % D][0] %= mod
                if k < d:
                    dp[i+1][(j + k) % D][0] += dp[i][j][1]
                    dp[i+1][(j + k) % D][0] %= mod
                elif k == d:
                    dp[i+1][(j + k) % D][1] += dp[i][j][1]
                    dp[i+1][(j + k) % D][1] %= mod
    print((sum(dp[-1][0]) + mod - 1) % mod)



if __name__ == '__main__':
    main()

Solution (Python):
import numpy as np
k=input()
d=int(input())
m=10**9+7
t=np.zeros(d)
s=0
for i in k:
    p=np.zeros(d)
    for j in range(10):
        p+=np.hstack([t[-(j%d):],t[:-(j%d)]])
    for j in range(int(i)):
        p[(s+j)%d]+=1
    t=p[::]%m
    s+=int(i)
t[s%d]+=1
print((int(t[0])-1)%m)

Solution (Python):
k = input()
len_k = len(k)
d = int(input())
MOD = 10**9 + 7

dp = [[[0]*d for i in range(len_k+1)] for i in range(2)]
dp[1][0][0] = 1

for i in range(len_k):
    for j in range(d):
        dp[1][i+1][(j+int(k[i])) % d] += dp[1][i][j]
        dp[1][i+1][(j+int(k[i])) % d] %= MOD
        for l in range(int(k[i])):
            dp[0][i+1][(j+l) % d] += dp[1][i][j]
            dp[0][i+1][(j+l) % d] %= MOD
        for l in range(10):
            dp[0][i+1][(j+l) % d] += dp[0][i][j]
            dp[0][i+1][(j+l) % d] %= MOD

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

Solution (Python):
K = int(input())
D = int(input())
mod = 10**9 + 7

dp = [[[0] * D for _ in range(2)] for _ in range(len(str(K))+1)]
dp[0][0][0] = 1

for i in range(len(str(K))):
    N = int(str(K)[i])
    for j in range(2):
        for k in range(D):
            for n in range((9 if j == 1 else N) + 1):
                dp[i+1][j or n < N][(k+n%D)%D] += dp[i][j][k]%mod

print((dp[-1][0][0]+dp[-1][1][0]-1)%mod)

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

dp0 = [[0] * D for _ in range(N+1)]
dp1 = [[0] * D for _ in range(N+1)]
dp0[0][0] = 1
for i in range(N):
    k = int(K[i])
    for j in range(D):
        dp0[i+1][(j+k)%D] = (dp0[i+1][(j+k)%D] + dp0[i][j]) % mod
        dp1[i+1][(j+k)%D] = (dp1[i+1][(j+k)%D] + dp1[i][j]) % mod
        for k_ in range(k):
            dp1[i+1][(j+k_)%D] = (dp1[i+1][(j+k_)%D] + dp0[i][j] + dp1[i][j]) % mod
        for k_ in range(k+1, 10):
            dp1[i + 1][(j + k_) % D] = (dp1[i + 1][(j + k_) % D] + dp1[i][j]) % mod

print((dp0[-1][0] + dp1[-1][0] - 1) % mod)

Solution (Python):
import sys
from math import log10, floor
K = input()
d = int(input())
digit_num = len(K)
MOD = 10**9+7

memo_ls = [[[0 for _k in range(2)] for j in range(d)] for i in range(digit_num + 1)]
memo_ls[0][0][0] = 1
dic = {j : j % d for j in range(10)}
for i, n in enumerate(K, 1):
    n = int(n)
    for j in range(10):
        for k in range(d):
            _from = (k - j) % d
            memo_ls[i][k][1] = (memo_ls[i][k][1] + memo_ls[i-1][_from][1]) % MOD
            if j == n:
                memo_ls[i][k][0] = (memo_ls[i-1][_from][0] + memo_ls[i][k][0]) % MOD
            elif j < n:
                memo_ls[i][k][1] = (memo_ls[i-1][_from][0] + memo_ls[i][k][1]) % MOD
print((sum(memo_ls[digit_num][0]) - 1) % MOD)

Solution (Python):
modulo = 10 ** 9 + 7

k = str(input())
digits = len(k)
d = int(input())

matrix = []

for i in range(10005):
    matrix.append([[0, 0] for j in range(d)])
    
matrix[0][0][1] = 1

for i, digit in enumerate(k):
    digit = int(digit)
    
    
    for j in range(d):
        
        for k in range(10):
            aux = (j - k) % d
            matrix[i+1][j][0] = (matrix[i+1][j][0] + matrix[i][aux][0]) % modulo
        aux = (j - digit) % d
        matrix[i+1][j][1] = matrix[i+1][j][1] + matrix[i][aux][1]
        
        for k in range(digit):
            aux = (j - k) % d
            matrix[i+1][j][0] = (matrix[i+1][j][0] + matrix[i][aux][1]) % modulo
            
result = (matrix[digits][0][0] + matrix[digits][0][1] - 1) % modulo
print(result, end='\n')

Solution (Python):
MOD=1000000007
K=input()
n=len(K)
D=int(input())

dp=[[[0,0] for j in range(D)] for i in range(10005)]
dp[0][0][1]=1

for i in range(n):
    num = int(K[i])
    for j in range(D):
        for k in range(10):
            dp[i+1][j][0]+=dp[i][(j-k)%D][0]
            dp[i+1][j][0]%=MOD
        dp[i+1][j][1]+= dp[i][(j-num)%D][1]
        for k in range(num):
            dp[i+1][j][0]+=dp[i][(j-k)%D][1]
            dp[i+1][j][0]%=MOD
print((dp[n][0][0]+dp[n][0][1]-1)%MOD)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    md = 10 ** 9 + 7
    k = [int(c) for c in input()]
    n=len(k)
    d = int(input())
    dp = [[0] * d for _ in range(n)]
    for b in range(k[0]):
        dp[0][b % d] += 1
    border = k[0]
    dpi = dp[0]
    for i, a in enumerate(k[1:], 1):
        dpi1 = dpi
        dpi = dp[i]
        for j in range(d):
            pre = dpi1[j]
            if pre == 0: continue
            for b in range(10):
                nj = (j + b) % d
                dpi[nj] = (dpi[nj] + pre) % md
        for b in range(a):
            nj = (border + b) % d
            dpi[nj] += 1
        border = (border + a) % d

    
    ans = dp[n-1][0] - 1 + (border % d == 0)
    print(ans % md)

main()

Solution (Python):
mod = 10**9+7
K = input()
n = len(K)
D = int(input())
dp = [[[0]*2 for i in range(D)] for _ in range(n)]
for i in range(int(K[0])):
    dp[0][i%D][0] += 1
dp[0][int(K[0])%D][1] += 1
for i in range(n-1):
    for j in range(D):
        for d in range(10):
            dp[i+1][(j+d)%D][0]+=dp[i][j][0]
            dp[i+1][(j+d)%D][0]%=mod
        for d in range(int(K[i+1])):
            dp[i+1][(j+d)%D][0]+=dp[i][j][1]
            dp[i+1][(j+d)%D][0]%=mod
        dp[i+1][(j+int(K[i+1]))%D][1] += dp[i][j][1]
        dp[i+1][(j+int(K[i+1]))%D][1]%=mod
print((dp[-1][0][0]+dp[-1][0][1]-1)%mod)

Solution (Python):
K = int(input())
D = int(input())
mod = 10**9 + 7

dp = [[[0] * D for _ in range(2)] for _ in range(len(str(K))+1)]
dp[0][0][0] = 1

for i in range(len(str(K))):
    N = int(str(K)[i])
    for j in range(2):
        for k in range(D):
            for n in range((9 if j == 1 else N) + 1):
                dp[i+1][j or n < N][(k+n%D)%D] += dp[i][j][k]%mod

print((dp[-1][0][0]+dp[-1][1][0]-1)%mod)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np
import itertools

K = list(map(int,readline().rstrip().decode('utf-8')))
D = int(read())

MOD = 10**9 + 7

Kcum = list(itertools.accumulate(K))

x = np.zeros(D,np.int64)
x[0] = 1
answer = 0
for kc,k in zip(Kcum[::-1],K[::-1]):
    for i in range(kc-k,kc):
        rest = (-i)%D
        answer += x[rest]
    y = np.zeros(D+10,np.int64)
    y[:D] = x
    y[10:] -= x
    np.cumsum(y,out=y) 
    for d in range(D,D+10):
        y[d%D] += y[d]
    x = y[:D] % MOD

answer -= 1 
if Kcum[-1]%D==0:
    answer += 1

answer %= MOD
print(answer)

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    k=input()
    d=int(input())
    n=len(k)
    dp=[[[0]*2 for _ in range(d)] for _ in range(n+1)]
    dp[0][0][0]=1
    for i in range(n):
        a=int(k[i])
        for j in range(d):
            for o in range(10):
                dp[i+1][(j+o)%d][1]+=dp[i][j][1]
                dp[i+1][(j+o)%d][1]%=MOD
                if(o<a):
                    dp[i+1][(j+o)%d][1]+=dp[i][j][0]
                    dp[i+1][(j+o)%d][1]%=MOD
                elif(o==a):
                    dp[i+1][(j+o)%d][0]+=dp[i][j][0]
                    dp[i+1][(j+o)%d][0]%=MOD
    print((dp[n][0][0]+dp[n][0][1]-1)%MOD)
resolve()

Solution (Python):

from itertools import accumulate

mod=1000000007


k=input()
d=int(input())
dp=[0]*(d+10)
dp2=0

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
def ketadp3(a, b):
    L = len(a)

    dp = [[[0 for i in range(2)] for j in range(b)] for k in range(L + 1)]
    dp[0][0][0] = 1
    for i in range(L):
        D = int(a[i])
        for k in range(b):
            for j in range(2):
                for d in range(10 if j else D+1):
                    dp[i + 1][(k + d) % b][j or (d < D)] += dp[i][k][j]
                    dp[i + 1][(k + d) % b][j or (d < D)] %= MOD

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


def main():
    n = input()
    d = int(input())
    ketadp3(n, d)


if __name__ == '__main__':
    main()

Solution (Python):
K = input()
D = int(input())
dp = [[0] * D for _ in range(len(K))]
mod = 10 ** 9 + 7


for i in range(int(K[0])):
  dp[0][i % D] += 1



tight = int(K[0]) % D
if len(K) > 1:
  for i in range(len(K) - 1):
    for j in range(D):
      for k in range(10):
        dp[i + 1][(j + k) % D] += dp[i][j]
        dp[i + 1][(j + k) % D] %= mod
    
    for k in range(int(K[i + 1])):
      dp[i + 1][(tight + k) % D] += 1
    
    tight = (tight + int(K[i + 1])) % D

print((dp[len(K) - 1][0] + (tight == 0) - 1) % mod)

Solution (Python):
mod = 10**9+7
K = input()
D = int(input())
N = len(K)
dp = [[0] * D for i in range(N)]
for i in range(int(K[0])):
    dp[0][i%D] += 1
tight = int(K[0])%D
for i in range(1, N):
    for j in range(D):
        for k in range(10):
            dp[i][j] += dp[i-1][(j-k)%D]
            dp[i][j] %= mod
    for k in range(int(K[i])):
        dp[i][(tight+k)%D] += 1
    tight = (tight+int(K[i]))%D
print((dp[N-1][0]+(tight==0)-1)%mod)