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):
N = [int(n) for n in list(input())]
d = int(input())
p = 10**9+7
DP = [[0]*d, [0]*d]
DP[1][0] = 1
for n in N:
    DP_ = [[0]*d, [0]*d]
    for i in range(2):
        for j in range(d):
            for k in range(n+i):
                DP_[i][j] += DP[1][(j-k) % d] % p
            for k in range(n+i, 10):
                DP_[i][j] += DP[0][(j-k) % d] % p
            DP_[i][j] %= p
    DP = DP_
print((DP[1][0] + p - 1) % p)

Solution (Python):

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    K=list(input())
    D=I()
    N=len(K)
    
    
    dpt=[[0]*D for _ in range(N+1)]
    dpl=[[0]*D for _ in range(N+1)]
    
    start=int(K[0])
    
    
    dpt[0][0]=1
            
    
    now=0
    
    for i in range(N):
        num=(int(K[i]))
        
        dpt[i+1][(now+num)%D]=1
        for k in range(num):
            dpl[i+1][(now+k)%D]+=1
        now=(now+num)%D
                    
        
        
        S=0
        for j in range(10):
            S+=dpl[i][j%D]
            
        for j in range(D):
            dpl[i+1][(j+9)%D]+=S
            dpl[i+1][(j+9)%D]%=mod
            S+=dpl[i][(j+10)%D]-dpl[i][j%D]
        
                
    
    print((dpt[-1][0]+dpl[-1][0]-1)%mod)
    
    
            
    
    

main()

Solution (Python):

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    K=input()
    D=I()
    N=len(str(K))
    
    
    dpt=[[0]*D for _ in range(N+1)]
    dpl=[[0]*D for _ in range(N+1)]
    
    start=int(K[0])
    
    
    dpt[0][0]=1
            
    
    now=0
    
    for i in range(N):
        num=(int(K[i]))
        
        dpt[i+1][(now+num)%D]=1
        for k in range(num):
            dpl[i+1][(now+k)%D]+=1
        now=(now+num)%D
                    
        
        
        S=0
        for j in range(10):
            S+=dpl[i][j%D]
            
        for j in range(D):
            dpl[i+1][(j+9)%D]+=S
            dpl[i+1][(j+9)%D]%=mod
            S+=dpl[i][(j+10)%D]-dpl[i][j%D]
        
                
    
    print((dpt[-1][0]+dpl[-1][0]-1)%mod)
    
    
            
    
    

main()

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

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


for digit in range(int(len(str(K)))):
    for smaller_flg in [0,1]:
        lim = 9 if smaller_flg else int(str(K)[digit])
        for digit_num in range(lim+1):
            new_smaller_flg = smaller_flg or digit_num < lim
            for mod_d in range(D):
                new_mod_d = (mod_d + digit_num)%D
                dp[digit+1][new_smaller_flg][new_mod_d] += dp[digit][smaller_flg][mod_d]
                dp[digit+1][new_smaller_flg][new_mod_d] %= MOD

print((dp[int(len(str(K)))][1][0] + dp[int(len(str(K)))][0][0] - 1) % MOD)

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

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

for digit in range(int(len(str(K)))):
    for smaller_flg in [0,1]:
        lim = 9 if smaller_flg else int(str(K)[digit])
        for digit_num in range(lim+1):
            new_smaller_flg = smaller_flg or digit_num < lim
            for mod_d in range(D):
                new_mod_d = (mod_d + digit_num)%D
                dp[new_smaller_flg][new_mod_d][digit+1] += dp[smaller_flg][mod_d][digit]
                dp[new_smaller_flg][new_mod_d][digit+1] %= MOD

print((dp[1][0][int(len(str(K)))] + dp[0][0][int(len(str(K)))] - 1) % MOD)

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

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

