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:
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 = dp1.copy()

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] = (dp1[(l+j)%d]+dp2[l])%mod

        #上からi桁目でk以下が確定
        if j<li[i]:
            dp1[(mm1+j)%d] = (dp1[(mm1+j)%d]+1)%mod
    print(dp1)
    

    mm1 = (mm1+li[i])%d
    dp2 = dp1.copy()
    dp1 = [0 for _ in range(d)]


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

Submission status: Wrong Answer

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

li = list(map(int,(list(str(k)))))
leng = len(li)

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

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]

        #上からi桁目でk以下が確定
        if j<li[i]:
            dp1[(mm1+j)%d] += 1
    #print(dp1)
    

    mm1 = (mm1+li[i])%d
    dp2 = dp1.copy()
    dp1 = [0 for _ in range(d)]


print(dp2[0]-1)

Submission status: Wrong Answer

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
    K //= 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)

Submission status: Wrong Answer

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

mod = 10**9+7
N = len(K)
dp0 = [[0]*D for _ in range(N)]
dp1 = [[0]*D for _ in range(N)]

for k in range(int(K[0])):
    dp1[0][k%D] = 1
dp0[0][int(K[0])%D] = 1

for i in range(N-1):
    for j in range(D):
        for k in range(10):
            dp1[i+1][(j+k)%D] += dp1[i][j]
            dp1[i+1][(j+k)%D] %= mod
        for k in range(int(K[i+1])):
            dp1[i+1][(j+k)%D] += dp0[i][j]
            dp1[i+1][(j+k)%D] %= mod
        dp0[i+1][(j+int(K[i+1]))%D] += dp0[i][j]
        dp0[i+1][(j+int(K[i+1]))%D] %= mod

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

Submission status: Wrong Answer

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

l = len(k)

dp = [[0 for _ in range(d)] for _ in range(l+1)]
dp2 = [[0 for _ in range(d)] for _ in range(l+1)]

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

for i in range(1, l+1):
    if i == 1:
        for p in range(10):
            if p > int(k[i-1]):
                continue
            for j in range(d):
                if p < int(k[i-1]):
                    dp[i][(j+p) % d] += dp[i-1][j]
                    dp[i][(j+p) % d] %= mod
                elif p == int(k[i-1]):
                    dp2[i][(j+p) % d] += dp2[i-1][j]
                    dp2[i][(j+p) % d] %= mod
        continue

    for p in range(10):
        for j in range(d):
            dp[i][(j+p) % d] += dp[i-1][j]
            dp[i][(j+p) % d] %= mod

        if p > int(k[i-1]):
            continue

        for j in range(d):
            if p < int(k[i-1]):
                dp[i][(j+p) % d] += dp2[i-1][j]
                dp[i][(j+p) % d] %= mod
            elif p == int(k[i-1]):
                dp2[i][(j+p) % d] += dp2[i-1][j]
                dp2[i][(j+p) % d] %= mod

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

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")

MOD = 1000000007  # type: int


def array(*args, initial=0):
    def forstr(N):
        return "[{} for _ in range("+str(N)+")]"

    a = args[-1]
    ans = eval(forstr(a).format(initial))
    if len(args) == 1:
        return ans
    else:
        return array(*args[:-1], initial=ans)


def solve(K: int, D: int):
    K = str(K)
    N = len(str(K))
    DP = array(N+1, 2, D, initial=0)
    DP[0][0][0] = 1
    for i in range(N):
        for j in range(2):
            lim = 9 if j else int(K[i])
            for k in range(D):
                for d in range(lim+1):
                    DP[i+1][j or d < lim][(k+d) % D] += DP[i][j][k]
                    DP[i+1][j or d < lim][(k+d) % D] %= MOD
    print(DP[N][0][0]+DP[N][1][0]-1)

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    K = int(next(tokens))  # type: int
    D = int(next(tokens))  # type: int
    solve(K, D)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")

