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



Sample input:
30
4


Sample output:
6

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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 #smaller->smaller
            if d < nd:
                dp[i+1][1][(j+d)%D] += dp[i][0][j%D]%MOD #exact->smaller
        dp[i+1][0][(j+int(K[i]))%D] += dp[i][0][j%D]%MOD #exact->exact


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

Submission status: Accepted

Solution code:
import sys
#input = sys.stdin.buffer.readline

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()

Submission status: Accepted

Solution code:
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[i][j] : 上からi桁目まで見てKと同じ時の、数字の総和がj(mod d)の数
    #dp2[i][j] : 上からi桁目まで見てK未満確定時の、数字の総和がj(mod d)の数
    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()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

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()

# dp[i][j] := i桁目まで見て、桁和がmod Dでjの時の通り数
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)

Submission status: Accepted

Solution code:
K=input()
D=int(input())
#余り0,余り1,余り2,…,余り(D-1)
dp=[0]*D
mod=10**9+7
s=0
for i in range(len(K)):
  ndp=[0]*D
  #余りがjだったものは(j+d)%Dの余りに変わるので
  for j in range(D):
    for d in range(10):
      ndp[(j+d)%D]=(ndp[(j+d)%D]+dp[j])%mod
  #直前までKと数字が同じだったものをカウント
  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)

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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)
# print(DP)

Submission status: Accepted

Solution code:
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
# print(mod(dfs() - 1))

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))

Submission status: Accepted

Solution code:
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)
# print(DP)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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

# main()
print(main())

Submission status: Accepted

Solution code:
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
#dp[1][1][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)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
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)
# for di in dp:
#   print(*di)

Submission status: Accepted

Solution code:
k = str(input())
d = int(input())
 
l = len(k)
 
mod = 10 ** 9 + 7
 
#less than: 1, else: 0
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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):
            #lim = 9 if k == 1 else nd
            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

#for i in range(L+1):
#    print(dp[i])
print(ans)

Submission status: Accepted

Solution code:
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):
            #lim = 9 if k == 1 else nd
            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

#for i in range(L+1):
#    print(dp[i])
print(ans)

Submission status: Accepted

Solution code:
K = input()
D = int(input())
lenK = len(K)
mod = 10**9+7
#dp[i][smaller][k]はi桁まで見たあまりkの物の数とする.ただしsmaller=0のときはまだK以下かわかってないとする. 
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)

Submission status: Accepted

Solution code:
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[i][j][k]: i上から桁目まででそれまでの和をDで割ったあまりがj,k=0:Nと一緒 k=1:Nより小さいことが確定
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
# pprint.pprint(dp)
print((sum(dp[n][0])-1)%mod)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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):
                    # print(i, j, lim, d, j or d < lim)
                    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()

Submission status: Accepted

Solution code:
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():
    # LCS
    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():
    # http://zehnpaard.hatenablog.com/entry/2018/06/26/201512
    # トポロジカルソート
    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)
#    print(Order)
    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))
#    print(dp)
    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
#    print(dp)
    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
#    print(dp)
    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)
#    print(dp)
    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
#    print(dp)
    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
#        print(s,W,B)
        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)
#            print(m,maskT,cur)
            # 次の部分maskT
            maskT = (maskT - 1) & m
#    print(dp)
    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()

"""

"""

Submission status: Accepted

Solution code:
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

# if( k_len == 1 ):
#     k = int(k)
#     print(k//d)
#     exit()
#
# for i in range(10):
#     dp[0][i%d] += 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)

Submission status: Accepted

Solution code:
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)