for digit in range(int(len(str(K)))):
    for smaller_flg in [0,1]:
        lim = 9 if smaller_flg else int(str(K)[digit])
        for digit_num in range(lim+1):
            new_smaller_flg = smaller_flg or digit_num < lim
            for mod_d in range(D):
                new_mod_d = (mod_d + digit_num)%D
                dp[digit+1][new_smaller_flg][new_mod_d] += dp[digit][smaller_flg][mod_d]
                dp[digit+1][new_smaller_flg][new_mod_d] %= MOD

print((dp[int(len(str(K)))][1][0] + dp[int(len(str(K)))][0][0] - 1) % MOD)

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

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

dp[N][0][0]=1
dp[N][0][1]=1

for _ in range(0,N):
    i=N-_-1
    for j in range(0,D):
        ans=0
        for k in range(0,10):
            ans+=dp[i+1][(j+k)%D][0]

        dp[i][j][0]=ans%mod

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

        ans+=dp[i+1][(j+int(K[i]))%D][1]

        dp[i][j][1]=ans%mod

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

Solution (Python):
n = int(input())
d = int(input())
p = 10**9+7
if d == 1:
    print(n % p)
    exit()
N = [int(i) for i in list(str(n))]
DP0 = [0] * d
DP1 = [0] * d
DP1[0] += 1
for i in N:
    DP0_ = [0] * d
    DP1_ = [0] * d
    for r in range(d):
        for j in range(i):
            DP0_[r] += DP1[(r-j) % d]
            DP1_[r] += DP1[(r-j) % d]
        DP0_[r] += DP0[(r-i) % d]
        DP1_[r] += DP1[(r-i) % d]
        for j in range(i+1, 10):
            DP0_[r] += DP0[(r-j) % d]
            DP1_[r] += DP0[(r-j) % d]
        DP0_[r], DP1_[r] = DP0_[r] % p, DP1_[r] % p
    DP0, DP1 = DP0_, DP1_
print((DP1[0]-1+p) % p)

Solution (Python):
n = int(input())
d = int(input())
p = 10**9+7
if d == 1:
    print(n % p)
    exit()
N = [int(i) for i in list(str(n))]
DP0 = [0] * d
DP1 = [0] * d
DP1[0] += 1
for i in N:
    DP0_ = [0] * d
    DP1_ = [0] * d
    for r in range(d):
        for j in range(i):
            DP0_[r] += DP1[(r-j) % d]
            DP1_[r] += DP1[(r-j) % d]
        DP0_[r] += DP0[(r-i) % d]
        DP1_[r] += DP1[(r-i) % d]
        for j in range(i+1, 10):
            DP0_[r] += DP0[(r-j) % d]
            DP1_[r] += DP0[(r-j) % d]
        DP0_[r], DP1_[r] = DP0_[r] % p, DP1_[r] % p
    DP0, DP1 = DP0_, DP1_
print((DP1[0]-1) % p)

Solution (Python):
n = int(input())
d = int(input())
p = 10**9+7
if d == 1:
    print(n % p)
    exit()
N = [int(i) for i in list(str(n))]
DP0 = [0] * d
DP1 = [0] * d
DP1[0] += 1
for i in N:
    DP0_ = [0] * d
    DP1_ = [0] * d
    for r in range(d):
        for j in range(i):
            DP0_[r] += DP1[(r-j) % d]
            DP1_[r] += DP1[(r-j) % d]
        DP0_[r] += DP0[(r-i) % d]
        DP1_[r] += DP1[(r-i) % d]
        for j in range(i+1, 10):
            DP0_[r] += DP0[(r-j) % d]
            DP1_[r] += DP0[(r-j) % d]
        DP0_[r], DP1_[r] = DP0_[r] % p, DP1_[r] % p
    DP0, DP1 = DP0_, DP1_
print((DP1[0]-1+p) % p)

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

mod = 10 ** 9 + 7

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