MOD = 1000000007  # type: int


def array(*args, initial=0):
    def forstr(N):
        return "[{} for _ in range("+str(N)+")]"

    a = args[-1]
    ans = eval(forstr(a).format(initial))
    if len(args) == 1:
        return ans
    else:
        return array(*args[:-1], initial=ans)


def solve(K: int, D: int):
    K = str(K)
    N = len(str(K))
    DP = array(N+1, 2, D, initial=0)
    DP[0][0][0] = 1
    for i in range(N):
        for j in range(2):
            if j:
                lim = 9
            else:
                lim = int(K[i])
            for k in range(D):
                for d in range(lim+1):
                    DP[i+1][j or d < lim][(k+d) % D] += DP[i][j][k]
                    DP[i+1][j or d < lim][(k+d) % D] %= MOD
    print(DP[N][0][0]+DP[N][1][0]-1)

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    K = int(next(tokens))  # type: int
    D = int(next(tokens))  # type: int
    solve(K, D)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np
k=input()
d=int(input())
m=10**9+7
t=np.zeros(d)
s=0
for i in k:
    p=np.zeros(d)
    for j in range(10):
        p+=np.hstack([t[-(j%d):],t[:-(j%d)]])
    for j in range(int(i)):
        p[(s+j)%d]+=1
    t=p[::]%m
    s+=int(i)
t[s%d]+=1
print(int(t[0])-1)

Submission status: Wrong Answer

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):
        for k in range(D):
            nk = (j+k)%D
            nY[nk] += Y[k]
        if j < c:
            nk = (j+a)%D
            nY[nk] = (nY[nk] + 1) % P
    
    a = (a+c) % D
    Y = nY
print((Y[0] - 1) % P)

Submission status: Wrong Answer

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

dp0 = [[0] * D for _ in range(N+1)]
dp1 = [[0] * D for _ in range(N+1)]
dp0[0][0] = 1
for i in range(N):
    k = int(K[i])
    for j in range(D):
        dp0[i+1][(j+k)%D] = dp0[i][j]
        dp1[i+1][(j+k)%D] = (dp1[i+1][(j+k)%D] + dp1[i][j]) % mod
        for k_ in range(k):
            dp1[i+1][(j+k_)%D] = (dp1[i+1][(j+k_)%D] + dp0[i][j] + dp1[i][j]) % mod
        for k_ in range(k+1, 10):
            dp1[i + 1][(j + k_) % D] = (dp1[i + 1][(j + k_) % D] + dp1[i][j]) % mod

print(dp0[-1][0] + dp1[-1][0] - 1)

Submission status: Wrong Answer

Solution code:
import sys
from math import log10, floor
K = int(sys.stdin.readline().strip())
d = int(input())
digit_num = floor(log10(K)) + 1
MOD = 10**9+7
# memo_ls[i][j][k] : 上からi桁目まででMODがjでflgがkの個数
memo_ls = [[[0 for _k in range(2)] for j in range(d)] for i in range(digit_num + 1)]
memo_ls[0][0][0] = 1
dic = {j : j % d for j in range(10)}
for i, n in enumerate(str(K), 1):
    n = int(n)
    for j in range(10):
        for k in range(d):
            _from = (k - j) % d
            memo_ls[i][k][1] = (memo_ls[i][k][1] + memo_ls[i-1][_from][1]) % MOD
            if j == n:
                memo_ls[i][k][0] = (memo_ls[i-1][_from][0] + memo_ls[i][k][0]) % MOD
            elif j < n:
                memo_ls[i][k][1] = (memo_ls[i-1][_from][0] + memo_ls[i][k][1]) % MOD
print((sum(memo_ls[-1][0]) - 1) % MOD)

Submission status: Wrong Answer

