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):
import sys
readline = sys.stdin.readline

S = readline().rstrip()
D = int(readline())
DIV = 10 ** 9 + 7
N = len(S)

dp = [[[0] * D for j in range(2)] for i in range(N)]


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

last = int(x0) % D
for i in range(1, len(S)):
  x = S[i]
  dp[i][0][(last + int(x)) % D] += dp[i - 1][0][last]
  dp[i][0][(last + int(x)) % D] %= DIV
  
  for j in range(int(x)):
    dp[i][1][(last + j) % D] += dp[i - 1][0][last]
    dp[i][1][(last + j) % D] %= DIV
  
  for j in range(D):
    for k in range(10):
      dp[i][1][(j + k) % D] += dp[i - 1][1][j]
      dp[i][1][(j + k) % D] %= DIV
  last = (last + int(x)) % D
    
print((dp[-1][0][0] + dp[-1][1][0] - 1) % DIV)

Solution (Python):
n = input()
d = int(input())
t = len(n)
mod = 10**9 + 7
dp1 = [[0 for i in range(d)] for j in range(t)]
dp2 = [[0 for i in range(d)] for j in range(t)]

dp1[0][int(n[0])%d] += 1
for i in range(int(n[0])):
    dp2[0][i%d] += 1
    
for i in range(1,t):
    now = int(n[i])
    for j in range(10):
        if j == now:
            for k in range(d):
                dp1[i][(k+j)%d] += dp1[i-1][k]
                dp2[i][(k+j)%d] += dp2[i-1][k]
                dp1[i][(k+j)%d] %= mod
                dp2[i][(k+j)%d] %= mod
        elif j < now:
            for k in range(d):
                dp2[i][(k+j)%d] += dp1[i-1][k]
                dp2[i][(k+j)%d] += dp2[i-1][k]
                dp2[i][(k+j)%d] %= mod
        else:
            for k in range(d):
                dp2[i][(k+j)%d] += dp2[i-1][k]
                dp2[i][(k+j)%d] %= mod

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

Solution (Python):

k = input()
d = int(input())
n = len(k)
MOD = 10**9+7






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

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

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

Solution (Python):
import sys
sys.setrecursionlimit(1 << 25)
readline = sys.stdin.buffer.readline
read = sys.stdin.readline  

import numpy as np
from functools import partial
array = partial(np.array, dtype=np.int64)
zeros = partial(np.zeros, dtype=np.int64)
full = partial(np.full, dtype=np.int64)

ra = range
enu = enumerate


def a_int(): return int(read())


MOD = 10**9 + 7
INF = 2**31  



K = np.array(list(map(int, list(input()))))
D = a_int()

'''
ある数xにおいて総和がDの倍数であるかの判定
x[0]+x[1]...+x[n] ≡ 0 (mod D) 各桁の和にMODを取れば良い。つまり桁ごとに処理できる

dp[i,j,k] ... K[:i]以下の整数のうち、k=mod Dとなるような数字の個数。j==1は上位桁が一致している場合の通りの個数。j==0は上位桁が一致しなくなったときの個数。

遷移
for l in range(10):
    dp[i+1,0,(k+l)%D] += dp[i,0,k] 
for l in range(K[i]):
    dp[i+1,0,(k+l)%D] += dp[i,1,k] 

dp[i+1,1,(k+K[i])%D] += dp[i,1,k]
'''


from numba import njit


@njit('(i8[:],i8)', cache=True)
def solve(K, D):
    N = K.shape[0]
    dp = np.zeros((N + 1, 2, D), dtype=np.int64)
    dp[0, 1, 0] = 1
    for i in range(N):  
        for k in range(D):  
            
            
            
            
            
            
            for l in range(10):
                m = (k + l) % D
                if l < K[i]:
                    dp[i + 1, 0, m] += dp[i, 0, k] + dp[i, 1, k]
                else:
                    dp[i + 1, 0, m] += dp[i, 0, k]  
                dp[i + 1, 0, m] %= MOD

            
            dp[i + 1, 1, (k + K[i]) % D] += dp[i, 1, k]
            

    print((dp[-1, :, 0].sum() - 1) % MOD)  


solve(K, D)

Solution (Python):
import sys
sys.setrecursionlimit(1 << 25)
readline = sys.stdin.buffer.readline
read = sys.stdin.readline  

