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:
#!/usr/bin/env python3

#from collections import defaultdict
#from heapq import heappush, heappop
import sys

sys.setrecursionlimit(10**6)
input = sys.stdin.buffer.readline
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")
MOD = 10 ** 9 + 7


def debug(*x):
    print(*x, file=sys.stderr)


def solve(K, D):
    K = [x - ord("0") for x in K]
    N = len(K)
    less = [[0] * D for i in range(N)]
    border = 0

    for i in range(N):
        for j in range(10):
            for d in range(D):
                less[i][(d + j) % D] += less[i - 1][d]
                less[i][(d + j) % D] %= MOD
            if j < K[i]:
                less[i][(border + j) % D] += 1
        border += K[i]
        border %= D

    ret = less[-1][0] - 1
    ret += (border == 0)
    return ret % MOD


def main():
    # parse input
    K = input().strip()
    D = int(input())
    print(solve(K, D))


# tests
T1 = """
30
4
"""


def test_T1():
    """
    >>> as_input(T1)
    >>> main()
    6
    """


T2 = """
1000000009
1
"""


def test_T2():
    """
    >>> as_input(T2)
    >>> main()
    2
    """


T3 = """
98765432109876543210
58
"""


def test_T3():
    """
    >>> as_input(T3)
    >>> main()
    635270834
    """

# add tests above


def _test():
    import doctest
    doctest.testmod()


def as_input(s):
    "use in test, use given string as input file"
    import io
    global read, input
    f = io.StringIO(s.strip())

    def input():
        return bytes(f.readline(), "ascii")

    def read():
        return bytes(f.read(), "ascii")


USE_NUMBA = False
if (USE_NUMBA and sys.argv[-1] == 'ONLINE_JUDGE') or sys.argv[-1] == '-c':
    print("compiling")
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('solve', solve.__doc__.strip().split()[0])(solve)
    cc.compile()
    exit()
else:
    input = sys.stdin.buffer.readline
    read = sys.stdin.buffer.read

    if (USE_NUMBA and sys.argv[-1] != '-p') or sys.argv[-1] == "--numba":
        # -p: pure python mode
        # if not -p, import compiled module
        from my_module import solve  # pylint: disable=all
    elif sys.argv[-1] == "-t":
        print("testing")
        _test()
        sys.exit()
    elif sys.argv[-1] != '-p' and len(sys.argv) == 2:
        # input given as file
        input_as_file = open(sys.argv[1])
        input = input_as_file.buffer.readline
        read = input_as_file.buffer.read

    main()

Submission status: Wrong Answer

Solution code:
k = input()
d = int(input())
mod = 10**9+7
if d == 1:
    print(int(k)%mod)
    exit()
dp = [[[0]*2 for i in range(d)] for j in range(len(k))]
## dp[][][0] k 以下確定 [1] 未定

s = int(k[0])
dp[0][s%d][1] = 1
for i in range(s%d):
    dp[0][i][0] = 1

for i in range(1,len(k)):
    s = int(k[i])
    for j in range(10):
        for m in range(d):
            if s == j:
                dp[i][(m+j)%d][1] += dp[i-1][m][1]
                dp[i][(m+j)%d][1] %= mod
            elif s > j:
                dp[i][(m+j)%d][0] += dp[i-1][m][1]
                dp[i][(m+j)%d][0] %= mod
            dp[i][(m+j)%d][0] += dp[i-1][m][0]
            dp[i][(m+j)%d][0] %= mod
ans = sum(dp[-1][0])

print((ans-1)%mod)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(100000000)
MOD = 10 ** 9 + 7

def main():
    K = input()
    D = int(input())

    dp = [[[0]*2 for _ in range(D)] for _ in range(len(K) + 1)] 
    dp[0][0][0] = 1
    for i in range(len(K)):
        M = int(K[i])
        for j in range(D):
            for k in range(10):
                if k < M:
                    dp[i + 1][(j + k)%D][1] += dp[i][j][1] + dp[i][j][0]
                elif k == M:
                    dp[i + 1][(j + k)%D][1] += dp[i][j][1]
                    dp[i + 1][(j + k)%D][0] += dp[i][j][0]
                else:
                    dp[i + 1][(j + k)%D][1] += dp[i][j][1]
                dp[i + 1][(j + k)%D][0] %= MOD
                dp[i + 1][(j + k)%D][1] %= MOD
    ans = sum(dp[-1][0])
    print((ans)%MOD)       
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(100000000)
MOD = 10 ** 9 + 7