for i in k:
    i = int(i)
    dp2 = [[0] * d for _ in range(2)]

    for j in range(d):
        dp2[1][(j + i) % d] += dp[1][j]

    for j in range(d):
        for k in range(i):
            dp2[0][(j + k) % d] += dp[1][j]

    for j in range(d):
        for k in range(10):
            dp2[0][(j + k) % d] += dp[0][j]

    dp = [[j % mod for j in k] for k in dp2]

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

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

mod = 10**9+7

s = str(K)

dp = [[[0, 0] for _ in range(D)] for _ in range(n+1)]
dp[0][0][0] = 1

for i in range(n):
    for j in range(D):
        for k in range(2):
            nd = int(s[i])
            for d in range(10):
                ni = i+1
                nj = (j+d)%D
                nk = k
                if k == 0:
                    if d > nd:
                        continue
                    elif d < nd:
                        nk = 1
                    else:
                        pass
                dp[ni][nj][nk] += dp[i][j][k]%mod
print((dp[n][0][0]+dp[n][0][1]-1)%mod)

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

dp = [[[0,0] for _ in range(D)] for _ in range(L+1)]
dp[0][0][0] = 1
for i,c in enumerate(K):
    c = int(c)
    for x in range(D):
        for d in range(10):
            y = (x+d)%D
            dp[i+1][y][1] += dp[i][x][1]
            dp[i+1][y][1] %= MOD
            if d > c: continue
            dp[i+1][y][int(d<c)] += dp[i][x][0]
            dp[i+1][y][int(d<c)] %= MOD
print((sum(dp[-1][0]) - 1) % MOD)

Solution (Python):
K = input()
d = int(input())
mod = 10**9+7
n = len(K)
dp = [[[0 for k in range(2)] for i in range(d)] for j in range(n+1)]
dp[0][0][0] = 1
for i in range(1,n+1):
  s = int(K[i-1])
  for j in range(d):
    for k in range(10):
      r = (j+k)%d
      dp[i][r][1] += dp[i-1][j][1]
      if k < s:
        dp[i][r][1] += dp[i-1][j][0]
      dp[i][r][1] %= mod
    dp[i][(j+s)%d][0] = dp[i-1][j][0]
print((sum(dp[n][0])-1)%mod)

Solution (Python):
s,d=input(),int(input())
n=[int(i) for i in s]
l=len(s)
mod=10**9+7
dp=[[[0]*d,[0]*d] for i in range(l+1)]
dp[0][0][0]=1
for i in range(l):
    for smaller in range(2):
        for j in range(d):
            for x in range(10 if smaller else n[i]+1):
                dp[i+1][smaller or x<n[i]][(j+x)%d] += dp[i][smaller][j]
                dp[i+1][smaller or x<n[i]][(j+x)%d]%=mod
print((dp[l][0][0]+dp[l][1][0]-1)%mod)

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

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

for i in range(l):
    for j in range(D):
        nd = int(K[i])
        for d in range(10):
            dp[i+1][1][(j+d)%D] += dp[i][1][j%D]%MOD 
            if d < nd:
                dp[i+1][1][(j+d)%D] += dp[i][0][j%D]%MOD 
        dp[i+1][0][(j+int(K[i]))%D] += dp[i][0][j%D]%MOD 


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

Solution (Python):
import sys


def main():
    K = input()
    D = int(input())
    MOD = 10**9+7
    
    dp = [[0]*D for _ in range(2)]
    dp[1][0] = 1
    n = 0
    for st in K:
        num = int(st)
        n += num
        use = [0]*D
        for i in range(D):
            for j in range(10):
                use[(i+j)%D] += dp[0][i]
            if num != 0:
                for j in range(num):
                    use[(i+j)%D] += dp[1][i]
        dp[0] = use
        for i in range(D):
            dp[0][i] %= MOD
        dp[1] = [0]*D
        dp[1][n%D] += 1
    
    print((dp[0][0]+dp[1][0]-1)%MOD)

if __name__ == "__main__":
    main()

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

N = len(K)

MOD = 10 ** 9 + 7










