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: Accepted

Solution code:
# @author 

import sys

class SDigitSum:
    def solve(self):
        MOD = 10 ** 9 + 7

        k = input().strip()
        d = int(input())

        s = len(k)
        dp = [[0] * d for _ in range(s + 1)]
        dp[0][0] = 1
        for i in range(10):
            dp[1][i % d] += 1

        # pre = [[0] * (d + 1) for _ in range(s + 1)]
        # for i in range(d):
        #     pre[1][i] = pre[1][i - 1] + dp[1][i]
        for l in range(2, s):
            # cur is sum(dp[l - 1][(-lm + r) % d] for lm in range(1, 10)
            # cur = sum(dp[l - 1][(-lm + 0) % d] for lm in range(1, 10))
            for r in range(d):
                dp[l][r] = (dp[l - 1][r] + sum(dp[l - 1][(-lm + r) % d] for lm in range(1, 10))) % MOD
                # dp[l][r] = (dp[l - 1][r] + cur) % MOD
                # cur -= dp[l - 1][(r - 9) % d]
                # cur += dp[l - 1][(r + 1 - 1) % d]


        ans = dp[s - 1][0]
        done = 0
        for i in range(s):
            lm = int(k[i])
            ans = (ans + sum(dp[s - 1 - i][(-done - (lm - v)) % d] for v in range(1, lm + 1 * (i != 0)))) % MOD
            done += lm

        if (sum(int(x) for x in k)) % d == 0:
            ans = (ans + 1) % MOD

        print((ans - 1) % MOD)

solver = SDigitSum()
input = sys.stdin.readline

solver.solve()

Submission status: Accepted

Solution code:
# @author 

import sys

class SDigitSum:
    def solve(self):
        MOD = 10 ** 9 + 7

        k = input().strip()
        d = int(input())

        s = len(k)
        dp = [[0] * d for _ in range(s + 1)]
        dp[0][0] = 1
        for i in range(10):
            dp[1][i % d] += 1

        pre = [[0] * (d + 1) for _ in range(s + 1)]
        for i in range(d):
            pre[1][i] = pre[1][i - 1] + dp[1][i]
        for l in range(2, s):
            # cur is sum(dp[l - 1][(-lm + r) % d] for lm in range(1, 10)
            cur = sum(dp[l - 1][(-lm + 0) % d] for lm in range(1, 10))
            for r in range(d):
                # dp[l][r] = (dp[l - 1][r] + sum(dp[l - 1][(-lm + r) % d] for lm in range(1, 10))) % MOD
                dp[l][r] = (dp[l - 1][r] + cur) % MOD
                cur -= dp[l - 1][(r - 9) % d]
                cur += dp[l - 1][(r + 1 - 1) % d]


        ans = dp[s - 1][0]
        done = 0
        for i in range(s):
            lm = int(k[i])
            ans = (ans + sum(dp[s - 1 - i][(-done - (lm - v)) % d] for v in range(1, lm + 1 * (i != 0)))) % MOD
            done += lm

        if (sum(int(x) for x in k)) % d == 0:
            ans = (ans + 1) % MOD

        print((ans - 1) % MOD)

solver = SDigitSum()
input = sys.stdin.readline

solver.solve()

Submission status: Accepted

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)%mod)

Submission status: Accepted

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) % MOD)

Submission status: Accepted

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) % mod)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
# 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)%MOD)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
"""<https://github.com/cheran-senthil/PyRival>"""
from __future__ import division, print_function

import sys

if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip

input = lambda: sys.stdin.readline().rstrip("\r\n")

MOD = 10**9 + 7