def main():
    K = input()
    D = int(input())

    dp = [[[0]*2 for _ in range(D)] for _ in range(len(K) + 1)] 
    dp[0][0][0] = 1
    for i in range(len(K)):
        M = int(K[i])
        for j in range(D):
            for k in range(10):
                if k < M:
                    dp[i + 1][(j + k)%D][1] += dp[i][j][1] + dp[i][j][0]
                elif k == M:
                    dp[i + 1][(j + k)%D][1] += dp[i][j][1]
                    dp[i + 1][(j + k)%D][0] += dp[i][j][0]
                #else:
                    #dp[i + 1][(j + k)%D][1] += dp[i][j][1]
                dp[i + 1][(j + k)%D][0] %= MOD
                dp[i + 1][(j + k)%D][1] %= MOD
    ans = sum(dp[-1][0])
    print((ans - 1)%MOD)       
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
K=input()
N=len(K)
D=int(input())
import numpy as np
d=np.zeros((N+1,D),dtype=np.int64)
d2=np.zeros((N+1,D),dtype=np.int64)
d[0,0]=1
m=10**9+7
for i in range(N):
    d[i+1]=np.roll(d[i],int(K[i]))
    for j in range(10):
        d2[i+1]+=np.roll(d2[i],j)
    for j in range(int(K[i])):
        d2[i+1]+=np.roll(d[i],j)
    d2[i+1]%=m
print(d[-1,0]+d2[-1,0]-1)

Submission status: Wrong Answer

Solution code:
from sys import stdin, stdout, setrecursionlimit
from collections import deque, defaultdict
from functools import lru_cache

rl = lambda: stdin.readline()
rll = lambda: stdin.readline().split()
rli = lambda: map(int, stdin.readline().split())

INF, NINF = float('inf'), float('-inf')

setrecursionlimit(100000)

def main():
	MOD = 10**9 + 7
	k, d = int(rl()), int(rl())
	ans = 0

	def totup(num):
		ans = deque()
		while num:
			num, dig = divmod(num, 10)
			ans.appendleft(dig)
		return tuple(ans)

	x = totup(k)

	dp = [[[0]*2 for j in range(d)] for i in range(len(x)+1)]
	dp[0][0][1] = 1
	for i in range(len(x)):
		for digsum in range(d):
			for tight in range(2):
				for dig in range(x[i]+1 if tight else 10):
					dp[i+1][(digsum + dig) % d][1 if tight and dig == x[i] else 0] += dp[i][digsum][tight] % MOD

	ans = (dp[len(x)][0][0] + dp[len(x)][0][1]) % MOD
	print(ans - 1)
	stdout.close()

if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
k = input()
D = int(input())
mod = 10 ** 9 + 7
keta = len(k)
dp = [[[0] * (2) for _ in range(D)] for _ in range(keta + 1)]
# dp[keta][D][smaler]
dp[0][0][0] = 1
for i in range(keta):
    num = int(k[i])
    for j in range(D):
        for smaller in range(2):
            for d in range(10):
                ni = i + 1
                nsmaller = smaller
                nj = (j + d) % D
                if smaller == 0:
                    if d < num:
                        nsmaller = 1
                    if d > num:
                        continue
                dp[ni][nj][nsmaller] += dp[i][j][smaller]
                dp[ni][nj][nsmaller] %= mod
print(dp[keta][0][1] + dp[keta][0][0] - 1)

Submission status: Wrong Answer

Solution code:
k = input()
D = int(input())
mod = 10 ** 9 + 7
keta = len(k)
dp = [[[0] * (2) for _ in range(D)] for _ in range(keta + 1)]
# dp[keta][d][smaler]
dp[0][0][0] = 1
for i in range(keta):
    num = int(k[i])
    for j in range(D):
        for smaller in range(2):
            for d in range(10):
                ni = i + 1
                nsmaller = smaller
                nj = (j + d) % D
                if smaller == 0:
                    if d < num:
                        nsmaller = 1
                    if d > num:
                        continue
                dp[ni][nj][nsmaller] += dp[i][j][smaller]
                dp[ni][nj][nsmaller] %= mod