dp0 = [[0] * D for _ in range(N + 1)]
dp1 = [0] * (N + 1)

for i in range(N):
    next_ = int(K[i])
    tmp = dp1[i]

    dp1[i + 1] = (tmp + next_) % D
    
    for j in range(next_):
        dp0[i + 1][(tmp + j) % D] += 1
    
    for j in range(D):
        for k in range(10):
            dp0[i + 1][(j + k) % D] += dp0[i][j]
    
    for j in range(D):
        dp0[i + 1][j] %= MOD








ans = dp0[N][0] - 1
if dp1[N] == 0:
    ans += 1

print (ans % MOD)

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

def main():
    kk = list(input())
    klen = len(kk)-1
    n = 10000
    k = [0]*n
    for i in range(klen-1,-1,-1):
        k[-(klen-i)] = int(kk[i])

    d = int(input())
    mod = 10**9 + 7

    
    
    dp1 = [[0]*d for i in range(n+1)]
    dp2 = [[0]*d for i in range(n+1)]

    dp1[0][0] = 1

    for i in range(n):
        for j in range(d):
            for r in range(10):
                if r < k[i]:
                    dp2[i+1][(j+r)%d] = (dp2[i+1][(j+r)%d] + dp1[i][j] + dp2[i][j])%mod
                elif r == k[i]:
                    dp1[i+1][(j+r)%d] = (dp1[i+1][(j+r)%d] + dp1[i][j])%mod
                    dp2[i+1][(j+r)%d] = (dp2[i+1][(j+r)%d] + dp2[i][j])%mod
                else:
                    dp2[i+1][(j+r)%d] = (dp2[i+1][(j+r)%d] + dp2[i][j])%mod



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

if __name__ == "__main__":
    main()

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

S = list(map(int, input()))
N = len(S)
D = INT()


dp0 = list2d(N+1, D, 0)
dp1 = list2d(N+1, D, 0)
dp0[0][0] = 1
for i, a in enumerate(S):
    for j in range(D):
        if not dp0[i][j] and not dp1[i][j]:
            continue
        for k in range(10):
            if k < a:
                dp1[i+1][(j+k)%D] += dp0[i][j]
                dp1[i+1][(j+k)%D] += dp1[i][j]
            elif k == a:
                dp0[i+1][(j+k)%D] += dp0[i][j]
                dp1[i+1][(j+k)%D] += dp1[i][j]
            else:
                dp1[i+1][(j+k)%D] += dp1[i][j]
        dp0[i+1][j] %= MOD
        dp1[i+1][j] %= MOD
ans = (dp0[N][0] + dp1[N][0] - 1) % MOD
print(ans)

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

dp=[0]*D
mod=10**9+7
s=0
for i in range(len(K)):
  ndp=[0]*D
  
  for j in range(D):
    for d in range(10):
      ndp[(j+d)%D]=(ndp[(j+d)%D]+dp[j])%mod
  
  for d in range(int(K[i])):
    ndp[(s+d)%D]+=1 
  dp=ndp
  s=(s+int(K[i]))%D

ans=dp[0]-1
if s%D==0:
  ans+=1
print(ans%mod)

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

dp=[0]*D
mod=10**9+7
s=0
for i in range(len(K)):
  ndp=[0]*D
  
  for j in range(D):
    for d in range(10):
      ndp[(j+d)%D]=(ndp[(j+d)%D]+dp[j])%mod
  
  for d in range(int(K[i])):
    ndp[(s+d)%D]+=1 
  dp=ndp
  s=(s+int(K[i]))%D
print((dp[0]-1+(s==0))%mod)

Solution (Python):
from collections import Counter