import numpy as np
from functools import partial
array = partial(np.array, dtype=np.int64)
zeros = partial(np.zeros, dtype=np.int64)
full = partial(np.full, dtype=np.int64)

ra = range
enu = enumerate


def a_int(): return int(read())


MOD = 10**9 + 7
INF = 2**31  


from collections import defaultdict, Counter, deque
from operator import itemgetter, xor, add
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  
from functools import reduce

K = np.array(list(map(int, list(input()))))
D = a_int()

'''
ある数xにおいて総和がDの倍数であるかの判定
x[0]+x[1]...+x[n] ≡ 0 (mod D) 各桁の和にMODを取れば良い。つまり桁ごとに処理できる

dp[i,j,k] ... K[:i]以下の整数のうち、k=mod Dとなるような数字の個数。j==1は上位桁が一致している場合の通りの個数。j==0は上位桁が一致しなくなったときの個数。

遷移
for l in range(10):
    dp[i+1,0,(k+l)%D] += dp[i,0,k] 
for l in range(K[i]):
    dp[i+1,0,(k+l)%D] += dp[i,1,k] 

dp[i+1,1,(k+K[i])%D] += dp[i,1,k]
'''


from numba import njit


@njit('(i8[:],i8)', cache=True)
def solve(K, D):
    N = K.shape[0]
    dp = np.zeros((N + 1, 2, D), dtype=np.int64)
    dp[0, 1, 0] = 1
    for i in range(N):  
        for k in range(D):  
            for l in range(K[i]):
                
                dp[i + 1, 0, (k + l) % D] += dp[i, 1, k]
            for l in range(10):  
                dp[i + 1, 0, (k + l) % D] += dp[i, 0, k]  
                dp[i + 1, 0, (k + l) % D] %= MOD
            
            dp[i + 1, 1, (k + K[i]) % D] += dp[i, 1, k]
            

    print((dp[-1, :, 0].sum() - 1) % MOD)  


solve(K, D)

Solution (Python):
import sys
sys.setrecursionlimit(1 << 25)
readline = sys.stdin.buffer.readline
read = sys.stdin.readline  

import numpy as np
from functools import partial
array = partial(np.array, dtype=np.int64)
zeros = partial(np.zeros, dtype=np.int64)
full = partial(np.full, dtype=np.int64)

ra = range
enu = enumerate


def a_int(): return int(read())


MOD = 10**9 + 7
INF = 2**31  


from collections import defaultdict, Counter, deque
from operator import itemgetter, xor, add
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  
from functools import reduce

K = np.array(list(map(int, list(input()))))
D = a_int()

'''
ある数xにおいて総和がDの倍数であるかの判定
x[0]+x[1]...+x[n] ≡ 0 (mod D) 各桁の和にMODを取れば良い。つまり桁ごとに処理できる

dp[i,j,k] ... K[:i]以下の整数のうち、k=mod Dとなるような数字の個数。j==1は上位桁が一致している場合の通りの個数。j==0は上位桁が一致しなくなったときの個数。

遷移
for l in range(10):
    dp[i+1,0,(k+l)%D] += dp[i,0,k] 
for l in range(K[i]):
    dp[i+1,0,(k+l)%D] += dp[i,1,k] 

dp[i+1,1,(k+K[i])%D] += dp[i,1,k]
'''


from numba import njit


@njit('(i8[:],i8)', cache=True)
def solve(K, D):
    N = K.shape[0]
    dp = np.zeros((N + 1, 2, D), dtype=np.int64)
    dp[0, 1, 0] = 1
    for i in range(N):  
        for k in range(D):  
            for l in range(10):  
                dp[i + 1, 0, (k + l) % D] += dp[i, 0, k]  
                if l < K[i]:
                    dp[i + 1, 0, (k + l) % D] += dp[i, 1, k]
                    
                dp[i + 1, 0, (k + l) % D] %= MOD
            
            if dp[i, 1, k]:
                dp[i + 1, 1, (k + K[i]) % D] += dp[i, 1, k]
            

    print((dp[-1, :, 0].sum() - 1) % MOD)  


solve(K, D)

Solution (Python):
import sys
sys.setrecursionlimit(1 << 25)
readline = sys.stdin.buffer.readline
read = sys.stdin.readline  

import numpy as np
from functools import partial
array = partial(np.array, dtype=np.int64)
zeros = partial(np.zeros, dtype=np.int64)
full = partial(np.full, dtype=np.int64)