print(dp[keta][0][1] + dp[keta][0][0] - 1)

Submission status: Wrong Answer

Solution code:
import sys

stdin = sys.stdin
inf = 1 << 60
mod = 1000000007

ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

k = ni()
s = str(k)
n = len(s)
d = ni()

dp = [[[0] * 2 for _ in range(d + 1)] for _ in range(n + 1)]
dp[0][0][0] = 1
for i in range(n):
    for j in range(d):
        for k in range(2):
            dmax = 9 if k else int(s[i])
            for D in range(dmax + 1):
                ni = i + 1
                nj = (j + D) % d
                nk = k | (D < dmax)
                dp[ni][nj][nk] += dp[i][j][k]
                dp[ni][nj][nk] %= mod

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

Submission status: Wrong Answer

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

def main():
    N = input()
    D = int(input())
    L = len(N)
    md = 10**9+7
    #dp[i][j][st]   i文字目で余りがjであり、st=1 未満が確定
    dp = [[[0] * 2 for j in range(D)] for i in range(L+1)]
    dp[0][0][0] = 1
    for i in range(L):              #使用する文字数
        n = int(N[i])
        i_ = i+1
        for j in range(D):          #あまり
            for k in range(10): #選ぶ文字
                j_ = (j + k)%D
                dp[i_][j_][1] += dp[i][j][1]
                dp[i_][j_][1] %= md
                if k<n:
                    dp[i_][j_][1] += dp[i][j][0]
                    dp[i_][j_][1] %= md
                if k==n:
                    dp[i_][j_][0] += dp[i][j][0]
                    dp[i_][j_][0] %= md

    print(sum(dp[L][0])-1)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N = [int(n) for n in list(input())]
d = int(input())
p = 10**9+7
DP = [[0]*d, [0]*d]
DP[1][0] = 1
for n in N:
    DP_ = [[0]*d, [0]*d]
    for i in range(2):
        for j in range(d):
            for k in range(n+i):
                DP_[i][j] += DP[1][(j-k) % d] % p
            for k in range(n+i, 10):
                DP_[i][j] += DP[0][(j-k) % d] % p
            DP_[i][j] %= p
    DP = DP_
print(DP[1][0] % p - 1)

Submission status: Wrong Answer

Solution code:
N = [int(n) for n in list(input())]
d = int(input())
p = 10**9+7
DP = [[0]*d, [0]*d]
DP[1][0] = 1
for n in N:
    DP_ = [[0]*d, [0]*d]
    for i in range(2):
        for j in range(d):
            for k in range(n+i):
                DP_[i][j] += DP[1][(j-k) % d]
            for k in range(n+i, 10):
                DP_[i][j] += DP[0][(j-k) % d]
    DP = DP_
print(DP[1][0] % p - 1)

Submission status: Wrong Answer

Solution code:
n = int(input())
d = int(input())
p = 10**9+7
if d == 1:
    print(n % p)
    exit()
N = [int(i) for i in list(str(n))]
DP0 = [0] * d
DP1 = [0] * d
DP1[0] += 1
for i in N:
    DP0_ = [0] * d
    DP1_ = [0] * d
    for r in range(d):
        for j in range(i):
            DP0_[r] += DP1[(r-j) % d]
            DP1_[r] += DP1[(r-j) % d]
        DP0_[r] += DP0[(r-i) % d]
        DP1_[r] += DP1[(r-i) % d]
        for j in range(i+1, 10):
            DP0_[r] += DP0[(r-j) % d]
            DP1_[r] += DP0[(r-j) % d]
        DP0_[r], DP1_[r] = DP0_[r] % p, DP1_[r] % p
    DP0, DP1 = DP0_, DP1_
print(DP1[0]-1)

Submission status: Wrong Answer

Solution code:
n = int(input())
d = int(input())
p = 10**9+7
if d == 1:
    print(n % p)
    exit()