def slv(K, D):
    rl = Counter()
    r = Counter()
    rl[0] = 1

    M = 10**9 + 7
    for c in K:
        d = int(c)
        rln = Counter()
        rn = Counter()
        for rem, count in rl.items():
            rln[(rem + d) % D] += count
            rln[(rem + d) % D] %= M

        for rem, count in rl.items():
            for i in range(d):
                rn[(rem + i) % D] += count
                rn[(rem + i) % D] %= M
        for rem, count in r.items():
            for i in range(10):
                rn[(rem + i) % D] += count
                rn[(rem + i) % D] %= M
        rl = rln
        r = rn
    return (rl[0] + r[0] - 1) % M


K = input()
D = int(input())
print(slv(K, D))

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


def main():
    n = int(readline())
    m = int(readline())
    mod = 10**9 + 7
    n = str(n)
    n_len = len(n)
    dp = [[[0 for _ in range(m)] for _ in range(2)] for _ in range(n_len + 1)]
    dp[0][0][0] = 1

    for i in range(n_len):
        n_n = int(n[i])
        for j in range(2):
            for k in range(m):
                for d in range(10):
                    if j == 1 or (j == 0 and d < n_n):
                        j_n = 1
                    elif d == n_n:
                        j_n = 0
                    else:
                        continue
                    k_n = (k + d % m) % m
                    dp[i + 1][j_n][k_n] += dp[i][j][k] % mod
    print((dp[-1][0][0] + dp[-1][1][0] - 1) % mod)


if __name__ == "__main__":
    main()

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

DP = [[[0 for _ in range(d)] for _ in range(2)] for _ in range(len(k)+1)]
DP[0][0][0] = 1

for i in range(len(k)):
    now = int(k[i])
    for j in range(2):
        for mod in range(d):
            for n in range(10):
                
                if j==1 or (j==0 and n < now):
                    next_j = 1
                
                elif n == now:
                    next_j = 0
                
                else: 
                    continue

                n_mod = n % d
                next_mod = (mod + n_mod) % d
                DP[i+1][next_j][next_mod] = (DP[i+1][next_j][next_mod] + DP[i][j][mod]) % (10**9+7)

ans = (DP[len(k)][0][0] + DP[len(k)][1][0] -1) % (10**9+7)
print(ans)

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

nums = [int(v) for v in string]
length = len(string) - 1
k = int(string)

M = 10**9 + 7
def mod(v):
    if v >= M:
        return v % M
    return v

dp = [[[None] * 2 for _ in range(d)] for _ in range(length + 2)]
def dfs(i=0, s=0, border=True):
    if dp[i][s][border] is not None:
        return dp[i][s][border]

    if i > length:
        r = int(not bool(s))
        dp[i][s][border] = r
        return r

    cnt = 0
    for n in range(max(9 * (not border), nums[i]) + 1):
        cnt = mod(cnt + dfs(i + 1, (s + n) % d, border and nums[i] == n))
    dp[i][s][border] = cnt
    return cnt


for i in reversed(range(length + 2)):
    for s in reversed(range(d)):
        for border in [False, True]:
            if i > length:
                dp[i][s][border] = int(not bool(s))
                continue

            cnt = 0
            for n in range(max(9 * (not border), nums[i]) + 1):
                cnt = mod(cnt + dp[i + 1][(s + n) % d][border and nums[i] == n])
            dp[i][s][border] = cnt

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

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

DP = [[[0 for _ in range(d)] for _ in range(2)] for _ in range(len(k)+1)]
DP[0][0][0] = 1

for i in range(len(k)):
    now = int(k[i])
    for j in range(2):
        for mod in range(d):
            for n in range(10):
                
                if j==1 or (j==0 and n < now):
                    next_j = 1
                
                elif n == now:
                    next_j = 0
                
                else: 
                    continue

                n_mod = n % d
                next_mod = (mod + n_mod) % d
                DP[i+1][next_j][next_mod] = (DP[i+1][next_j][next_mod] + DP[i][j][mod]) % (10**9+7)

ans = (DP[len(k)][0][0] + DP[len(k)][1][0] -1) % (10**9+7)
print(ans)

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