Solution code:
import sys
from math import log10, floor
K = int(sys.stdin.readline().strip())
d = int(input())
digit_num = floor(log10(K)) + 1
MOD = 10**9+7
# memo_ls[i][j][k] : 上からi桁目まででMODがjでflgがkの個数
memo_ls = [[[0 for _k in range(2)] for j in range(d)] for i in range(digit_num + 1)]
memo_ls[0][0][0] = 1
dic = {j : j % d for j in range(10)}
for i, n in enumerate(str(K), 1):
    n = int(n)
    for j in range(10):
        for k in range(d):
            _from = (k - j) % d
            memo_ls[i][k][1] = (memo_ls[i][k][1] + memo_ls[i-1][_from][1]) % MOD
            if j == n:
                memo_ls[i][k][0] = (memo_ls[i-1][_from][0] + memo_ls[i][k][0]) % MOD
            elif j < n:
                memo_ls[i][k][1] = (memo_ls[i-1][_from][0] + memo_ls[i][k][1]) % MOD
print(sum(memo_ls[-1][0]) % MOD - 1)

Submission status: Wrong Answer

Solution code:
import sys
from math import log10, floor
K = int(sys.stdin.readline().strip())
d = int(input())
digit_num = floor(log10(K)) + 1
MOD = 10**9+7
# memo_ls[i][j][k] : 上からi桁目まででMODがjでflgがkの個数
memo_ls = [[[0 for _k in range(2)] for j in range(d)] for i in range(digit_num + 1)]
memo_ls[0][0][0] = 1
dic = {j : j % d for j in range(10)}
for i, n in enumerate(str(K), 1):
    n = int(n)
    for j in range(10):
        for k in range(d):
            _from = (k - j) % d
            memo_ls[i][k][1] = (memo_ls[i][k][1] + memo_ls[i-1][_from][1]) % MOD
            if j == n:
                memo_ls[i][k][0] = (memo_ls[i-1][_from][0] + memo_ls[i][k][0]) % MOD
            elif j < n:
                memo_ls[i][k][1] = (memo_ls[i-1][_from][0] + memo_ls[i][k][1]) % MOD
print(sum(memo_ls[-1][0]) - 1)

Submission status: Wrong Answer

Solution code:
import sys
from math import log10, floor
K = int(sys.stdin.readline().strip())
d = int(input())
digit_num = floor(log10(K)) + 1
MOD = 10**9+7
# memo_ls[i][j][k] : 上からi桁目まででMODがjでflgがkの個数
memo_ls = [[[0 for _k in range(2)] for j in range(d)] for i in range(digit_num + 1)]
memo_ls[0][0][0] = 1
dic = {j : j % d for j in range(10)}
for i, n in enumerate(str(K), 1):
    n = int(n)
    for j in range(10):
        for k in range(d):
            _from = (k - j) % d
            if j == n:
                memo_ls[i][k][0] += memo_ls[i-1][_from][0]
                memo_ls[i][k][1] += memo_ls[i-1][_from][1]
            elif j < n:
                memo_ls[i][k][1] += memo_ls[i-1][_from][1] + memo_ls[i-1][_from][0]
            else:
                memo_ls[i][k][1] += memo_ls[i - 1][_from][1]
            memo_ls[i][k][0] %= MOD
            memo_ls[i][k][1] %= MOD
print(sum(memo_ls[-1][0]) - 1)

Submission status: Wrong Answer

Solution code:
import sys
from math import log10, floor
K = int(sys.stdin.readline().strip())
d = int(input())
digit_num = floor(log10(K)) + 1
MOD = 10**9+7
# memo_ls[i][j][k] : 上からi桁目まででMODがjでflgがkの個数
memo_ls = [[[0 for _k in range(2)] for j in range(d)] for i in range(digit_num + 1)]
memo_ls[0][0][0] = 1
dic = {j : j % d for j in range(10)}
for i, n in enumerate(str(K), 1):
    n = int(n)
    for j in range(10):
        x = dic[j]
        for k in range(d):
            _from = k - x if k - x >= 0 else d + k - x
            if j == n:
                memo_ls[i][k][0] += memo_ls[i-1][_from][0]
                memo_ls[i][k][1] += memo_ls[i-1][_from][1]
            elif j < n:
                memo_ls[i][k][1] += memo_ls[i-1][_from][1] + memo_ls[i-1][_from][0]
            else:
                memo_ls[i][k][1] += memo_ls[i - 1][_from][1]
            memo_ls[i][k][0] %= MOD
            memo_ls[i][k][1] %= MOD