N = [int(i) for i in list(str(n))]
DP0 = [0] * d
DP1 = [0] * d
DP1[0] += 1
for i in N:
    DP0_ = [0] * d
    DP1_ = [0] * d
    for r in range(d):
        for j in range(i):
            DP0_[r] += DP1[(r-j) % d]
        for j in range(i, 10):
            DP0_[r] += DP0[(r-j) % d]
        for j in range(i+1):
            DP1_[r] += DP1[(r-j) % d]
        for j in range(i+1, 10):
            DP1_[r] += DP0[(r-j) % d]
        DP0_[r], DP1_[r] = DP0_[r] % p, DP1_[r] % p
    DP0, DP1 = DP0_, DP1_
print(DP1[0]-1)

Submission status: Wrong Answer

Solution code:
n = int(input())
d = int(input())
p = 10**9+7
if d == 1:
    print(n % d)
    exit()
N = [int(i) for i in list(str(n))]
DP0 = [0] * d
DP1 = [0] * d
DP1[0] += 1
for i in N:
    DP0_ = [0] * d
    DP1_ = [0] * d
    for r in range(d):
        for j in range(i):
            DP0_[r] += DP1[(r-j) % d]
        for j in range(i, 10):
            DP0_[r] += DP0[(r-j) % d]
        for j in range(i+1):
            DP1_[r] += DP1[(r-j) % d]
        for j in range(i+1, 10):
            DP1_[r] += DP0[(r-j) % d]
        DP0_[r], DP1_[r] = DP0_[r] % p, DP1_[r] % p
    DP0, DP1 = DP0_, DP1_
print(DP1[0]-1)

Submission status: Wrong Answer

Solution code:
n = int(input())
d = int(input())
p = 10**9+7
N = [int(i) for i in list(str(n))]
DP = [[[0 for j in range(d)]for i in range(len(N))] for _ in range(2)]
for i in range(len(N)):
    if i == 0:
        for j in range(d):
            for k in range(N[i]):
                if k % d == j:
                    DP[0][i][j] += 1
                    DP[1][i][j] += 1
            if N[i] % d == j:
                DP[1][i][j] += 1
    else:
        for j in range(d):
            for k in range(N[i]):
                DP[0][i][j] += DP[1][i-1][(j-k) % d]
            for k in range(N[i], 10):
                DP[0][i][j] += DP[0][i-1][(j-k) % d]
            for k in range(N[i]+1):
                DP[1][i][j] += DP[1][i-1][(j-k) % d]
            for k in range(N[i]+1, 10):
                DP[1][i][j] += DP[1][i-1][(j-k) % d]
print((DP[1][-1][0]-1)%p)

Submission status: Wrong Answer

Solution code:
n = int(input())
d = int(input())
p = 10**9+7
N = [int(i) for i in list(str(n))]
X = [sum([1 for k in range(N[0]) if k % d == j]) for j in range(d)]
Y = [sum([1 for k in range(N[0]+1) if k % d == j]) for j in range(d)]
for i in range(1, len(N)):
    r = N[i]-1
    X_ = [0]*d
    for j in range(d):
        x = 0
        for k in range(r+1):
            x += Y[(j-k) % d]
        for k in range(r+1, 10):
            x += X[(j-k) % d]
        X_[j] = x % p
    r += 1
    Y_ = [0]*d
    for j in range(d):
        y = 0
        for k in range(r+1):
            y += Y[(j-k) % d]
        for k in range(r+1, 10):
            y += X[(j-k) % d]
        Y_[j] = y % p
    X, Y = X_, Y_
print(Y[0]-1)

Submission status: Wrong Answer

Solution code:
d = int(input())
n = int(input())
p = 10**9+7
N = [int(i) for i in list(str(n))]
X = [sum([1 for k in range(N[0]) if k % d == j]) for j in range(d)]
Y = [sum([1 for k in range(N[0]+1) if k % d == j]) for j in range(d)]
for i in range(1, len(N)):
    r = N[i]-1
    X_ = [0]*d
    for j in range(d):
        x = 0
        for k in range(r+1):
            x += Y[(j-k) % d]
        for k in range(r+1, 10):
            x += X[(j-k) % d]
        X_[j] = x % p
    r += 1
    Y_ = [0]*d
    for j in range(d):
        y = 0
        for k in range(r+1):
            y += Y[(j-k) % d]
        for k in range(r+1, 10):
            y += X[(j-k) % d]
        Y_[j] = y % p
    X, Y = X_, Y_
