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: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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: Time Limit Exceeded

Solution code:
import numpy as np

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

dp = np.array([[[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: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
K = int(input())
D = int(input())
strK = str(K)
lenK = len(strK)
#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 in range(lenK):
    for j in range(2):
        for k in range(D):
            if j == 0:
                for l in range(int(strK[i])+1):
                    if l != int(strK[i]):    
                        if k + l < D:
                            dp[i+1][1][k+l] += dp[i][0][k]
                        else:
                            dp[i+1][1][(k+l)%D] += dp[i][0][k]
                    else:
                        if k+l < D:
                            dp[i+1][0][k+l] += dp[i][0][k]
                        else:
                            dp[i+1][0][(k+l)%D] += dp[i][0][k]
            else:
                for l in range(10):
                    if k+l < D:
                        dp[i+1][1][k+l] += dp[i][1][k]
                    else:
                        dp[i+1][1][(k+l)%D] += dp[i][1][k]
print((dp[lenK][0][0] + dp[lenK][1][0] - 1)%1000000007)

Submission status: Time Limit Exceeded

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

# dp[d][r][i] : (d+1)桁目の数がiで、それまでの桁の数の和をDで割ったときの余りがrとなる組合せ
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)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
k=list(input())
d=int(input())
dp1=np.array([[0]*d for _ in range(len(k))],dtype=np.int64)
dp2=np.array([[0]*d for _ in range(len(k))],dtype=np.int64)
mod=10**9+7

def mult(a,b):
    a=np.hstack((a,np.zeros(d,dtype=np.int64)))
    b=np.hstack((b,np.zeros(d,dtype=np.int64)))
    c=np.fft.irfft(np.fft.rfft(a)*np.fft.rfft(b))
    return np.rint(c[:d]+c[d:])%mod
def createD(n):
    return np.hstack((np.full(n%d+1,n//d+1),np.full(d-n%d-1,n//d)))

dp1[0]=createD(9)
dp2[0]=createD(int(k[-1]))
for i,c in enumerate(reversed(k[:-1])):
    c=int(c)
    dp1[i+1]=mult(dp1[0],dp1[i])
    if c==0:
        dp2[i+1]=dp2[i]
    else:
        p=np.zeros(d);p[c%d]=1
        dp2[i+1]=mult(createD(c-1),dp1[i])+mult(p,dp2[i])
print((dp2[-1][0]-1)%mod)

Submission status: Time Limit Exceeded

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():
    def ketadp(a,D):
        n = len(a)
        dp = defaultdict(int)
        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]
                dp[i + 1, less_, hasD_] %= mod

        ans = sum(dp[n, less, 0] for less in (0, 1))
        return ans
    K = SI()
    D = I()
    ans = (ketadp(K,D)-1)%mod
    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 = 10**9 + 7
mod2 = 998244353
inf = 10**18
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**6)

if __name__ == '__main__':
    examS()

"""

"""

Submission status: Time Limit Exceeded

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

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

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

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

for i in range(1,leng):
    for j in range(0,10):
        for l in range(d):
            #既にk以下であることが確定
            dp1[(l+j)%d] += dp2[l]
            dp1[(l+j)%d] %= mod

        #上からi桁目でk以下が確定
        if j<li[i]:
            dp1[(mm1+j)%d] += 1
            dp1[(mm1+j)%d] %= mod
    #print(dp1,dp2)
    mm1 = (mm1+li[i])%d
    dp2 = [dp1[i] for i in range(d)]
    dp1 = [0 for _ in range(d)]
dp2[sum(li)%d]+=1
print((dp2[0]-1)%mod)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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] += 1

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

Submission status: Time Limit Exceeded

Solution code:
K = input()
N = len(K)
D = int(input())
X = [0] * D
Y = [0] * D
X[0] = 1
P = 10**9+7
for i in range(N):
    nX = [0] * D
    nY = [0] * D
    for j in range(10):
        for k in range(D):
            nk = (j+k)%D
            nY[nk] += Y[k]
            if j < int(K[i]):
                nY[nk] = (nY[nk] + X[k]) % P
            elif j == int(K[i]):
                nX[nk] = (nX[nk] + X[k]) % P
    
    X, Y = nX, nY
print((X[0] + Y[0] - 1) % P)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9+7
k = input()
d = int(input())
n = len(k)
dp = [[0] * 2 for _ in range(d)]
# dp[sum][smaller_already] - the number of ways to choose digits so far
# such that the sum of digits modulo D is 'sum' and 'smaller_already'
# says whether we already chosen some digit smaller than in K
dp[0][0] = 1
for i in range(n):
    new_dp = [[0] * 2 for _ in range(d)]
    for sums in range(d):
        for sm_already in (False, True):
            for digit in range(10):
                if digit > int(k[i]) and not sm_already:
                    break
                new_dp[(sums + digit) % d][sm_already or (digit < int(k[i]))] += dp[sums][sm_already]
    dp = new_dp
res = (dp[0][False] + dp[0][True] - 1) % MOD
print(res)

Submission status: Time Limit Exceeded

Solution code:
p = 10**9+7
K = input().strip()
D = int(input())
n = len(K)
dp = [[[0 for _ in range(D)] for _ in range(2)] for _ in range(n+1)]
dp[0][0][0] = 1
for i in range(1,n+1):
    for t in range(2):
        for d in range(D):
            for j in range(10 if t else int(K[i-1])+1):
                dp[i][t or (j<int(K[i-1]))][(d+j)%D] = (dp[i][t or (j<int(K[i-1]))][(d+j)%D]+dp[i-1][t][d])%p
print((dp[n][0][0]+dp[n][1][0]-1)%p)

Submission status: Time Limit Exceeded

Solution code:
p = 10**9+7
K = input().strip()
D = int(input())
n = len(K)
dp = [[[0 for _ in range(D)] for _ in range(2)] for _ in range(n+1)]
dp[0][0][0] = 1
for i in range(1,n+1):
    for t in range(2):
        for d in range(D):
            for j in range(10 if t else int(K[i-1])+1):
                dp[i][t|(j<int(K[i-1]))][(d+j)%D] = (dp[i][t|(j<int(K[i-1]))][(d+j)%D]+dp[i-1][t][d])%p
print((dp[n][0][0]+dp[n][1][0]-1)%p)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)
m=10**9+7
 
num=input()
d=int(input())
pl = len(num)
dp = [[[-1,-1] for i in range(d)] for j in range(pl)]
 
 
def solve(i,res,tt):
    if i>=pl:
        if res%d==0:
            return 1
        return 0
    if dp[i][res][tt]!=-1:
        return dp[i][res][tt]
    else:
        if tt:
            s=0
            lim = int(num[i])
            for j in range(lim):
                s+=solve(i+1, (res+j)%d, 0)%m
            s+=solve(i+1, (res+lim)%d, 1)%m
            dp[i][res][tt] = s
            return s
 
        else:
            s=0
            for j in range(0,10):
                s+=solve(i+1, (res+j)%d, 0)%m
            dp[i][res][tt] = s
            return s
print((solve(0,0,1)-1)%m)

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache
import sys
sys.setrecursionlimit(10**9)
m=10**9+7
 
num=input()
d=int(input())
pl = len(num)
 
@lru_cache(None)
def solve(i,res,tt):
    if i>=pl:
        if res%d==0:
            return 1
        return 0
    else:
        if tt:
            s=0
            lim = int(num[i])
            for j in range(lim):
                s+=solve(i+1, (res+j)%d, 0)%m
            s+=solve(i+1, (res+lim)%d, 1)%m
            return s
 
        else:
            s=0
            for j in range(0,10):
                s+=solve(i+1, (res+j)%d, 0)%m
            return s
print((solve(0,0,1)-1)%m)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)
m=10**9+7
from collections import defaultdict
 
num=input()
d=int(input())
pl = len(num)
dp = [defaultdict(lambda : [-1,-1]) for i in range(pl)]

 
def solve(i,res,tt):
    if i>=pl:
        if res%d==0:
            return 1
        return 0
    if dp[i][res][tt]!=-1:
        return dp[i][res][tt]
    else:
        if tt:
            s=0
            lim = int(num[i])
            for j in range(lim):
                s+=solve(i+1, (res+j)%d, 0)%m
            s+=solve(i+1, (res+lim)%d, 1)%m
            dp[i][res][tt] = s
            return s
 
        else:
            s=0
            for j in range(0,10):
                s+=solve(i+1, (res+j)%d, 0)%m
            dp[i][res][tt] = s
            return s
print((solve(0,0,1)-1)%m)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)
m=10**9+7
 
