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: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
input=lambda :sys.stdin.buffer.readline().rstrip()
class ModInt(object):
    __MOD=10**9+7

    def __init__(self,x):
        self.__x=x%self.__MOD

    def __repr__(self):
        return str(self.__x)

    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,self.__MOD-2,self.__MOD)) if isinstance(other, ModInt) else ModInt(self.__x*pow(other, self.__MOD-2,self.__MOD))

    def __pow__(self,other):
        return ModInt(pow(self.__x,other.__x,self.__MOD)) if isinstance(other,ModInt) else ModInt(pow(self.__x,other,self.__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,self.__MOD-2,self.__MOD)) if isinstance(other,ModInt) else ModInt(other*pow(self.__x,self.__MOD-2,self.__MOD))

    def __rpow__(self,other):
        return ModInt(pow(other.__x,self.__x,self.__MOD)) if isinstance(other,ModInt) else ModInt(pow(other,self.__x,self.__MOD))

def resolve():
    k=input()
    n=len(k)
    d=int(input())
    dp=[[[ModInt(0)]*2 for _ in range(d)] for _ in range(n+1)]
    dp[0][0][0]=ModInt(1)
    for i in range(n):
        a=int(k[i])
        for m in range(d):
            for j in range(10):
                if(j<a):
                    dp[i+1][(m+j)%d][1]+=dp[i][m][0]
                    dp[i+1][(m+j)%d][1]+=dp[i][m][1]
                elif(j==a):
                    dp[i+1][(m+j)%d][0]+=dp[i][m][0]
                    dp[i+1][(m+j)%d][1]+=dp[i][m][1]
                else:
                    dp[i+1][(m+j)%d][1]+=dp[i][m][1]
    print(dp[n][0][0]+dp[n][0][1]-1)
resolve()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
input=lambda :sys.stdin.buffer.readline().rstrip()
class ModInt(object):
    __MOD=10**9+7

    def __init__(self,x):
        self.__x=x%self.__MOD

    def __repr__(self):
        return str(self.__x)

    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,self.__MOD-2,self.__MOD)) if isinstance(other, ModInt) else ModInt(self.__x*pow(other, self.__MOD-2,self.__MOD))

    def __pow__(self,other):
        return ModInt(pow(self.__x,other.__x,self.__MOD)) if isinstance(other,ModInt) else ModInt(pow(self.__x,other,self.__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,self.__MOD-2,self.__MOD)) if isinstance(other,ModInt) else ModInt(other*pow(self.__x,self.__MOD-2,self.__MOD))

    def __rpow__(self,other):
        return ModInt(pow(other.__x,self.__x,self.__MOD)) if isinstance(other,ModInt) else ModInt(pow(other,self.__x,self.__MOD))

def resolve():
    k=input()
    n=len(k)
    d=int(input())
    dp=[[[ModInt(0)]*2 for _ in range(d)] for _ in range(n+1)]
    dp[0][0][0]=1
    for i in range(n):
        a=int(k[i])
        for m in range(d):
            for j in range(10):
                if(j<a):
                    dp[i+1][(m+j)%d][1]+=dp[i][m][0]
                    dp[i+1][(m+j)%d][1]+=dp[i][m][1]
                elif(j==a):
                    dp[i+1][(m+j)%d][0]+=dp[i][m][0]
                    dp[i+1][(m+j)%d][1]+=dp[i][m][1]
                else:
                    dp[i+1][(m+j)%d][1]+=dp[i][m][1]
    print(dp[n][0][0]+dp[n][0][1]-1)
resolve()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
input=lambda :sys.stdin.buffer.readline().rstrip()
class ModInt(object):
    __MOD=10**9+7

    def __init__(self,x):
        self.__x=x%self.__MOD

    def __repr__(self):
        return str(self.__x)

    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,self.__MOD-2,self.__MOD)) if isinstance(other, ModInt) else ModInt(self.__x*pow(other, self.__MOD-2,self.__MOD))

    def __pow__(self,other):
        return ModInt(pow(self.__x,other.__x,self.__MOD)) if isinstance(other,ModInt) else ModInt(pow(self.__x,other,self.__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,self.__MOD-2,self.__MOD)) if isinstance(other,ModInt) else ModInt(other*pow(self.__x,self.__MOD-2,self.__MOD))

    def __rpow__(self,other):
        return ModInt(pow(other.__x,self.__x,self.__MOD)) if isinstance(other,ModInt) else ModInt(pow(other,self.__x,self.__MOD))