def main():
    K, D = list(map(int, input())), int(input())
    n = len(K)

    dp = [[0] * D for _ in range(n)]
    for i in range(10):
        dp[0][i % D] += 1
    for i in range(n - 1):
        for j in range(D):
            dp[i + 1][j] = sum(dp[i][(j - k) % D] for k in range(10)) % MOD

    cnt, k = 0, 0
    for i in range(n - 1):
        cnt = (cnt + sum(dp[-i - 2][(-j - k) % D] for j in range(K[i]))) % MOD
        k += K[i]
    cnt += sum((j + k) % D == 0 for j in range(K[-1] + 1))

    print((cnt - 1) % MOD)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python
"""<https://github.com/cheran-senthil/PyRival>"""
from __future__ import division, print_function

import os
import sys
from io import BytesIO, IOBase
from collections import Counter

if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip
else:
    _str = str
    str = lambda x=b"": x if type(x) is bytes else _str(x).encode()

MOD = 10**9 + 7


def main():
    K, d = list(map(int, input())), int(input())
    n = len(K)

    dp = [[0] * d for _ in range(n)]

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

    for i in range(n - 1):
        dpi, dpii = dp[i], dp[i + 1]
        for j in range(d):
            dpii[j] = sum(dpi[(j - k) % d] for k in range(10)) % MOD

    res, k = 0, 0
    for i in range(n - 1):
        dpi = dp[-i - 2]
        res = (res + sum(dpi[(-j - k) % d] for j in range(K[i]))) % MOD
        k += K[i]
    res += sum((k + j) % d == 0 for j in range(K[-1] + 1))

    print((res - 1) % MOD)


# region template

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._buffer = BytesIO()
        self._fd = file.fileno()
        self._writable = "x" in file.mode or "r" not in file.mode
        self.write = self._buffer.write if self._writable else None

    def read(self):
        if self._buffer.tell():
            return self._buffer.read()
        return os.read(self._fd, os.fstat(self._fd).st_size)

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self._buffer.tell()
            self._buffer.seek(0, 2), self._buffer.write(b), self._buffer.seek(ptr)
        self.newlines -= 1
        return self._buffer.readline()

    def flush(self):
        if self._writable:
            os.write(self._fd, self._buffer.getvalue())
            self._buffer.truncate(0), self._buffer.seek(0)


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", b" "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", b"\n"))
    if kwargs.pop("flush", False):
        file.flush()


sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
input = lambda: sys.stdin.readline().rstrip(b"\r\n")

# endregion

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python
"""<https://github.com/cheran-senthil/PyRival>"""
from __future__ import division, print_function

import os
import sys
from io import BytesIO, IOBase
from collections import Counter

if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip
else:
    _str = str
    str = lambda x=b"": x if type(x) is bytes else _str(x).encode()

MOD = 10**9 + 7


def main():
    k, d = list(map(int, input())), int(input())
    n = len(k)

    dp = [[0] * d for _ in range(n)]
    for m in range(10):
        dp[0][m % d] += 1
    for i in range(n - 1):
        for j in range(d):
            dp[i + 1][j] = sum(dp[i][(j - m) % d] for m in range(10)) % MOD

    res, cnt = 0, 0
    for i in range(n - 1):
        res = (res + sum(dp[-i - 2][(-m - cnt) % d] for m in range(k[i]))) % MOD
        cnt += k[i]
    res += sum((cnt + m) % d == 0 for m in range(k[-1] + 1))

    print((res - 1) % MOD)


# region template

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._buffer = BytesIO()
        self._fd = file.fileno()
        self._writable = "x" in file.mode or "r" not in file.mode
        self.write = self._buffer.write if self._writable else None

    def read(self):
        if self._buffer.tell():
            return self._buffer.read()
        return os.read(self._fd, os.fstat(self._fd).st_size)

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self._buffer.tell()
            self._buffer.seek(0, 2), self._buffer.write(b), self._buffer.seek(ptr)
        self.newlines -= 1
        return self._buffer.readline()

    def flush(self):
        if self._writable:
            os.write(self._fd, self._buffer.getvalue())
            self._buffer.truncate(0), self._buffer.seek(0)


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", b" "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", b"\n"))
    if kwargs.pop("flush", False):
        file.flush()


sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
input = lambda: sys.stdin.readline().rstrip(b"\r\n")

# endregion

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def f(ks, d):
    md = 10 ** 9 + 7
    dp = [0] * d
    just = 0

    for k in ks:
        ndp = [0] * d

        ndp[0] = s = sum(dp[i % d] for i in range(-9, 1))
        for i in range(1, d):
            ndp[i] = s = (s + dp[i % d] - dp[(i - 10) % d]) % md

        for ndi in range(just, just + k):
            ndp[ndi % d] += 1

        just = (just + k) % d
        dp = ndp

    print((dp[0] + (just == 0) - 1) % md)


ks = list(map(int, list(input())))
d = int(input())
f(ks, d)

Submission status: Accepted

Solution code:
def f(ks, d):
    md = 10 ** 9 + 7
    dp = [0] * d
    just = 0

    for k in ks:
        ndp = [0] * d

        for di, dk in enumerate(dp):
            for ndi in range(di, di + 10):
                ndp[ndi % d] += dk

        for ndi in range(just, just + k):
            ndp[ndi % d] += 1

        ndp = [ndk % md for ndk in ndp]

        just = (just + k) % d
        dp = ndp

    print((dp[0] + (just == 0) - 1) % md)


ks = list(map(int, list(input())))
d = int(input())
f(ks, d)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10070)
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True  and False
MOD = 10**9 + 7

def f(s,r):
    sz = len(s)
    n = int(s[0])
    if sz==1:
        sum = 0
        for i in range(n+1):
          if (r-i)%d == 0:
            sum += 1
        return sum
    sum = f(s[1:], (r-n)%d)
    for i in range(n):
        sum += dp[sz-1][(r-i)%d]
        if sum >= MOD:
            sum -= MOD
    return sum

k = input()
d = inn()
e = len(k)
dp = [ [0 for i in range(d)] for j in range(max(2,e)) ]
for i in range(10):
    dp[1][i%d] += 1
for i in range(2,e):
  for j in range(d):
    for m in range(10):
        dp[i][j] += dp[i-1][(j-m)%d]
        if dp[i][j] >= MOD:
            dp[i][j] -= MOD
print((f(k,0)-1)%MOD)

Submission status: Accepted

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)%mod))

Submission status: Accepted

Solution code:
mod=10**9+7
K=list(map(int,input().strip()))
d=int(input())
l=len(K)
DP=[[[0]*d for _ in range(2)] for _ in range(l+1)]
DP[0][0][0]=1
for i,k in enumerate(K):
    for less in range(2):
        if less:
            limit=9
        else:
            limit=k
        for m in range(d):
            for l in range(limit+1):
                DP[i+1][less or l<limit][(m+l)%d]+=DP[i][less][m]
                DP[i+1][less or l<limit][(m+l)%d]%=mod
print((DP[-1][0][0]+DP[-1][1][0]-1)%mod)

Submission status: Accepted

Solution code:


MOD = 1000000007

def F(k, s):
    return dp[k][s]

def solve(n):
    resp = 0
    n = map(int, str(n))
    pref = 0
    for i in range(len(n)):
        for d in range(n[i]):
            resp += F(len(n) - i - 1, (pref - d) % D)
            resp %= MOD
        pref -= n[i]
        pref %= D
    return resp


K = raw_input()
D = input()

# dp[i][j] = cant de numeros de i digitos con suma % d = j
dp = [[0] * D for _ in range(len(K) + 1)]
dp[0][0] = 1
for i in range(1, len(K) + 1):
    for j in range(D):
        for d in range(10):
            dp[i][j] += dp[i - 1][(j - d) % D]
            dp[i][j] %= MOD

resp = solve(K) - 1
if sum(map(int, str(K))) % D == 0:
    resp += 1
print(resp % MOD)