Solution (Python):
k = list(map(int, list(input())))
n = len(k)
d = int(input())
dp = [[[0]*d for _ in range(2)] for _ in range(n+1)]
dp[0][0][0] = 1
mod = 10**9 + 7
for s in (0,1):
  for i in range(n):
    for j in range(10 if s else k[i]+1):
      for m in range(d):
        dp[i+1][s|(j<k[i])][(m+j)%d] = (dp[i+1][s|(j<k[i])][(m+j)%d] + dp[i][s][m]) % mod
print((dp[n][0][0] + dp[n][1][0] - 1) % mod)

Solution (Python):
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=1000000007
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  s=S()
  n=len(s)
  _d=I()


  dp=[[[0]*(_d+1) for _ in range(2)]for __ in range(n+1)]
  dp[0][0][0]=1

  for i in range(n):
    nd=int(s[i])
    for j in range(2):
      for k in range(_d):
        for d in range(10):

          ni=i+1
          nj=j
          nk=k

          if nj==0:
            if d>nd:
              continue
            if d<nd:
              nj=1

          nk+=d
          nk%=_d

          dp[ni][nj][nk]+=dp[i][j][k]
          dp[ni][nj][nk]%=mod

  return (dp[n][0][0]+dp[n][1][0]-1)%mod


print(main())

Solution (Python):
mod=10**9+7
k=input()
d=int(input())
l=[int(i) for i in "0"+k]
dp=[[[0]*(d+2),[0]*(d+2)] for _ in "ww"]
dp[0][0][0]=1

for i,j in enumerate(l):
    if i==0: continue
    for p in range(d+1):
        if dp[i%2-1][0][p]:
            dp[i%2][0][[(p+j)%d,d][(p+j)%d==0]]=1
            for q in range(j):
                dp[i%2][1][[[(p+q)%d,d][(p+q)%d==0],0][p==q==0]]+=1
        if dp[i%2-1][1][p]:
            for q in range(10):
                dp[i%2][1][[[(p+q)%d,d][(p+q)%d==0],0][p==q==0]]+=dp[i%2-1][1][p]
    for p in range(d+2):
        dp[i%2-1][0][p]=0
        dp[i%2-1][1][p]=0
        dp[i%2][0][p]%=mod
        dp[i%2][1][p]%=mod

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

Solution (Python):
MOD = 10**9 + 7
K = input()
D = int(input())
N = len(K)
dp0 = [[0] * D for _ in range(N+1)]
dp1 = [[0] * D for _ in range(N+1)]
dp0[0][0] = 1
for i, digit in enumerate(K, 1):
    digit = int(digit)
    for d in range(D):
        for k in range(10):
            dp1[i][(d + k) % D] += dp1[i-1][d]
            dp1[i][(d + k) % D] %= MOD
            if k < digit:
                dp1[i][(d + k) % D] += dp0[i-1][d]
                dp1[i][(d + k) % D] %= MOD
            elif k == digit:
                dp0[i][(d + k) % D] += dp0[i-1][d]
                dp0[i][(d + k) % D] %= MOD
print((dp0[N][0] + dp1[N][0] - 1) % MOD)

Solution (Python):

import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

K = list(map(int,input())); n = len(K)
D = int(input())
dp = [[[0]*D for i in range(2)] for j in range(n+1)]
dp[0][0][0] = 1
for i in range(n):
  for p in range(D):
    dp[i+1][0][p] = dp[i][0][(p-K[i])%D] % mod
    tmp = 0
    for l in range(K[i]):
      tmp += dp[i][0][(p-l)%D]
    for l in range(10):
      tmp += dp[i][1][(p-l)%D]
    dp[i+1][1][p] = tmp % mod
print((dp[n][0][0] + dp[n][1][0] -1) % mod)

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

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