num=input()
d=int(input())
pl = len(num)
dp = [[[-1,-1] for i in range(d)] for j in range(pl)]

 
def solve(i,res,tt):
    if i>=pl:
        if res%d==0:
            return 1
        return 0
    if dp[i][res][tt]!=-1:
        return dp[i][res][tt]
    else:
        if tt:
            s=0
            lim = int(num[i])
            for j in range(lim):
                s+=solve(i+1, (res+j)%d, 0)%m
            s+=solve(i+1, (res+lim)%d, 1)%m
            dp[i][res][tt] = s
            return s
 
        else:
            s=0
            for j in range(0,10):
                s+=solve(i+1, (res+j)%d, 0)%m
            dp[i][res][tt] = s
            return s
print((solve(0,0,1)-1)%m)

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache
import sys
sys.setrecursionlimit(10**9)
m=10**9+7

num=input()
d=int(input())
pl = len(num)

@lru_cache(None)
def solve(i,res,tt):
    if i>=pl:
        if res%d==0:
            return 1
        return 0
    else:
        if tt:
            s=0
            lim = int(num[i])
            for j in range(lim):
                s+=solve(i+1, (res+j)%d, 0)%m
            s+=solve(i+1, (res+lim)%d, 1)%m
            return s

        else:
            s=0
            for j in range(0,10):
                s+=solve(i+1, (res+j)%d, 0)%m
            return s