print(sum(memo_ls[-1][0]) - 1)

Submission status: Wrong Answer

Solution code:
import sys
from math import log10, floor
k = int(sys.stdin.readline().strip())
d = int(input())
digit_num = floor(log10(k)) + 1
MOD = 10**9+7
# memo_ls[i][j][k] : 上からi桁目まででMODがjでflgがkの個数
memo_ls = [[[0 for _k in range(2)] for j in range(d)] for i in range(digit_num + 1)]
memo_ls[0][0][0] = 1
dic = {j : j % d for j in range(10)}
for i, n in enumerate(str(k), 1):
    n = int(n)
    for j in range(10):
        x = dic[j]
        for k in range(d):
            _from = k - x if k - x >= 0 else d + k - x
            if j == n:
                memo_ls[i][k][0] += memo_ls[i-1][_from][0]
                memo_ls[i][k][1] += memo_ls[i-1][_from][1]
            elif j < n:
                memo_ls[i][k][1] += memo_ls[i-1][_from][1] + memo_ls[i-1][_from][0]
            else:
                memo_ls[i][k][1] += memo_ls[i - 1][_from][1]
            memo_ls[i][k][0] %= MOD
            memo_ls[i][k][1] %= MOD
print(sum(memo_ls[-1][0]) - 1)

Submission status: Wrong Answer

Solution code:
import sys
from math import log10, floor
k = int(sys.stdin.readline().strip())
d = int(input())
digit_num = floor(log10(k)) + 1
MOD = 10**9+7
# memo_ls[i][j][k] : 上からi桁目まででMODがjでflgがkの個数
memo_ls = [[[0 for k in range(2)] for j in range(d)] for i in range(digit_num + 1)]
memo_ls[0][0][0] = 1
dic = {j : j % d for j in range(10)}
for i, n in enumerate(str(k), 1):
    n = int(n)
    for j in range(10):
        x = dic[j]
        for k in range(d):
            _from = k - x if k - x >= 0 else d + k - x
            if j == n:
                memo_ls[i][k][0] += memo_ls[i-1][_from][0]
                memo_ls[i][k][1] += memo_ls[i-1][_from][1]
            elif j < n:
                memo_ls[i][k][1] += memo_ls[i-1][_from][1] + memo_ls[i-1][_from][0]
            else:
                memo_ls[i][k][1] += memo_ls[i - 1][_from][1]
            memo_ls[i][k][0] %= MOD
            memo_ls[i][k][1] %= MOD
print(sum(memo_ls[-1][0]) - 1)

Submission status: Wrong Answer

Solution code:
import sys
from math import log10, floor
k = int(sys.stdin.readline().strip())
d = int(input())
digit_num = floor(log10(k)) + 1
MOD = 10**9+7
# memo_ls[i][j][k] : 上からi桁目まででMODがjでflgがkの個数
memo_ls = [[[0 for k in range(2)] for j in range(d)] for i in range(digit_num + 1)]
memo_ls[0][0][0] = 1
for i, n in enumerate(str(k), 1):
    for j in range(10):
        x = j % d
        for k in range(d):
            _from = k - x if k - x >= 0 else d + k - x
            if j == int(n):
                memo_ls[i][k][0] += memo_ls[i-1][_from][0]
                memo_ls[i][k][1] += memo_ls[i-1][_from][1]
            elif j < int(n):
                memo_ls[i][k][1] += memo_ls[i-1][_from][1] + memo_ls[i-1][_from][0]
            else:
                memo_ls[i][k][1] += memo_ls[i - 1][_from][1]
            memo_ls[i][k][0] %= MOD
            memo_ls[i][k][1] %= MOD