Submission status: Accepted

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

L=len(K)

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

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

for ketanum in K[1:]:
    NDP=[0]*D

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

    for j in range(int(ketanum)):
        NDP[(LIMIT+j)%D]+=1

    LIMIT=(LIMIT+int(ketanum))%D

    DP=NDP

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

Submission status: Accepted

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
        d1 = max(0, d-10)
        for j in range(d1):
            for jj in range(j+1,j+10):
                u[jj] += t[j]
            u[j] %= mod

        for j in range(d1, 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] % mod

    return (t[0] - 1) % mod


print(main())

Submission status: Accepted

Solution code:
from itertools import accumulate

k = input()
d = int(input())
dp = [0] * (d + 10)
dp2 = 0
MOD = 10 ** 9 + 7
for c in k:
    c = int(c)
    for e in range(d - 1, -1, -1):
        dp[e + 10] -= dp[e]
    dp[dp2] += 1
    dp[dp2 + c] -= 1
    dp = list(accumulate(dp))
    for e in range(9, -1, -1):
        dp[e] += dp[d + e]
        dp[d + e] = 0
    for e in range(d):
        dp[e] %= MOD
    dp2 = (dp2 + c) % d
ans = dp[0] - 1
if dp2 == 0:
    ans += 1
print(ans % MOD)

Submission status: Accepted

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

S = [[0, 0] for i in range(D)]
S[0][0] = 1
for i in range(N):
    c = int(K[i])
    T = [[0, 0] for i in range(D)]
    for d in range(D):
        w0, w1 = S[d]
        w0 %= MOD
        w = S[d][0] % MOD
        for v in range(c):
            T[(d+v)%D][1] += w0
        T[(d+c)%D][0] += w0

        w1 %= MOD
        for v in range(10):
            T[(d+v)%D][1] += w1
    S = T
print((sum(S[0])-1) % MOD)

Submission status: Accepted

Solution code:
import sys
fin = sys.stdin.readline


MOD = 10**9 + 7
K = [int(elem) for elem in fin()[:-1]]
D = int(fin())

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

for bound in K:
    next_dp = [[0] * 2 for _ in range(D)]
    for num in range(10):
        for d in range(D):
            next_reminder = (num + d) % D
            if num < bound:
                next_dp[next_reminder][0] += (dp[d][0] + dp[d][1])
            elif num == bound:
                next_dp[next_reminder][0] += dp[d][0]
                next_dp[next_reminder][1] += dp[d][1]
            else:
                next_dp[next_reminder][0] += dp[d][0]
            next_dp[next_reminder][0] %= MOD
            next_dp[next_reminder][1] %= MOD
    # import pdb; pdb.set_trace()
    dp = next_dp

res = dp[0][0] + dp[0][1] - 1
print(res) if res >= 0 else print(res + MOD)

Submission status: Accepted

Solution code:
a = input()
dd = int(input())
mod = 10**9 + 7
n = len(a)
dp = [[[0 for j in range(dd)] for k in range(2)] for i in range(n+1)]
dp[0][0][0] = 1
for i in range(n):
  for j in range(2):
    for k in range(dd):
      lim = 9 if j else int(a[i]) - 0
      for d in range(lim+1):
        dp[i+1][(j or d) <lim][(k+d)%dd] += dp[i][j][k]
        dp[i+1][(j or d) <lim][(k+d)%dd] %= mod
ans = 0
for j in range(2):
  ans += dp[n][j][0]
print((ans-1)%mod)

Submission status: Accepted

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

s = len(N)
mod=10**9+7
#[2][D][s]
dp=[[[0]*(s+1) for i in range(D)] for i in range(2)]
dp[0][0][0]=1
for i in range(s):
    for j in range(D):
        for k in range(10):
            dp[1][(j+k)%D][i+1]+=dp[1][j][i]
            dp[1][(j+k)%D][i+1]%=mod
        for k in range(int(N[i])):
            dp[1][(j+k)%D][i+1]+=dp[0][j][i]
            dp[1][(j+k)%D][i+1]%=mod
        dp[0][(j+int(N[i]))%D][i+1]+=dp[0][j][i]
        dp[0][(j+int(N[i]))%D][i+1]%=mod