def resolve():
    k=input() # 1-indexed
    n=len(k)
    d=int(input())
    dp=[[[ModInt(0)]*2 for _ in range(d)] for _ in range(n+1)]
    dp[0][0][0]=1
    for i in range(n):
        a=int(k[i])
        for m in range(d):
            for j in range(10):
                dp[i+1][(m+j)%d][1]+=dp[i][m][1]
                if(j<a):
                    dp[i+1][(m+j)%d][1]+=dp[i][m][0]
                elif(j==a):
                    dp[i+1][(m+j)%d][0]+=dp[i][m][0]
                else:
                    continue
    print(dp[n][0][0]+dp[n][0][1]-1)
resolve()

Submission status: Wrong Answer

Solution code:
MOD = 10**9 + 7


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

    dp = [[[0 for i in range(b+1)] 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]) % MOD


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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
MOD = 10**9 + 7


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

    dp = [[[0 for i in range(b+1)] 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]) % MOD


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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
K = input()
D = int(input())
dp = [[0] * D for _ in range(len(K))]
mod = 10 ** 9 + 7
#桁DP
#0 ~ K[0] - 1までの数をトップとする場合
for i in range(int(K[0])):
  dp[0][i % D] += 1
#tightは上限付近の制御に使う
#K[0]をトップとする場合がtight
#tightは上限ギリギリを攻める
tight = int(K[0]) % D
if len(K) > 1:
  for i in range(len(K) - 1):
    for j in range(D):
      for k in range(10):
        dp[i + 1][(j + k) % D] += dp[i][j]
        dp[i + 1][(j + k) % D] %= mod
  #Kを超えないようにしている
  for k in range(int(K[i + 1])):
    dp[i + 1][(tight + k) % D] += 1
  #上からi桁まで見たもので、上限ギリギリのものの剰余
  tight = (tight + int(K[i + 1])) % D
#tightは最終的に上限の剰余に一致するので、0でないならその分を除く
print((dp[len(K) - 1][0] + (tight == 0) - 1) % mod)
#print(dp, tight)

Submission status: Wrong Answer

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

#memo = [[[-1 for k in range(2)] for j in range(D)] for i in range(N)]
@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) % MOD - 1
print(ans)

Submission status: Wrong Answer

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

#memo = [[[-1 for k in range(2)] for j in range(D)] for i in range(N)]
@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

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

Submission status: Wrong Answer

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)
        elif i == int(K[N-1-digit]):
            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) % MOD - 1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

import numpy as np
from numpy.fft import rfft, irfft
MOD = 10 ** 9 + 7
K = [int(x) for x in input().rstrip()]
L = len(K)
D = int(input())

fft_len = 1
while fft_len < 2*D:
    fft_len *= 2

def fft_convolve(A,B):
    return np.round(irfft(rfft(A,fft_len) * rfft(B,fft_len))).astype(np.int64) % MOD

def convolve(A,B):
    M = 1 << 16
    mask = M - 1
    A1,A2 = A>>16, A&mask
    B1,B2 = B>>16, B&mask
    X,Y,Z = [fft_convolve(P,Q) for P,Q in [[A1,B1],[A1-A2,B1-B2],[A2,B2]]]
    X = (X << 32) + ((X-Y+Z) << 16) + Z
    X[:D] += X[D:D+D]
    return X[:D] % MOD

# d桁以下、自由に使った場合の余りごとの個数。0を含めて数えておく
ones = [np.zeros(D,dtype=np.int64)]
for x in range(10):
    arr = ones[-1].copy()
    arr[x%D] += 1
    ones.append(arr)
full = []
dp = np.zeros(D, dtype=np.int64)
dp[0] = 1
full.append(dp)
for d in range(1,L):
    dp = convolve(dp,ones[10])
    full.append(dp)