print(sum(memo_ls[-1][0]) - 1)

Submission status: Wrong Answer

Solution code:
from math import log10, floor
k = int(input())
d = int(input())
digit_num = floor(log10(k)) + 1
MOD = 10**9+7
# memo_ls[i][j][k] : 上からi桁目まででMODがjでflgがkの個数
memo_ls = [[[0 for k in range(2)] for j in range(d)] for i in range(digit_num + 1)]
memo_ls[0][0][0] = 1
for i, n in enumerate(str(k), 1):
    for j in range(10):
        x = j % d
        for k in range(d):
            _from = k - x if k - x >= 0 else d + k - x
            if j == int(n):
                memo_ls[i][k][0] += memo_ls[i-1][_from][0]
                memo_ls[i][k][1] += memo_ls[i-1][_from][1]
            elif j < int(n):
                memo_ls[i][k][1] += memo_ls[i-1][_from][1] + memo_ls[i-1][_from][0]
            else:
                memo_ls[i][k][1] += memo_ls[i - 1][_from][1]
            memo_ls[i][k][0] %= MOD
            memo_ls[i][k][1] %= MOD
print(sum(memo_ls[-1][0]) - 1)

Submission status: Wrong Answer

Solution code:
MOD=1000000007
K=input()
n=len(K)
D=int(input())

dp=[[[0,0] for j in range(D)] for i in range(10005)]
dp[0][0][1]=1

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

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    md = 10 ** 9 + 7
    k = [int(c) for c in input()]
    n=len(k)
    d = int(input())
    dp = [[0] * d for _ in range(n)]
    # dp[0]=1
    for b in range(k[0]):
        dp[0][b % d] = 1
    border = k[0]
    dpi = dp[0]
    for i, a in enumerate(k[1:], 1):
        dpi1 = dpi
        dpi = dp[i]
        for j in range(d):
            pre = dpi1[j]
            if pre == 0: continue
            for b in range(10):
                nj = (j + b) % d
                dpi[nj] = (dpi[nj] + pre) % md
        for b in range(a):
            nj = (border + b) % d
            dpi[nj] += 1
        border = (border + a) % d

    #p2D(dp)
    ans = dp[n-1][0] - 1 + (border % d == 0)
    print(ans % md)

main()

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    md = 10 ** 9 + 7
    k = [int(c) for c in input()]
    d = int(input())
    dp = [[0] * d for _ in range(len(k))]
    # dp[0]=1
    for b in range(k[0]):
        dp[0][b % d] = 1
    border = k[0]
    dpi = dp[0]
    for i, a in enumerate(k[1:], 1):
        dpi1 = dpi
        dpi = dp[i]
        for j in range(d):
            pre = dpi1[j]
            if pre == 0: continue
            for b in range(10):
                nj = (j + b) % d
                dpi[nj] = (dpi[nj] + pre) % md
        for b in range(a):
            nj = (border + b) % d
            dpi[nj] += 1
        border = (border + a) % d

    #p2D(dp)
    ans = dp[-1][0] - 1 + (border % d == 0)
    print(ans % md)

main()

Submission status: Wrong Answer

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

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()
    d=int(input())
    n=len(k)
    dp=[[[ModInt(0)]*2 for _ in range(d)] for _ in range(n+1)]
    dp[0][0][0]=ModInt(1)
    from itertools import product
    for i in range(n):
        a=int(k[i])
        for m,l,b in product(range(d),range(2),range(10)):
            nm,nl=(m+b)%d,l
            if((not l) and (b>a)): continue
            if(a>b): nl=1
            dp[i+1][nm][nl]+=dp[i][m][l]
    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()
    d=int(input())
    n=len(k)
    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 j in range(d):
            for o in range(10):
                dp[i+1][(j+o)%d][1]+=dp[i][j][1]
                if(o<a): dp[i+1][(j+o)%d][1]+=dp[i][j][0]
                elif(o==a): dp[i+1][(j+o)%d][0]+=dp[i][j][0]
    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")