ra = range
enu = enumerate


def a_int(): return int(read())


MOD = 10**9 + 7
INF = 2**31  


from collections import defaultdict, Counter, deque
from operator import itemgetter, xor, add
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  
from functools import reduce

K = np.array(list(map(int, list(input()))))
D = a_int()

'''
ある数xにおいて総和がDの倍数であるかの判定
x[0]+x[1]...+x[n] ≡ 0 (mod D) 各桁の和にMODを取れば良い。つまり桁ごとに処理できる

dp[i,j,k] ... K[:i]以下の整数のうち、k=mod Dとなるような数字の個数。j==1は上位桁が一致している場合の通りの個数。j==0は上位桁が一致しなくなったときの個数。

遷移
for l in range(10):
    dp[i+1,0,(k+l)%D] += dp[i,0,k] 
for l in range(K[i]):
    dp[i+1,0,(k+l)%D] += dp[i,1,k] 

dp[i+1,1,(k+K[i])%D] += dp[i,1,k]
'''


from numba import njit


@njit('(i8[:],i8)', cache=True)
def solve(K, D):
    N = K.shape[0]
    dp = np.zeros((N + 1, 2, D), dtype=np.int64)
    dp[0, 1, 0] = 1
    for i in range(N):  
        for k in range(D):  
            for l in range(10):  
                dp[i + 1, 0, (k + l) % D] += dp[i, 0, k]  
                if l < K[i]:
                    dp[i + 1, 0, (k + l) % D] += dp[i, 1, k]
                    
                dp[i + 1, 0, (k + l) % D] %= MOD
            
            dp[i + 1, 1, (k + K[i]) % D] += dp[i, 1, k]
            

    print((dp[-1, :, 0].sum() - 1) % MOD)  


solve(K, D)

Solution (Python):
import sys
sys.setrecursionlimit(1 << 25)
readline = sys.stdin.buffer.readline
read = sys.stdin.readline  

import numpy as np
from functools import partial
array = partial(np.array, dtype=np.int64)
zeros = partial(np.zeros, dtype=np.int64)
full = partial(np.full, dtype=np.int64)

ra = range
enu = enumerate


def a_int(): return int(read())


MOD = 10**9 + 7
INF = 2**31  


from collections import defaultdict, Counter, deque
from operator import itemgetter, xor, add
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  
from functools import reduce

K = np.array(list(map(int, list(input()))))
D = a_int()

'''
ある数xにおいて総和がDの倍数であるかの判定
x[0]+x[1]...+x[n] ≡ 0 (mod D) 各桁の和にMODを取れば良い。つまり桁ごとに処理できる

dp[i,j,k] ... K[:i]以下の整数のうち、k=mod Dとなるような数字の個数。j==1は上位桁が一致している場合の通りの個数。j==0は上位桁が一致しなくなったときの個数。

遷移
for l in range(10):
    dp[i+1,0,(k+l)%D] += dp[i,0,k] 
for l in range(K[i]):
    dp[i+1,0,(k+l)%D] += dp[i,1,k] 

dp[i+1,1,(k+K[i])%D] += dp[i,1,k]
'''


from numba import njit


@njit('(i8[:],i8)', cache=True)
def solve(K, D):
    N = K.shape[0]
    dp = np.zeros((N + 1, 2, D), dtype=np.int64)
    dp[0, 1, 0] = 1
    for i in range(N):  
        for k in range(D):  
            for l in range(10):  
                dp[i + 1, 0, (k + l) % D] += dp[i, 0, k]  
                if l < K[i]:
                    dp[i + 1, 0, (k + l) % D] += dp[i, 1, k]  
                    
                dp[i + 1, 0, (k + l) % D] %= MOD
            
            dp[i + 1, 1, (k + K[i]) % D] += dp[i, 1, k]
            dp[i + 1, 1, (k + K[i]) % D] %= MOD

    print((dp[-1, :, 0].sum() - 1) % MOD)  


solve(K, D)

Solution (Python):
k=input()
d=int(input())
l=len(k)
N=10**9 + 7
dp=[[[0]*2 for _ in range(d+5)] for i in range(l+5)]
prefs=[int(k[0])%d]
for i in range(1,l):
    prefs.append((prefs[i-1]+int(k[i]))%d)
for i in range(0,int(k[0])):
    dp[0][i%d][1]+=1