dist = np.zeros(D+D, dtype=np.int64)

cumsum = 0
for i,x in enumerate(K):
    arr = convolve(ones[x], full[L-i-1])
    dist[cumsum:cumsum+D] += arr
    cumsum += x
    cumsum %= D

answer = dist[::D].sum() - 1 # 0除外
answer %= MOD
print(answer)

Submission status: Wrong Answer

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

lenn=len(k)
dp=[[0,0] for i in range(d)]
dp[0][0]=1
mod=1e9 +7

for pos in range(lenn):
    dp1=[[0,0] for i in range(d)]
    
    for summ in range(d):
        for chk in [0,1]:
            for dig in range(10):
                
                if(dig>int(k[pos]))and(chk==0):
                    break
                else:
                    
                    dp1[(summ+dig)%d][(chk)or(dig<(int(k[pos])))]+=dp[summ][chk]
                    dp1[(summ+dig)%d][(chk)or(dig<(int(k[pos])))]%=mod
                    
                                
    dp=dp1.copy()
    
    
ans=(dp[0][0]+dp[0][1])%mod
ans-=1
print(ans if ans != -1 else mod-1)

Submission status: Wrong Answer

Solution code:
r=range
M=10**9+7
n=input()
d=int(input())
dp=[[[0,0]for j in r(d)]for i in r(len(n)+1)]
dp[0][0][0]=1
for i,x in enumerate(map(int,n),1):
  for j in r(10):
    for k in r(d):
      dp[i][(j+k)%d][1]+=dp[i-1][k][1]
      dp[i][(j+k)%d][1]%=M
      if j<x:
        dp[i][(j+k)%d][1]+=dp[i-1][k][0]
        dp[i][(j+k)%d][1]%=M
      if j==x:
        dp[i][(j+k)%d][0]+=dp[i-1][k][0]
        dp[i][(j+k)%d][0]%=M
print(sum(dp[-1][0])%M-1)

Submission status: Wrong Answer

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

M = 10**9 + 7
K = int(input())
D = int(input())

dp = [[None] * 100 for _ in range(10**5 + 1)]
def f(k, i):
    if dp[i][k] is not None:
        return dp[i][k]

    if i == 0:
        r = (k % D) == 0
        dp[i][k] = r
        return r
    r = sum(f((k + x) % D, i - 1) for x in range(0, 10)) % M
    dp[i][k] = r
    return r

# dp = [[0] * 100 for _ in range(10**5 + 1)]
# for i in range(10**5 + 1):
#     for k in range(100):
#         if i == 0:
#             dp[i][k] = int((k % D) == 0)
#         else:
#             dp[i][k] = sum(dp[(k + x) % D][i - 1] for x in range(0, 10)) % M
#
# def f(k, i):
#     return dp[i][k]

sk = str(K)
dig = len(sk)
answer = 0
s = sum(map(int, list(sk)))
for j in range(int(sk[-1]) + 1):
    if (s - j) % D == 0:
        answer += 1

if dig > 1:
    s -= int(sk[-1])
    for i in range(dig - 1, 1, -1):
        if sk[i - 1] == "0":
            continue
        for j in range(int(sk[i - 1])):
            answer += f((s - 1) % D - j, dig - i)
        s -= int(sk[i - 1])

    for k in range(1, int(sk[0])):
        answer += f(k % D, dig - 1)

    if dig > 1: # 先頭0固定
        for k in range(10):
            answer += f(k % D, dig - 2)


print((answer - 1) % M)

Submission status: Wrong Answer

Solution code:
def make_dp(D,L):
    dp=[[0]*D for i in range(L+1)]
    for d in range(10):
        dp[0][d%D]+=1
            
    MOD=10**9+7
    for i in range(1,L+1):
        for d in range(D):
            for j in range(10):
                dp[i][d]+=dp[i-1][(d-j)%D]
                dp[i][d]%=MOD
    return dp