for i, s in enumerate(K):
    a = ord(s)-48
    for j in range(D):
        for k in range(10):
            b = (j+k)%D
            dp[i+1][1][b] += dp[i][1][j]
            if k<a:
                dp[i+1][1][b] += dp[i][0][j]
            dp[i+1][1][b] %= mod
    
    for j in range(D):
        b = (j+a)%D
        dp[i+1][0][b] += dp[i][0][j]
        dp[i+1][0][b] %= mod

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

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

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

for i in range(N):
    a = ord(K[i])-48
    for j in range(D):
        for k in range(10):
            b = (j+k)%D
            dp[i+1][1][b] += dp[i][1][j]
            if k<a:
                dp[i+1][1][b] += dp[i][0][j]
            dp[i+1][1][b] %= mod
    
    for j in range(D):
        b = (j+a)%D
        dp[i+1][0][b] += dp[i][0][j]
        dp[i+1][0][b] %= mod

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

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

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

for i in range(N):
    a = ord(K[i])-48
    for j in range(D):
        for k in range(10):
            b = (j+k)%D
            dp[i+1][1][b] += dp[i][1][j]
            dp[i+1][1][b] %= mod

            if k<a:
                dp[i+1][1][b] += dp[i][0][j]
                dp[i+1][1][b] %= mod
    
    for j in range(D):
        b = (j+a)%D
        dp[i+1][0][b] += dp[i][0][j]
        dp[i+1][0][b] %= mod

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

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

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

for i in range(N):
    a = ord(K[i])-48
    
    for j in range(D):
        for k in range(10):
            dp[i+1][1][(j+k)%D] += dp[i][1][j]
            dp[i+1][1][(j+k)%D] %= mod

    for j in range(D):
        dp[i+1][0][(j+a)%D] += dp[i][0][j]
        dp[i+1][0][(j+a)%D] %= mod

    for j in range(D):
        for k in range(a):
            dp[i+1][1][(j+k)%D] += dp[i][0][j]
            dp[i+1][1][(j+k)%D] %= mod

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

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

dp = [[[0] * 2 for _ in range(d)] for i in range(l+1)]
dp[0][0][0] = 1
 
for i in range(l):
    lim = int(k[i])
    for j in range(d):
        for num in range(10):
            dp[i+1][(j+num) % d][1] = (dp[i+1][(j+num) % d][1] + dp[i][j][1]) % mod
        for num in range(lim):
            dp[i+1][(j+num) % d][1] = (dp[i+1][(j+num) % d][1] + dp[i][j][0]) % mod
        
        dp[i+1][(j+lim) % d][0] = (dp[i+1][(j+lim) % d][0] + dp[i][j][0]) % mod
                
ans = (dp[l][0][0] + dp[l][0][1] + mod - 1) % mod
 
print(ans)

Solution (Python):
n=input()
d=int(input())
m=len(n)
mod=10**9+7

DP=[[[0]*d for _ in range(2)] for _ in range(m+1)]
DP[0][0][0]=1

for i in range(1,m+1):
    for flag in range(2):
        num=9 if flag else int(n[i-1])
        for j in range(d):
            for k in range(num+1):
                DP[i][flag or k<num][(j+k)%d] +=DP[i-1][flag][j]
                DP[i][flag or k<num][(j+k)%d] %=mod

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

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

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

for i in range(L):
    nd = int(K[i])
    for j in range(D):
        for k in range(2):
            
            for d in range(10):
                nk = k
                if k == 0:
                    if d > nd:
                        continue
                    if d < nd:
                        nk = 1
                dp[i+1][(j+d) % D][nk] += dp[i][j][k]
                dp[i+1][(j+d) % D][nk] %= mod

ans = (dp[L][0][0]+dp[L][0][1]-1+mod) % mod



print(ans)

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

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

for i in range(L):
    nd = int(K[i])
    for j in range(D):
        for k in range(2):
            
            for d in range(10):
                nk = k
                if k == 0:
                    if d > nd:
                        continue
                    if d < nd:
                        nk = 1
                dp[i+1][(j+d) % D][nk] += dp[i][j][k]
                dp[i+1][(j+d) % D][nk] %= mod