dp[0][int(k[0])%d][0]+=1
for i in range(1,l):
    for r in range(d):
        for dig in range(10):
            dp[i][r][1]=(dp[i][r][1]+dp[i-1][(r-dig+d)%d][1])%N
        for dig in range(0,int(k[i])):
            dp[i][r][1] = (dp[i][r][1] + dp[i - 1][(r - dig + d) % d][0]) % N
        if prefs[i]==r:
            dp[i][r][0]=(dp[i][r][0]+1)%N
print((dp[l-1][0][1]+dp[l-1][0][0]-1+N)%N)

Solution (Python):
import math

K=input()
D=int(input())
n=len(K)
dp=[[[0 for _ in range(D)] for _ in range(2)] for _ in range(n+1)]
MOD=10**9+7

dp[0][0][0]=1
for i in range(0,n):
    a=int(K[i])
    x=a%D
    for j in range(D):
        for x in range(10):
            dp[i+1][1][(j+x)%D]=(dp[i+1][1][(j+x)%D]+dp[i][1][j])%MOD
        for x in range(a):
            dp[i+1][1][(j+x)%D]=(dp[i+1][1][(j+x)%D]+dp[i][0][j])%MOD
        dp[i+1][0][(j+a)%D]=dp[i][0][j]

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

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

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

for i in range(len(k)):
  x=int(k[i])
  for j in range(d):
    dp[i+1][(j+x)%d][0]+=dp[i][j][0]
    dp[i+1][(j+x)%d][0]%=mod
    for z in range(10):
      dp[i+1][(j+z)%d][1]+=dp[i][j][1]
      dp[i+1][(j+z)%d][1]%=mod
    
    for y in range(x):
      dp[i+1][(j+y)%d][1]+=dp[i][j][0]
      dp[i+1][(j+y)%d][1]%=mod
      

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

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


def main():
    K = input().replace("\n", "")
    D = int(input())
    
    mod = pow(10, 9)+7
    n = len(K)
    dp = [[0]*D for _ in range(n+1)]
    
    dp[0][0] = 1
    sub = 0
    
    if D == 1:
        ans = 0
        for i in range(n):
            ans = (ans*10+int(K[i]))%mod
        print(ans)
        sys.exit()


    for i in range(n):
        if i != 0:
            for j in range(10):
                for k in range(D):
                    dp[i+1][(k+j)%D] += dp[i][k]
                    dp[i+1][(k+j)%D] %= mod
            for j in range(1, 10):
                dp[i+1][j%D] += 1
                dp[i+1][j%D] %= mod
        
        
        for j in range(int(K[i])):
            if i == 0 and j == 0:
                continue
            dp[i+1][(j+sub)%D] += 1
            dp[i+1][(j+sub)%D] %= mod
        sub = (sub+int(K[i]))%D
    
    sub = 0
    for i in range(n):
        sub = (sub+int(K[i]))%D
    if sub == 0:
        dp[n][0] += 1
        dp[n][0] %= mod
        
    
    print(dp[n][0])
    
    
if __name__ == "__main__":
    main()

Solution (Python):






import sys
input = sys.stdin.readline

import math

import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache





MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"






def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]



def DD(arg): return defaultdict(arg)


def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr


def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors


def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum


def gcd(a, b):
    while b: a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd (a, b)


def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count


def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]


def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count





K = S()
D = I()

N = len(K)

dp = [[[0 for i in range(D)] for f in range(2)] for k in range(N+1)]
dp[0][0][0] = 1
for k in range(N):
  s = int(K[k])
  for i in range(D):
    for j in range(10):
      dp[k+1][1][(i+j)%D] += dp[k][1][i]
      dp[k+1][1][(i+j)%D] %= MOD
    for j in range(s):
      dp[k+1][1][(i+j)%D] += dp[k][0][i]
      dp[k+1][1][(i+j)%D] %= MOD
    dp[k+1][0][(i+s)%D] += dp[k][0][i]
    dp[k+1][0][(i+s)%D] %= MOD

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

Solution (Python):






import sys
input = sys.stdin.readline

import math

import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache





MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"






def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]



def DD(arg): return defaultdict(arg)


def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr


def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors


def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum


def gcd(a, b):
    while b: a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd (a, b)


def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count


def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]


def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count





K = S()
D = I()

N = len(K)

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