def find(s,D):
    MOD=10**9+7
    dp=make_dp(D,len(s))
    cur=0
    ans=0
    for i in range(len(s)):
        
        if i==len(s)-1:
            for j in range(0,int(s[i])+1):
                if (j+cur)%D==0:
                    ans+=1
            return ans%MOD
          
        
        
        for j in range(0,int(s[i])):
            #ans+=dp[len(s)-i-2][(j+cur)%MOD]
            #print("len(s)-i-2,(j+cur)%MOD)")
            #print(len(s)-i-2,(j+cur)%MOD)
            #ans%=MOD
            
            #print("dp[{}][{}]".format(len(s)-i-2,(D-cur-j)%D))
            ans+=dp[len(s)-i-2][(D-cur-j)%D]
            ans%=MOD
            #print("j,ans",j,ans)
        cur+=int(s[i])
        
        cur%=D
    
    return ans%MOD
def findout(s,D):
    tt=0
    temp_ans=0
    for x in s:
        tt+=int(x)
    if tt%D==0:
        temp_ans+=1
    MOD=10**9+7
    return (find(s,D)-1-temp_ans)%MOD
N=input()
K=int(input())
#N="1234"*1000
#k=100
print(findout(N,K))

Submission status: Wrong Answer

Solution code:
K = list(map(int, input().strip()))
D = int(input())
mod = 10**9+7

dp = [0]*D
dp[0] += 1
S = 0
for k in K:
    dp[S%D] -= 1
    dp2 = [0]*(D+10)
    for j, d in enumerate(dp):
        dp2[j] += d
        dp2[j+10] -= d
    for j in range(1, D+10):
        dp2[j] = (dp2[j-1] + dp2[j]) % mod
    for j in range(10):
        dp2[(D+j)%D] = (dp2[(D+j)%D] + dp2[D+j]) % mod 
    dp = dp2[:D]
    for j in range(k+1):
        dp[(S+j)%D] = (dp[(S+j)%D] + 1)%mod
    S += k
print(dp[0]-1)

Submission status: Wrong Answer

Solution code:
k = input()
d = int(input())
MOD = 10**9 + 7

# dp[i][is_smaller][summation % d]
dp = [[[0]*d for i in range(2)] for i in range(len(k)+1)]
dp[0][0][0] = 1

for i in range(len(k)):
    # is_smaller = 0 -> is_smaller = 0
    for l in range(d):
        dp[i+1][0][(l+int(k[i])) % d] += dp[i][0][l]
        dp[i+1][0][(l+int(k[i])) % d] %= MOD
        
    # is_smaller = 0 -> is_smaller = 1
    for l in range(d):
        for j in range(int(k[i])):
            dp[i+1][1][(l+j) % d] += dp[i][0][l]            
            dp[i+1][1][(l+j) % d] %= MOD    

    # is_smaller = 1 -> is_smaller = 1
    for l in range(d):
        for j in range(10):
            dp[i+1][1][(l+j) % d] += dp[i][1][l]
            dp[i+1][1][(l+j) % d] %= MOD

print(dp[len(k)][1][0] + dp[len(k)][0][0] - 1)

Submission status: Wrong Answer

Solution code:
K = list(map(int, list(input())))
D = int(input())
N = len(K)
dp = [[[0]*D for _ in range(2)] for _ in range(N+1)]
mod = 10**9+7
dp[0][0][0] = 1

for i in range(N):
    for smaller in range(2):
        for j in range(D):
            for x in range(10 if smaller else K[i]+1):
                dp[i+1][smaller or int(x < K[i])][j] = (dp[i+1][smaller or int(x < K[i])][j] + dp[i][smaller][(j-x)%D]) % mod

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

Submission status: Wrong Answer

Solution code:
K = list(map(int, list(input())))
D = int(input())
N = len(K)
dp = [[[0]*D for _ in range(2)] for _ in range(N+1)]
mod = 10**9+7
dp[0][0][0] = 1

for i in range(N):
    for smaller in range(2):
        for j in range(D):
            for x in range(10 if smaller else K[i]+1):
                dp[i+1][smaller or int(x < K[i])][j] = (dp[i+1][smaller or int(x < K[i])][j] + dp[i][smaller][(j-x)%D]) % mod

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

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!

MOD = 10**9+7