print((dp[0][0][s]+dp[1][0][s]-1)%mod)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush,heappop,heapify
import math
from collections import *
from functools import reduce,cmp_to_key
import sys
input = sys.stdin.readline

from itertools import accumulate
from functools import lru_cache

M = mod = 10 ** 9 + 7
def factors(n):return sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))
def inv_mod(n):return pow(n, mod - 2, mod)
 
def li():return [int(i) for i in input().rstrip('\n').split()]
def st():return input().rstrip('\n')
def val():return int(input().rstrip('\n'))
def li2():return [i for i in input().rstrip('\n')]
def li3():return [int(i) for i in input().rstrip('\n')]

@lru_cache(None)
def rec(n, curr, rem):
    if not n:return 1 if curr % rem == 0 else 0
    ans = 0
    for j in range(10):
        ans = (ans + rec(n - 1, (curr + j) % rem, rem)) % mod
    return ans


k = st()
d = val()
n = len(k)

curr = ans = 0


for i in range(n):
    for j in range(int(k[i])):
        ans = (ans + rec(n - i - 1, (curr + j) % d, d)) % mod


    curr = (curr + int(k[i])) % d

if curr % d == 0:ans += 1
ans -= 1

print(ans % mod)

Submission status: Runtime Error

Solution code:
// #pragma GCC optimize ("O3")
// #pragma GCC target ("sse4")

#include <bits/stdc++.h>
using namespace std;
const int INF = 1 << 29;
const int NINF = -1*INF;
const long long LLINF = 1ll << 60;
const long long LLNINF = -1*LLINF;

template <class Ch, class Tr, class Container>
basic_ostream <Ch, Tr> & operator << (basic_ostream <Ch, Tr> & os, Container const& x) {
    os << "{ ";
    for(auto& y : x) os << y << " ";
    return os << "}";
}

template <class X, class Y>
ostream & operator << (ostream & os, pair <X, Y> const& p) {
	return os << "[ " << p.first << ", " << p.second << "]" ;
}

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
 
typedef pair<int, int> pi;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<double> vd;
typedef vector<ld> vld;
typedef vector<pi> vpi;
typedef vector<vector<int>> vvi;
typedef vector<vll> vvll;
typedef vector<vd> vvd;
typedef vector<vld> vvld;
 
#define mp make_pair
#define pb push_back
#define pf push_front
#define all(x) x.begin(), x.end()
#define revAll(x) x.rbegin(), x.rend()
#define gcd(a, b) __gcd(a, b)
#define popcount(x) __builtin_popcount(x)
#define isize(x) (int)(x.size())
#define rep(i,n) for(int i = 0; i < n; i++)
#define rep1(i, n) for(int i = 1; i < n+1; i++)
#define umap unordered_map

const ll MOD = 1e9 + 7;

void madd(ll& a, ll b){
	a += b;
	if (a >= MOD) a -= MOD;
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);
	string K; cin >> K;
	int D; cin >> D;
	vi lim = vi();
	for(const auto& c : K){
		lim.pb((int)(c - '0'));
	}
	int n = isize(lim);
	ll dp[n+1][2][D];
	rep(i,n+1)rep(j, 2)rep(k, D) dp[i][j][k] = 0;
	dp[0][1][0] = 1;

	for(int i = 0; i < n; i++){
		for(int tight = 0; tight <= 1; tight++){
			for(int ds = 0; ds < D; ds++){
				int md = tight ? lim[i] : 9;
				for(int d = 0; d <= md; d++){
					int nt = (tight and lim[i] == d) ? 1 : 0;
					int nds = (d + ds) % D;
					madd(dp[i+1][nt][nds], dp[i][tight][ds]);
				}
			}
		}
	}
	ll ans = 0;
	madd(ans, dp[n][0][0]);
	madd(ans, dp[n][1][0]);
	cout << ans-1;	
}