ans = 0
carry = 0
for i in range(N):
  s = int(K[i])
  for j in range(s):
    ans += dp[N-1-i][(-carry-j)%D]
    ans %= MOD
  carry += s
  carry %= D

print((ans-1+int(carry==0))%MOD)

Solution (Python):
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy


import heapq
sys.setrecursionlimit(10**6)
INF =  float("inf")
import bisect
import statistics
mod = 10**9+7

K = input()
D = int(input())

n = len(K)

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

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

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

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gcd
from operator import mul
from functools import reduce
from operator import mul
from pprint import pprint



sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


def digit_dp(n, f):
    dp = [[[0] * f for _ in range(2)] for _ in range(10002)]
    dp[0][0][0] = 1
    l = len(n)
    for i in range(l):
        max_d = int(n[i])
        for j in range(2):
            for ki in range(f):
                for di in range(10 if j else max_d + 1):
                    dp[i + 1][j or (di < max_d)][(ki + di) % f] += dp[i][j][ki]
                    dp[i + 1][j or (di < max_d)][(ki + di) % f] %= mod
    return dp[l][0][0] + dp[l][1][0] - 1


k = input()
d = I()
print(digit_dp(k, d) % mod)

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gcd
from operator import mul
from functools import reduce
from operator import mul
from pprint import pprint



sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


def digit_dp(n, f):
    dp = [[[0] * f for _ in range(2)] for _ in range(10002)]
    dp[0][0][0] = 1
    l = len(n)
    for i in range(l):
        max_d = int(n[i])
        for j in range(2):
            for ki in range(f):
                for di in range(10 if j else max_d + 1):
                    dp[i + 1][j or (di < max_d)][(ki + di) % f] += dp[i][j][ki]
                    dp[i + 1][j or (di < max_d)][(ki + di) % f] %= mod
    return dp[l][0][0] + dp[l][1][0] - 1


k = input()
d = int(input())
print(digit_dp(k, d) % mod)

Solution (Python):

import numpy as np
from numba import njit


@njit("i8(i8[:],i8)")
def solve(K, D):
    N = len(K)
    MOD = 1_000_000_007
    dp = np.zeros((N + 1, 2, D), dtype=np.int64)
    dp[0][0][0] = 1
    for i in range(N):
        for is_less in range(2):
            for k in range(D):
                for l in range(10 if is_less else K[i] + 1):
                    is_less_ = is_less or l < K[i]
                    k_ = (k + l) % D
                    dp[i + 1][is_less_][k_] += dp[i][is_less][k]
                    dp[i + 1][is_less_][k_] %= MOD
    return (dp[N][0][0] + dp[N][1][0] - 1) % MOD


print(solve(np.array(list(map(int, input()))), int(input())))

Solution (Python):
def solve(K, D):
    N = len(K)
    MOD = 1_000_000_007
    dp = [[[0] * D for _ in range(2)] for _ in range(N + 1)]
    dp[0][0][0] = 1
    for i in range(N):
        for is_less in range(2):
            for k in range(D):
                for l in range(10 if is_less else K[i] + 1):
                    is_less_ = is_less or l < K[i]
                    k_ = (k + l) % D
                    dp[i + 1][is_less_][k_] += dp[i][is_less][k]
                    dp[i + 1][is_less_][k_] %= MOD
    return (dp[N][0][0] + dp[N][1][0] - 1) % MOD


print(solve(list(map(int, input())), int(input())))

Solution (Python):
from sys import stdin, stdout, setrecursionlimit
from collections import deque, defaultdict, Counter
from heapq import heappush, heappop
from functools import lru_cache
import math

setrecursionlimit(10**6)
rl = lambda: stdin.readline()
rll = lambda: stdin.readline().split()
rli = lambda: map(int, stdin.readline().split())
rlf = lambda: map(float, stdin.readline().split())

INF, NINF = float('inf'), float('-inf')
MOD = 10**9 + 7

def main():
	K = rll()[0]
	D = int(rl())
	lim = []
	for c in K: lim.append(int(c))
	n = len(lim)
	dp = [[[0]*D for j in range(2)] for i in range(n+1)]
	dp[0][1][0] = 1
	for i in range(n):
		for tight in range(2):
			for ds in range(D):
				md = lim[i] if tight else 9
				for d in range(md+1):
					nt = 1 if tight and lim[i] == d else 0
					nds = (d + ds) % D
					dp[i+1][nt][nds] += dp[i][tight][ds]
					dp[i+1][nt][nds] %= MOD
	ans = (dp[n][0][0] + dp[n][1][0] - 1) % MOD
	print(ans)
	stdout.close()