n=input()
D=int(input())

dp = [[[0 for _ in range(D)] for _ in range(2)] for _ in range(len(n)+1)] # 上からi桁まで、is_less, mod_D

dp[0][0][0] = 1
for i,ni in enumerate(n): #i桁目からi+1桁目に遷移
    ni = int(ni)
    for mod_d in range(D):
        for is_less in range(2):#1 なら真に小さい
            for d in range(10 if is_less else ni+1): # d: i+1桁目の数字
                dp[i+1][is_less or d < ni][(mod_d + d)%D] += dp[i][is_less][mod_d]
                dp[i+1][is_less or d < ni][(mod_d + d)%D] %= MOD
#    print(dp)

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

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)


def cnt(i, f, s):
    if i == n:
        if s:
            return 0
        else:
            return 1
    t = (i, f, s)
    if t in memo:
        return memo[t]
    if f:
        m = 10
        re = 0
    else:
        ki = int(k[i])
        m = ki
        re = cnt(i + 1, 0, (s + ki) % d)
    for j in range(m):
        re += cnt(i + 1, 1, (s + j) % d)
    memo[t] = re = re % md
    return re


md = 10 ** 9 + 7
memo = {}
k = input()
d = int(input())
n = len(k)
print(cnt(0, 0, 0) - 1)

Submission status: Wrong Answer

Solution code:
mod = 10**9 + 7

K = list(map(int, list(input())))
D = int(input())
keta = len(K)

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

from itertools import product
for i, j, k in product(range(keta), range(2), range(D)):
    max_n = K[i] if j else 9
    for l in range(max_n+1):
        dp[i+1][j and l == max_n][(k+l)%D] += dp[i][j][k]
        dp[i+1][j and l == max_n][(k+l)%D] %= mod

ans = 0
for i in range(2):
    ans += dp[-1][i][0]
    ans %= mod
print(max(0, ans - 1))

Submission status: Wrong Answer

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

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

for i in range(len(k)):
    for j in range(2):
        for m in range(d):
            if j == 1:
                for num in range(10):
                    dp[i+1][j][(m+num)%d] += dp[i][j][m]
                    dp[i+1][j][(m+num)%d] %= mod
            else:
                for num in range(int(k[i])+1):
                    if num != int(k[i]):
                        dp[i+1][1][(m+num)%d] += dp[i+1][j][m]
                        dp[i+1][1][(m+num)%d] %= mod
                    else:
                        dp[i+1][0][(m+num)%d] += dp[i+1][j][m]
                        dp[i + 1][0][(m + num) % d] %= mod

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

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(100000)
input=lambda : sys.stdin.readline().rstrip('\n')

s=list(map(int,input()))
d=int(input())
memo=[[[-1 for i in range(d)]for i in range(2)]for i in range(len(s)+1)]
def dgtdp(k=0,t=True,md=0):
    if memo[k][t][md]!=-1:
        return memo[k][t][md]
    if k==len(s):
        return md==0
    x=s[k]
    lim= x if t else 9
    ret=0
    for i in range(lim+1):
        ret+=dgtdp(k+1,t and (i==lim),(md+i)%d)
        ret%=10**9+7
    memo[k][t][md]=ret
    return ret

print(dgtdp()-1)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(100000)
input=lambda : sys.stdin.readline().rstrip('\n')

s=input()
d=int(input())
memo=[[[-1 for i in range(d)]for i in range(2)]for i in range(len(s)+1)]
def dgtdp(k=0,t=True,md=0):
    if memo[k][t][md]!=-1:
        return memo[k][t][md]
    if k==len(s):
        return md==0
    x=int(s[k])
    lim= x if t else 9
    ret=0
    for i in range(lim+1):
        ret+=dgtdp(k+1,t and (i==lim),(md+i)%d)
        ret%=10**9+7
    memo[k][t][md]=ret
    return ret

print(dgtdp()-1)

Submission status: Wrong Answer

Solution code:
K=int(input())
D=int(input())
def digisum(num):
  s='{}'.format(num)
  return sum(map(int,s))
cnt=0
for n in range(1,K+1):
  if digisum(n)%D==0:
    cnt+=1