ans = (dp[L][0][0]+dp[L][0][1]-1+mod) % mod



print(ans)

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

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

for i in range(L):
    nd = int(K[i])
    for j in range(D):
        for k in range(2):
            
            for d in range(10):
                nk = k
                if k == 0:
                    if d > nd:
                        continue
                    if d < nd:
                        nk = 1
                dp[i+1][(j+d) % D][nk] += dp[i][j][k]
                dp[i+1][(j+d) % D][nk] %= mod

ans = (dp[L][0][0]+dp[L][0][1]-1+mod) % mod



print(ans)

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

dp = [[[0]*D for i in range(2)] for _ in range(lenK + 1)]
dp[0][0][0] = 1
for i,c in enumerate(K):
    for less in range(2):
        lim = 9 if less else int(c)
        for r in range(D):
            for d in range(lim+1):
                dp[i+1][less or d < lim][(r+d)%D] += dp[i][less][r]
                dp[i+1][less or d < lim][(r+d)%D] %= mod
print((dp[-1][0][0] + dp[-1][1][0] - 1)%mod)

Solution (Python):
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,pprint,fractions
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

s = input()
D = inp()
n = len(s)

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

for i in range(n):
    nd = int(s[i])
    for j in range(D):
        for k in range(2):
            for d in range(10):
                ni = i+1; nj = (j+d)%D; nk = k
                if k == 0:
                    if d > nd: continue
                    elif d < nd: nk = 1
                dp[ni][nj][nk] += dp[i][j][k] % mod

print((sum(dp[n][0])-1)%mod)

Solution (Python):
import sys
input = sys.stdin.readline
K = list(map(int, list(input())[: -1]))
D = int(input())
mod = 10 ** 9 + 7
dp = [[0] * D for _ in range(len(K) + 1)]
dplim = [[0] * D for _ in range(len(K) + 1)]
dplim[0][0] = 1
for i in range(len(K)):
  for j in range(D):
    dplim[i + 1][(j + K[i]) % D] += dplim[i][j]
    for k in range(10):
      if k < K[i]:
        dp[i + 1][(j + k) % D] += dplim[i][j]
      dp[i + 1][(j + k) % D] += dp[i][j]
      dp[i + 1][(j + k) % D] %= mod
print((dp[-1][0] + dplim[-1][0] - 1) % mod)

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

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

for i in range(N):
    nd = int(K[i])
    for j in range(D):
        for k in range(2):
            for d in range(10):
                ni = i + 1
                nj = (j+d) % D
                nk = k
                if nk == 0:
                    if d > nd:
                        continue
                    if d < nd:
                        nk += 1
                dp[ni][nj][nk] += dp[i][j][k]
                dp[ni][nj][nk] %= mod

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

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


dp = [[[0]*10 for r in range(D)] for d in range(digit)]

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

for d in range(1, digit):
  for r in range(D):
    s = sum(dp[d-1][r])
    for i in range(10):
      dp[d][(r+i)%D][i] += s
      dp[d][(r+i)%D][i] %= MOD

ans = 0
r = 0
for _d, k in enumerate(K, 1):
  d = digit - _d
  k = int(k)
  if _d == 1:
    for i in range(1, k):
      ans += dp[d][0][i]
      ans %= MOD
  else:
    for i in range(1, 10):
      ans += dp[d][0][i]
      ans %= MOD
    
    for i in range(k):
      ans += dp[d][r][i]
      ans %= MOD
  
  r = (r-k)%D

e = 0
for i in K:
  e += int(i)
  e %= D

if e % D == 0:
  ans += 1
  ans %= MOD

print(ans)

Solution (Python):
def main():
    MOD = 10**9 + 7
    K = input()
    D = int(input())
    N = len(K)
    dp = [[[0]*D for j 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(D):
                lim = (9 if j else int(K[i]))
                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)


if __name__ == '__main__':
    main()