print(Y[0]-1)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

from collections import Counter

rl = Counter()
r = Counter()
rl[0] = 1

M = 10**9 + 7
for c in K:
    d = int(c)
    rln = Counter()
    rn = Counter()
    for rem, count in rl.items():
        rln[(rem + d) % D] += count
        rln[(rem + d) % D] %= M

    for rem, count in rl.items():
        for i in range(d):
            rn[(rem + i) % D] += count
            rn[(rem + i) % D] %= M
    for rem, count in r.items():
        for i in range(10):
            rn[(rem + i) % D] += count
            rn[(rem + i) % D] %= M
    rl = rln
    r = rn

print(rl[0] + r[0] - 1)

Submission status: Wrong Answer

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

import random
string = str(10**10000)
# d = random.randint(1, 9)
# print(string, d)

nums = [int(v) for v in string]
length = len(string) - 1
k = int(string)

M = 10**9 + 7
def mod(v):
    if v >= M:
        return v % M
    return v

dp = [[[None] * 2 for _ in range(d)] for _ in range(length + 2)]
def dfs(i=0, s=0, border=True):
    if dp[i][s][border] is not None:
        return dp[i][s][border]

    if i > length:
        r = int(not bool(s))
        dp[i][s][border] = r
        return r

    cnt = 0
    for n in range(max(9 * (not border), nums[i]) + 1):
        cnt = mod(cnt + dfs(i + 1, (s + n) % d, border and nums[i] == n))
    dp[i][s][border] = cnt
    return cnt
# print(mod(dfs() - 1))

for i in reversed(range(length + 2)):
    for s in reversed(range(d)):
        for border in [False, True]:
            if i > length:
                dp[i][s][border] = int(not bool(s))
                continue

            cnt = 0
            for n in range(max(9 * (not border), nums[i]) + 1):
                cnt = mod(cnt + dp[i + 1][(s + n) % d][border and nums[i] == n])
            dp[i][s][border] = cnt

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

Submission status: Wrong Answer

Solution code:
# import sys
# sys.setrecursionlimit(10**6 * 2 + 1)
string = input()
nums = [int(v) for v in string]
length = len(string) - 1
k = int(string)
d = int(input())

M = 10**9 + 7
def mod(v):
    if v >= M:
        return v % M
    return v

dp = [[[None] * 2 for _ in range(d)] for _ in range(length + 2)]
def dfs(i=0, s=0, border=True):
    if dp[i][s][border] is not None:
        return dp[i][s][border]

    if i > length:
        r = not bool(s)
        dp[i][s][border] = r
        return r

    cnt = 0
    for n in range(max(9 * (not border), nums[i]) + 1):
        cnt = mod(cnt + dfs(i + 1, (s + n) % d, border and nums[i] == n))
    dp[i][s][border] = cnt
    return cnt
# print(mod(dfs() - 1))

for i in reversed(range(length + 2)):
    for s in reversed(range(d)):
        for border in [False, True]:
            if i > length:
                dp[i][s][border] = not bool(s)
                continue

            cnt = 0
            for n in range(max(9 * (not border), nums[i]) + 1):
                cnt = mod(cnt + dp[i + 1][(s + n) % d][border and nums[i] == n])
            dp[i][s][border] = cnt

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

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6 * 2 + 1)
string = input()
nums = [int(v) for v in string]
length = len(string) - 1
k = int(string)
d = int(input())

M = 10**9 + 7
def mod(v):
    if v >= M:
        return v % M
    return v

dp = [[[None] * 2 for _ in range(d)] for _ in range(length + 2)]
def dfs(i=0, s=0, border=True):
    if dp[i][s][border] is not None:
        return dp[i][s][border]

    if i > length:
        r = not bool(s)
        dp[i][s][border] = r
        return r

    cnt = 0
    for n in range(max(9 * (not border), nums[i]) + 1):
        cnt = mod(cnt + dfs(i + 1, (s + n) % d, border and nums[i] == n))
    dp[i][s][border] = cnt
    return cnt