print(cnt%(10e9+7))

Submission status: Wrong Answer

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

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

for i in range(length):
    for j in range(2):
        for k in range(D):
            if j == 1:
                x = 9
            else:
                x = int(K[i])
            for d in range(x + 1):
                dp[i + 1][j or d < x][(k + d) % D] += dp[i][j][k]
                dp[i + 1][j or d < x][(k + d) % D] %= mod
ans = 0
for i in range(2):
    ans += dp[length][i][0]

print(ans % mod - 1)

Submission status: Wrong Answer

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

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

for i in range(length):
    for j in range(2):
        for k in range(D):
            if j == 1:
                x = 9
            else:
                x = int(K[i])
            for d in range(x + 1):
                dp[i + 1][j or d < x][(k + d) % D] += dp[i][j][k]
ans = 0
for i in range(2):
    ans += dp[length][i][0]

print(ans % mod - 1)

Submission status: Wrong Answer

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

L=len(K)

DP=[[0]*D for i in range(2)]#DP[num][limit]で,一つ前の桁について,「桁和,そこまでKと一致していれば1」の場合の数


for j in range(10):
    if j>int(K[0]):
        continue
    if j==int(K[0]):
        DP[1][j%D]=1
    else:
        DP[0][j%D]=1
        


for keta in range(1,L):
    NDP=[[0]*D for i in range(2)]

    for i in range(D):
        for j in range(10):
            NDP[0][(i+j)%D]=(NDP[0][(i+j)%D]+DP[0][i])%mod

    for i in range(D):
        for j in range(10):
            if j>int(K[keta]):
                continue
            if j==int(K[keta]):
                NDP[1][(i+j)%D]=(NDP[1][(i+j)%D]+DP[1][i])%mod
            else:
                NDP[0][(i+j)%D]=(NDP[0][(i+j)%D]+DP[1][i])%mod

    DP=NDP

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

Submission status: Wrong Answer

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

L=len(K)

DP=[[0]*D for i in range(2)]#DP[num][limit]で,一つ前の桁について,「桁和,そこまでKと一致していれば1」の場合の数


for j in range(10):
    if j>int(K[0]):
        continue
    if j==int(K[0]):
        DP[1][j%D]=1
    else:
        DP[0][j%D]=1
        


for keta in range(1,L):
    NDP=[[0]*D for i in range(2)]

    for i in range(D):
        for j in range(10):
            NDP[0][(i+j)%D]=(NDP[0][(i+j)%D]+DP[0][i])%mod

    for i in range(D):
        for j in range(10):
            if j>int(K[keta]):
                continue
            if j==int(K[keta]):
                NDP[1][(i+j)%D]=(NDP[1][(i+j)%D]+DP[1][i])%mod
            else:
                NDP[0][(i+j)%D]=(NDP[0][(i+j)%D]+DP[1][i])%mod

    DP=NDP

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

Submission status: Wrong Answer

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

L=len(K)

DP=[[0]*D for i in range(2)]#DP[num][limit]で,一つ前の桁について,「桁和,そこまでKと一致していれば1」の場合の数


for j in range(10):
    if j>int(K[0]):
        continue
    if j==int(K[0]):
        DP[1][j%D]=1
    else:
        DP[0][j%D]=1
        


for keta in range(1,L):
    NDP=[[0]*D for i in range(2)]

    for i in range(D):
        for j in range(10):
            NDP[0][(i+j)%D]=(NDP[0][(i+j)%D]+DP[0][i])%mod

    for i in range(D):
        for j in range(10):
            if j>int(K[keta]):
                continue
            if j==int(K[keta]):
                NDP[1][(i+j)%D]=(NDP[1][(i+j)%D]+DP[1][i])%mod
            else:
                NDP[0][(i+j)%D]=(NDP[0][(i+j)%D]+DP[1][i])%mod

    DP=NDP

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

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
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 LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    k = S()
    d = I()
    t = [0] * d
    c = 0
    for i in k:
        i = int(i)
        u = t[:]
        for j in range(c,c+i):
            u[j%d] += 1
        c += i
        c %= d
        for j in range(max(0,d-10)):
            for jj in range(j+1,j+10):
                u[jj] += t[j]
            u[j] %= mod

        for j in range(max(0,d-10), d):
            for jj in range(j+1,j+10):
                u[jj%d] += t[j]
            u[j] %= mod
        t = u

    if c == 0:
        return t[0]

    return (t[0] - 1) % mod