if __name__ == "__main__":
	main()

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

Solution (Python):
def solve():
  K = list(map(int,list(input())))
  digit = len(K)
  D = int(input())
  dp = [[[0]*D for _ in range(2)] for _ in range(digit+1)]
  dp[0][1][0] = 1
  mod = 10**9+7
  for k in range(1,digit+1):
    for d in range(D):
      dp[k][1][d] = dp[k-1][1][(d-K[k-1])%D]
      for p in range(10):
        dp[k][0][d] += dp[k-1][0][(d-p)%D] 
      for p in range(K[k-1]):
        dp[k][0][d] += dp[k-1][1][(d-p)%D]
      dp[k][0][d] %= mod
  ans = (dp[-1][0][0]+dp[-1][1][0]-1)%mod
  return ans
print(solve())

Solution (Python):
mod=10**9+7
n=input()
d=int(input())
l=len(n)
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(10):
    for k in range(d):
      if j==int(n[i]):
        dp[i+1][0][(k+j)%d]+=dp[i][0][k]
        dp[i+1][1][(k+j)%d]+=dp[i][1][k]
      elif j<int(n[i]):
        dp[i+1][1][(k+j)%d]+=dp[i][0][k]+dp[i][1][k]
      elif j>int(n[i]):
        dp[i+1][1][(k+j)%d]+=dp[i][1][k]
      dp[i+1][0][k]%=mod
      dp[i+1][1][k]%=mod
print((dp[-1][0][0]+dp[-1][1][0]-1)%mod)

Solution (Python):
import sys

stdin = sys.stdin


def ni(): return int(ns())


def na(): return list(map(int, stdin.readline().split()))


def naa(N): return [na() for _ in range(N)]


def ns(): return stdin.readline().rstrip()  


K = ns()
D = ni()

dp = [0] * D
mod = 10 ** 9 + 7
now_mod = 0

for k in K:
    k = int(k)
    dp_old = dp
    dp = [0] * D
    for kk in range(k):
        dp[(now_mod+kk) % D] += 1
    now_mod = (now_mod + k) % D
    for i, d in enumerate(dp_old):
        for n in range(10):
            dp[(i+n) % D] += d
            dp[(i+n) % D] %= mod
    
if now_mod == 0:
    dp[0] += 1
print((dp[0]-1) % mod)

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

MOD = [[0] * 10 for i in range(n)]






for i in range(n):
    for j in range(10):
        MOD[i][j] = j % d

D = [0] * d
h = 0
for i in range(int(k[0])):
    D[MOD[n-1][i]] += 1
h = MOD[n-1][int(k[0])]

for i in range(1, n):
    
    DN = [0] * d
    for j in range(10):
        for l in range(d):
            DN[(l + MOD[n-1-i][j]) % d] = (DN[(l + MOD[n-1-i][j]) % d] + D[l]) % mod
    for j in range(int(k[i])):
        DN[(h + MOD[n-1-i][j]) % d] = (DN[(h + MOD[n-1-i][j]) % d] + 1) % mod
    h = (h + MOD[n-1-i][int(k[i])]) % d
    D = DN[:]


D[h] += 1

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

Solution (Python):

def resolve():
    MOD = 10**9+7
    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):
        for d in range(D):
            
            for k in range(10):
                dp[i + 1][(d + k) % D][1] += dp[i][d][1]
                dp[i + 1][(d + k) % D][1] %= MOD

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

            dp[i + 1][(d + num) % D][0] += dp[i][d][0]
            dp[i + 1][(d + num) % D][0] %= MOD


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


if __name__ == "__main__":
    resolve()

Solution (Python):

def resolve():
    MOD = 10**9+7
    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):
        num = int(K[i])
        for j in range(D):
            for smaller in range(2):
                for d in range(10):
                    ni = i+1
                    nsmaller = smaller
                    nj = (j+d)%D
                    if smaller == 0:
                        if d < num:
                            nsmaller = 1
                        if d > num:
                            continue
                    dp[ni][nj][nsmaller] += dp[i][j][smaller]
                    dp[ni][nj][nsmaller] %= MOD
    print((dp[N][0][1] + dp[N][0][0] - 1) % MOD)


if __name__ == "__main__":
    resolve()