MOD=10**9+7
input=lambda :sys.stdin.buffer.readline().rstrip()
def resolve():
    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):
        a=int(k[i])
        for j in range(d):
            for o in range(10):
                dp[i+1][(j+o)%d][1]+=dp[i][j][1]
                dp[i+1][(j+o)%d][1]%=MOD
                if(o<a):
                    dp[i+1][(j+o)%d][1]+=dp[i][j][0]
                    dp[i+1][(j+o)%d][1]%=MOD
                elif(o==a):
                    dp[i+1][(j+o)%d][0]+=dp[i][j][0]
                    dp[i+1][(j+o)%d][0]%=MOD
    print((dp[n][0][0]+dp[n][0][1]-1)%MOD)
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()
    d=int(input())
    n=len(k)
    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 j in range(d):
            for o in range(10):
                dp[i+1][(j+o)%d][1]+=dp[i][j][1]
                if(o<a): dp[i+1][(j+o)%d][1]+=dp[i][j][0]
                elif(o==a): dp[i+1][(j+o)%d][0]+=dp[i][j][0]
    print((dp[n][0][0]+dp[n][0][1]-1)._ModInt__x)
resolve()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
input=lambda :sys.stdin.buffer.readline().rstrip()
MOD=10**9+7
class ModInt:
    def __init__(self, x):
        self.x = x % MOD

    def __str__(self):
        return str(self.x)

    __repr__ = __str__

    def __add__(self, other):
        return (
            ModInt(self.x + other.x) if isinstance(other, ModInt) else
            ModInt(self.x + other)
        )

    def __sub__(self, other):
        return (
            ModInt(self.x - other.x) if isinstance(other, ModInt) else
            ModInt(self.x - other)
        )

    def __mul__(self, other):
        return (
            ModInt(self.x * other.x) if isinstance(other, ModInt) else
            ModInt(self.x * other)
        )

    def __truediv__(self, other):
        return (
            ModInt(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(self.x * pow(other, MOD - 2, MOD))
        )

    def __pow__(self, other):
        return (
            ModInt(pow(self.x, other.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(self.x, other, MOD))
        )

    __radd__ = __add__

    def __rsub__(self, other):
        return (
            ModInt(other.x - self.x) if isinstance(other, ModInt) else
            ModInt(other - self.x)
        )

    __rmul__ = __mul__

    def __rtruediv__(self, other):
        return (
            ModInt(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, ModInt) else
            ModInt(other * pow(self.x, MOD - 2, MOD))
        )

    def __rpow__(self, other):
        return (
            ModInt(pow(other.x, self.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(other, self.x, MOD))
        )

def resolve():
    k=input()
    d=int(input())
    n=len(k)
    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 j in range(d):
            for o in range(10):
                dp[i+1][(j+o)%d][1]+=dp[i][j][1]
                if(o<a): dp[i+1][(j+o)%d][1]+=dp[i][j][0]
                elif(o==a): dp[i+1][(j+o)%d][0]+=dp[i][j][0]
    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()
    d=int(input())
    n=len(k)
    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 j in range(d):
            for o in range(10):
                dp[i+1][(j+o)%d][1]+=dp[i][j][1]
                if(o<a): dp[i+1][(j+o)%d][1]+=dp[i][j][0]
                elif(o==a): dp[i+1][(j+o)%d][0]+=dp[i][j][0]
    print(dp[n][0][0]+dp[n][0][1]-1)
resolve()