print(main())

Submission status: Wrong Answer

Solution code:
# time complexity: O(DlgN)
# space complexity: O(DlgN)

import sys
fin = sys.stdin.readline

MOD = 10**9 + 7
N_list = tuple(list(fin())[:-1])
N = len(N_list)
D = int(fin())

# Python can't calculate this in 2 secs...
# dp_tight = tuple([[0] * N for _ in range(D)])
# dp_loose = tuple([[0] * N for _ in range(D)])

# def recurse(k = 0, tight = True, rem = 0):
#     if k == len(N_list):
#         return rem == 0

#     digit = int(N_list[k])
#     bound = digit if tight else 9
#     dp = dp_tight if tight else dp_loose
#     result = dp[rem][k]
#     if result:
#         return result

#     for i in range(bound + 1):
#         result += recurse(k + 1, tight and (i == bound), (rem + i) % D)
#         result %= MOD
#     dp[rem][k] = result
#     return result

# print(recurse() - 1) # to remove 0


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

dp[0][0][0] = 1
for i in range(N):
    for loose in range(2):
        bound = 9 if loose else int(N_list[i])
        for d in range(D):
            for num in range(bound + 1):
                dp[i+1][loose or num < bound][(d + num) % D] += dp[i][loose][d]
                dp[i+1][loose or num < bound][(d + num) % D] %= MOD
print(dp[-1][1][0] - 1)

Submission status: Wrong Answer

Solution code:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

SIZE = 10**5+1
MOD = 10**9+7
k = ns().zfill(SIZE)
d = ni()

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

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

for digit in range(SIZE):

    for num in range(10):
        if int(k[digit]) == num:
            for mod in range(d):
                dp[1][(mod+num)%d][digit+1] += dp[1][mod][digit]
                dp[1][(mod+num)%d][digit+1] %= MOD
        
        elif int(k[digit]) > num:
            for mod in range(d):
                dp[0][(mod+num)%d][digit+1] += dp[1][mod][digit]
                dp[0][(mod+num)%d][digit+1] %= MOD
        
        for mod in range(d):
            dp[0][(mod+num)%d][digit+1] += dp[0][mod][digit]
            dp[0][(mod+num)%d][digit+1] %= MOD

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
modi = 10**9+7
dp = {}
def getAns(num, pos, mod, L, d):
    
    if (num, pos, mod) in dp:
        return dp[(num, pos, mod)]

    if pos == L-1:
        ans = 0
        for i in range(int(num)+1):
            if i%d == mod: ans += 1
        return ans

    first = int(num[0])
    ans = 0
    upper = '9'*(len(num)-1)
    for i in range(first):
        ans = (ans+getAns(upper, pos+1, (10*d+mod-i)%d, L, d))%modi
    ans = (ans+getAns(num[1:], pos+1, (10*d+mod-first)%d, L, d))%modi

    dp[(num, pos, mod)] = ans

    return ans

k = input()
d = int(input())

print((getAns(k, 0, 0, len(k), d)-1)%modi)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
modi = 10**9+7
dp = {}
def getAns(num, pos, mod, L, d):
    
    if (num, pos, mod) in dp:
        return dp[(num, pos, mod)]

    if pos == L-1:
        ans = 0
        for i in range(int(num)+1):
            if i%d == mod: ans += 1
        return ans

    first = int(num[0])
    ans = 0
    for i in range(first):
        ans = (ans+getAns('9'*(len(num)-1), pos+1, (10*d+mod-i)%d, L, d))%modi
    ans = (ans+getAns(num[1:], pos+1, (10*d+mod-first)%d, L, d))%modi

    dp[(num, pos, mod)] = ans

    return ans

k = input()
d = int(input())

print((getAns(k, 0, 0, len(k), d)-1)%modi)