print(mod(dfs() - 1))

Submission status: Wrong Answer

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

DP = [[[0 for _ in range(d)] for _ in range(2)] for _ in range(len(k)+1)]
DP[0][0][0] = 1

for i in range(len(k)):
    now = int(k[i])
    for j in range(2):
        for mod in range(d):
            for n in range(10):
                # 対象の数字未満が確定する場合
                if j==1 or (j==0 and n < now):
                    next_j = 1
                # 対象の数字とこの桁まで同じ場合
                elif n == now:
                    next_j = 0
                # 対象の数字よりも大きな値の場合
                else: 
                    continue

                n_mod = n % d
                next_mod = (mod + n_mod) % d
                DP[i+1][next_j][next_mod] = (DP[i+1][next_j][next_mod] + DP[i][j][mod]) % (10**9+7)

ans = DP[len(k)][0][0] + DP[len(k)][1][0] -1 
print(ans)
# print(DP)

Submission status: Wrong Answer

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=1000000007
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  s=S()
  n=len(s)
  _d=I()


  dp=[[[0]*(_d+1) for _ in range(2)]for __ in range(n+1)]
  dp[0][0][0]=1

  for i in range(n):
    nd=int(s[i])
    for j in range(2):
      for k in range(_d):
        for d in range(10):

          ni=i+1
          nj=j
          nk=k

          if nj==0:
            if d>nd:
              continue
            if d<nd:
              nj=1

          nk+=d
          nk%=_d

          dp[ni][nj][nk]+=dp[i][j][k]
          dp[ni][nj][nk]%=mod

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

# main()
print(main())

Submission status: Wrong Answer

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=1000000007
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  s=S()
  n=len(s)
  _d=I()


  dp=[[[0]*(_d+1) for _ in range(2)]for __ in range(n+1)]
  dp[0][0][0]=1

  for i in range(n):
    nd=int(s[i])
    for j in range(2):
      for k in range(_d):
        for d in range(10):

          ni=i+1
          nj=j
          nk=k

          if nj==0:
            if d>nd:
              continue
            if d<nd:
              nj=1

          nk+=d
          nk%=_d

          dp[ni][nj][nk]+=dp[i][j][k]

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

# main()
print(main())

Submission status: Wrong Answer

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):
    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(int(k[i])):
            dp[i+1][(j+num) % d][1] = (dp[i+1][(j+num) % d][1] + dp[i][j][0]) % mod
            dp[i+1][(j+num) % d][0] = (dp[i+1][(j+num) % d][0] + dp[i][j][0]) % mod
                
ans = (dp[l][0][0] + dp[l][0][1] + mod - 1) % mod

print(ans)

Submission status: Wrong Answer

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

DP=[[[0]*d for _ in range(2)] for _ in range(m+1)]
DP[0][0][0]=1

for i in range(1,m+1):
    for flag in range(2):
        num=9 if flag else int(n[i-1])
        for j in range(d):
            for k in range(num+1):
                DP[i][flag or k<num][(j+k)%d] +=DP[i-1][flag][j]
                DP[i][flag or k<num][(j+k)%d] %=mod

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

Submission status: Wrong Answer

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,pprint,fractions
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

s = input()
D = inp()
n = len(s)
#dp[i][j][k]: i上から桁目まででそれまでの和をDで割ったあまりがj,k=0:Nと一緒 k=1:Nより小さいことが確定
dp = [[[0 for i in range(2)] for j in range(D)] for k in range(n+1)]
dp[0][0][0] = 1

for i in range(n):
    nd = int(s[i])
    for j in range(D):
        for k in range(2):
            for d in range(10):
                ni = i+1; nj = (j+d)%D; nk = k
                if k == 0:
                    if d > nd: continue
                    elif d < nd: nk = 1
                dp[ni][nj][nk] += dp[i][j][k]
                dp[ni][nj][nk] %= mod