Submission status: Runtime Error

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


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

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


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

Submission status: Runtime Error

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



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


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


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

Submission status: Runtime Error

Solution code:
from collections import Counter
from collections import deque
import math
import bisect
import sys
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

mod=10**9+7
K=input()
n=len(K)
d=int(input())
dp=[[0]*n for i in range(d)]
dp1=[[0]*n for i in range(d)]
c=0
for i in range(n):
    c+=int(K[i])
    dp1[c%d][i]=1
for j in range(1,int(K[0])):
    dp[j][0]+=1
for i in range(n-1):
    if i>0:
        for j in range(1,10):
            dp[j%d][i]+=1
    for j in range(d):
        if dp1[j][i]==1:
            for k in range(int(K[i+1])):
                dp[(j+k)%d][i+1]+=1
        if dp[j][i]!=0:
            for k in range(10):
                dp[(j+k)%d][i+1]+=dp[j][i]
    for j in range(d):
        dp[j][i]=dp[j][i]%mod
for j in range(1,10):
    dp[j%d][-1]+=1
print((dp[0][-1]+dp1[0][-1])%mod)

Submission status: Runtime Error

Solution code:
from collections import Counter
from collections import deque
import math
import bisect
import sys
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

mod=10**9+7
K=input()
n=len(K)
d=int(input())
dp=[[0]*n for i in range(d)]
dp1=[[0]*n for i in range(d)]
c=0
for i in range(n):
    c+=int(K[i])
    dp1[c%d][i]=1
for j in range(1,int(K[0])):
    dp[j][0]+=1
for i in range(n-1):
    if i>0:
        for j in range(1,10):
            dp[j%d][i]+=1
    for j in range(d):
        if dp1[j][i]==1:
            for k in range(int(K[i+1])):
                dp[(j+k)%d][i+1]+=dp1[j][i]
        if dp[j][i]!=0:
            for k in range(10):
                dp[(j+k)%d][i+1]+=dp[j][i]
    for j in range(d):
        dp[j][i]=dp[j][i]%mod
for j in range(1,10):
    dp[j%d][-1]+=1
print((dp[0][-1]+dp1[0][-1])%mod)

Submission status: Runtime Error

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(10001)

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)

	@lru_cache(None)
	def dfs(tight, i, tot):
		if i == len(x):
			return 1 if tot == 0 else 0
		maxdig = x[i] if tight else 9
		cnt = 0
		for dig in range(0, maxdig + 1):
			ntight = 1 if tight and dig == x[i] else 0
			cnt += dfs(ntight, i + 1, (tot + dig) % d)
		return cnt % MOD

	ans += dfs(1, 0, 0) - 1
	print(ans % MOD)

	stdout.close()

if __name__ == "__main__":
	main()

Submission status: Runtime Error

Solution code:
from sys import stdin, stdout
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')

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

	@lru_cache(None)
	def dfs(x, tight, i, tot):
		if i == len(x):
			return 1 if tot % d == 0 else 0
		start = 0 if i > 0 else 1
		maxdig = x[i] if tight else 9
		cnt = 0
		for dig in range(start, maxdig + 1):
			ntight = 1 if tight and dig == x[i] else 0
			cnt += dfs(x, ntight, i + 1, tot + dig)
		return cnt % MOD

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

	tupk = totup(k)
	ans += dfs(tupk, 1, 0, 0)
	for i in range(1, len(tupk)):
		bndry = 10**i-1
		ans += dfs(totup(bndry), 1, 0, 0)
		ans %= MOD

	print(ans % MOD)

	stdout.close()

if __name__ == "__main__":
	main()