print((solve(0,0,1)-1)%m)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9 + 7


def ketadp3(a, b):
    L = len(str(a))

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

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


def main():
    # a, b = map(int, input().split())
    # print(ketadp(b)-ketadp(a-1))
    n = int(input())
    d = int(input())
    print(ketadp3(n, d))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9 + 7


def ketadp3(a, b):
    L = len(str(a))

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

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


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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9+7
s = input()
d = int(input())
dp = [[[0 for _ in range(2)] for _ in range(d)] for _ in range(len(s)+1)]
dp[0][0][0] = 1

for i in range(len(s)):
	for j in range(d):
		for k in range(10):
			dp[i+1][(j+k)%d][1] += dp[i][j][1]
			dp[i+1][(j+k)%d][1] %= MOD
			if int(s[i]) == k:
				dp[i+1][(j+k)%d][0] += dp[i][j][0]
				dp[i+1][(j+k)%d][0] %= MOD
			elif int(s[i]) > k:
				dp[i+1][(j+k)%d][1] += dp[i][j][0]
				dp[i+1][(j+k)%d][1] %= MOD

print((sum(dp[len(s)][0])-1)%MOD)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**8)

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

memo = [[[-1 for k in range(2)] for j in range(D)] for i in range(N)]

def f(digit, current_sum, flag):
    if digit == -1:
        if current_sum % D == 0:
            return 1
        else:
            return 0

    #if memo[digit][current_sum][flag] != -1:
    #    return memo[digit][current_sum][flag]

    ret = 0
    for i in range(10):
        if flag or i < int(K[N-1-digit]):
            if memo[digit-1][(current_sum+i)%D][1] != -1:
                ret += memo[digit-1][(current_sum+i)%D][1]
            else:
                ret += f(digit-1, (current_sum+i)%D, 1)
        elif i == int(K[N-1-digit]):
            if memo[digit-1][(current_sum+i)%D][0] != -1:
                ret += memo[digit-1][(current_sum+i)%D][0]
            else:
                ret += f(digit-1, (current_sum+i)%D, 0)
        
    memo[digit][current_sum][flag] = ret % MOD
    return ret

#substract 0 case
ans = (f(N-1, 0, 0) - 1) % MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**8)

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

memo = [[[-1 for k in range(2)] for j in range(D)] for i in range(N)]

def f(digit, current_sum, flag):
    if digit == -1:
        if current_sum % D == 0:
            return 1
        else:
            return 0

    if memo[digit][current_sum][flag] != -1:
        return memo[digit][current_sum][flag]

    ret = 0
    for i in range(10):
        if flag or i < int(K[N-1-digit]):
            ret += f(digit-1, (current_sum+i)%D, 1)
            ret %= MOD
        elif i == int(K[N-1-digit]):
            ret += f(digit-1, (current_sum+i)%D, 0)
            ret %= MOD

    memo[digit][current_sum][flag] = ret
    return ret

#substract 0 case
ans = (f(N-1, 0, 0) - 1) % MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**8)
from functools import lru_cache

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

@lru_cache(maxsize=10000000)
def f(digit, current_sum, flag):
    if digit == -1:
        if current_sum % D == 0:
            return 1
        else:
            return 0

    ret = 0
    for i in range(10):
        if flag or i < int(K[N-1-digit]):
            ret += f(digit-1, (current_sum+i)%D, 1)
        elif i == int(K[N-1-digit]):
            ret += f(digit-1, (current_sum+i)%D, 0)
    
    return ret % MOD

#substract 0 case
ans = (f(N-1, 0, 0) - 1) % MOD
print(ans)