# pprint.pprint(dp)
print(sum(dp[n][0])-1)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
K = list(map(int, list(input())[: -1]))
D = int(input())
mod = 10 ** 9 + 7
dp = [[0] * D for _ in range(len(K) + 1)]
dplim = [[0] * D for _ in range(len(K) + 1)]
dplim[0][0] = 1
for i in range(len(K)):
  for j in range(D):
    dplim[i + 1][(j + K[i]) % D] += dplim[i][j]
    for k in range(10):
      if k < K[i]:
        dp[i + 1][(j + k) % D] += dplim[i][j]
      dp[i + 1][(j + k) % D] += dp[i][j]
      dp[i + 1][(j + k) % D] %= mod
print(dp[-1][0] + dplim[-1][0] - 1 % mod)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
K = list(map(int, list(input())[: -1]))
D = int(input())
mod = 10 ** 9 + 7
dp = [[0] * D for _ in range(len(K) + 1)]
dplim = [[0] * D for _ in range(len(K) + 1)]
dplim[0][0] = 1
for i in range(len(K)):
  for j in range(D):
    dplim[i + 1][(j + K[i]) % D] += dplim[i][j]
    for k in range(10):
      if k < K[i]:
        dp[i + 1][(j + k) % D] += dplim[i][j]
      dp[i + 1][(j + k) % D] += dp[i][j]
      dp[i + 1][(j + k) % D] %= mod
print(dp[-1][0] + dplim[-1][0] - 1)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
K = list(map(int, list(input())[: -1]))
D = int(input())
mod = 10 ** 9 + 7
dp = [[0] * D for _ in range(len(K) + 1)]
dplim = [[0] * D for _ in range(len(K) + 1)]
dplim[0][0] = 1
for i in range(len(K)):
  for j in range(D):
    dplim[i + 1][(j + K[i]) % D] += dplim[i][j]
    for k in range(10):
      if k < K[i]:
        dp[i + 1][(j + k) % D] += dplim[i][j]
      dp[i + 1][(j + k) % D] += dp[i][j]
      dp[i + 1][(j + k) % D] %= mod
print(dp[-1][0] - (D != 1))

Submission status: Wrong Answer

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

MOD = 10**9 + 7

k_len = len(k)
dp = [[0] * d for _ in range(k_len)]
dp[0][0] = 1

# if( k_len == 1 ):
#     k = int(k)
#     print(k//d)
#     exit()
#
# for i in range(10):
#     dp[0][i%d] += 1

for i in range(1, k_len):
    for j in range(10):
        dp[i][0] += dp[i-1][(0-j)%d]
    dp[i][0] = dp[i][0] % MOD
    for j in range(1,d):
        dp[i][j] = (dp[i][j-1] + dp[i-1][j] - dp[i-1][(j-10)%d]) % MOD

ans = 0
heads = 0
for i in range(k_len):
    pick = int(k[i])
    for j in range(pick):
        ans += dp[k_len - 1 - i][(0 - j - heads) % d]
        ans = ans % MOD
    heads += pick

if(heads % d == 0):
    ans += 1

print(ans - 1)

Submission status: Wrong Answer

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

MOD = 10**9 + 7

k_len = len(k)
dp = [[0] * d for _ in range(k_len-1)]

if( k_len == 1 ):
    k = int(k)
    print(k//d)
    exit()

for i in range(10):
    dp[0][i%d] += 1

for i in range(1, k_len-1):
    for j in range(10):
        dp[i][0] += dp[i-1][(0-j)%d]
    dp[i][0] = dp[i][0] % MOD
    for j in range(1,d):
        dp[i][j] = (dp[i][j-1] + dp[i-1][j] - dp[i-1][(j-10)%d]) % MOD

ans = 0
heads = 0
for i in range(k_len-1):
    pick = int(k[i])
    for j in range(pick):
        ans += dp[k_len - 2 - i][(0 - j - heads) % d]
        ans = ans % MOD
    heads += pick

print(ans - 1)

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 = [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: 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 = [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[k%d]+=1

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)
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] = (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,dp2)
    

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

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)
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] = (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,dp2)
    

    mm1 = (mm1+li[i])%d
    dp2 = [dp1[i] for i in range(d)]
    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)
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)