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

Solution (Python):
import sys
readline = sys.stdin.readline



K = readline().rstrip()
D = int(readline())
DIV = 10 ** 9 + 7
keta = len(K)

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

x0 = int(K[0])
dp[0][0][x0 % D] = 1
bef = x0 % D 
for i in range(x0):
  dp[0][1][i % D] += 1
  
for i in range(1, keta):
  x = int(K[i])
  
  
  dp[i][0][(bef + x) % D] = 1
  
  
  
  for j in range(x):
    dp[i][1][(bef + j) % D] += dp[i - 1][0][bef]
  
  for j in range(D):
    dp[i][1][j] %= DIV
  
  bef = (bef + x) % D 
  
  
  for j in range(D):
    for k in range(10): 
      dp[i][1][(k + j) % D] += dp[i - 1][1][j]
      
  for j in range(D):
    dp[i][1][j] %= DIV

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

Solution (Python):
K = list(map(int, list(input())))
D = int(input())
MOD = 10 ** 9 + 7

DP = [[[0] * 2 for _ in range(D)] for _ in range(len(K))]

for i in range(K[0]):
  DP[0][i % D][0] += 1
DP[0][K[0] % D][1] += 1

for i in range(1, len(K)):
  for j in range(10):
    for k in range(D):
      DP[i][(j + k) % D][0] = (DP[i][(j + k) % D][0] + DP[i - 1][k][0]) % MOD
  for j in range(K[i]):
    for k in range(D):
      DP[i][(j + k) % D][0] = (DP[i][(j + k) % D][0] + DP[i - 1][k][1]) % MOD
  for k in range(D):
    DP[i][(k + K[i]) % D][1] = (DP[i][(k + K[i]) % D][1] + DP[i - 1][k][1]) % MOD

ans = (DP[-1][0][0] + DP[-1][0][1] - 1) % MOD
while ans < 0:
  ans += MOD

print(ans)

Solution (Python):
MOD = 10 ** 9 + 7
k = input()
d = int(input())
dp = [0] * d
now = 0
for i in map(int, k):
    ndp = [0] * d
    for t in range(i):
        ndp[(now+t) % d] = (ndp[(now+t) % d] + 1) % MOD
    for j in range(d):
        for t in range(10):
            ndp[(j+t) % d] = (ndp[(j+t) % d] + dp[j]) % MOD
    now = (now + i) % d
    dp = ndp
print((dp[0] - 1 + (now == 0)) % MOD)

Solution (Python):




import sys

sys.setrecursionlimit(10**6)
input = sys.stdin.buffer.readline
INF = 10 ** 9 + 1  
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 + 1)]
    border = 0
    debug(": K, N", K, N)
    debug(": less", less)
    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

    debug(": less", less)
    ret = less[N - 1][0] - 1
    ret += (border == 0)
    return ret % MOD


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



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
    """


T4 = """
555
1
"""


def test_T4():
    """
    >>> as_input(T4)
    >>> main()
    555
    """


T6 = """
5
1
"""


def test_T6():
    """
    >>> as_input(T6)
    >>> main()
    5
    """




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":
        
        
        from my_module import solve  
    elif sys.argv[-1] == "-t":
        print("testing")
        _test()
        sys.exit()
    elif sys.argv[-1] != '-p' and len(sys.argv) == 2:
        
        input_as_file = open(sys.argv[1])
        input = input_as_file.buffer.readline
        read = input_as_file.buffer.read

    main()

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


k = input()
n = len(k)
d = int(input())
dp0 = [[0]*(d) for _ in range(n+1)]
dp1 = [[0]*(d) for _ in range(n+1)]
dp1[0][0] = 1
M = 10**9+7
for i in range(1,n+1):
    for j in range(d):
        v = int(k[i-1])
        dp1[i][j] = dp1[i-1][(j-v)%d]
        for vv in range(10):
            if vv<v:
                dp0[i][j] += dp1[i-1][(j-vv)%d]
            dp0[i][j] += dp0[i-1][(j-vv)%d]
        dp1[i][j] %= M
        dp0[i][j] %= M
ans = (dp0[n][0]+dp1[n][0]-1) % M
print(ans)

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

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

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

for i in range(1, L+1):
    a = int(K[i-1])
    for d in range(D):
        dp[i][0][(d+a)%D] += dp[i-1][0][d]
        dp[i][0][(d+a)%D] %= MOD
        for b in range(10):
            dp[i][1][(d+b)%D] += dp[i-1][1][d] + (b<a)*dp[i-1][0][d]
            dp[i][1][(d+b)%D] %= MOD

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

Solution (Python):
def solve():
    MOD = 10**9 + 7

    strN = input().rstrip()
    D = int(input())

    maxD = len(strN)

    dpLt = [0] * D
    NmodD = 0
    for d, Nd in enumerate(strN):
        Nd = int(Nd)
        dpLt2 = [0] * D
        for modD in range(D):
            dpLt[modD] = dpNow = dpLt[modD] % MOD
            for x in range(10):
                modD2 = (modD+x) % D
                dpLt2[modD2] += dpNow
        for x in range(Nd):
            modD2 = (NmodD+x) % D
            dpLt2[modD2] += 1
        NmodD = (NmodD+Nd) % D
        dpLt = dpLt2

    print((dpLt[0] + (NmodD == 0) - 1) % MOD)


solve()

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

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

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

print((sum(dp[-1][0])-1)%mod)

Solution (Python):
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))]


s = int(k[0])
dp[0][s%d][1] = 1
for i in range(s):
    dp[0][i%d][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)

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

Solution (Python):
def solve():
    MOD = 10**9 + 7

    strN = input().rstrip()
    D = int(input())

    maxD = len(strN)

    dp = [[[0]*(D) for j in range(2)] for i in range(maxD+1)]
    dp[0][0][0] = 1
    for d, Nd in enumerate(strN):
        Nd = int(Nd)
        for isLtN in range(2):
            for modD in range(D):
                dp[d][isLtN][modD] %= MOD
                for x in range(10):
                    if not isLtN and x > Nd: continue
                    isLtN2 = isLtN or x < Nd
                    modD2 = (modD+x) % D
                    dp[d+1][isLtN2][modD2] += dp[d][isLtN][modD]

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


solve()

Solution (Python):


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    """
    _ _ 

    dp[i][j][one_of_previous_number_is_lower] = count of remainder j up to i-th digit, 0 <= j < D

    dp[i][(j+digit)%D][True] += dp[i-1][j][True] + dp[i-1][j][False] digit < K[i]
    dp[i][(j+digit)%D][False] += dp[i-1][j][False]        digit == K[i]
    """
    K = list(map(int, input().strip()))
    D = read_int()
    dp = [[0, 0] for _ in range(D)]
    dp[0][0] = 1
    modulo = 10**9+7
    for i in range(len(K)):
        new_dp = [[0, 0] for _ in range(D)]
        for j in range(D):
            for digit in range(10):
                new_dp[(j+digit)%D][True] += dp[j][True]
                if digit < K[i]:
                    new_dp[(j+digit)%D][True] += dp[j][False]
                if digit == K[i]:
                    new_dp[(j+digit)%D][False] += dp[j][False]
                new_dp[(j+digit)%D][False] %= modulo
                new_dp[(j+digit)%D][True] %= modulo
        dp = new_dp
    return (dp[0][0]+dp[0][1]-1)%modulo


if __name__ == '__main__':
    print(solve())

Solution (Python):


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    """
    _ _ 

    dp[i][j][one_of_previous_number_is_lower] = count of remainder j up to i-th digit, 0 <= j < D

    dp[i][(j+digit)%D][True] += dp[i-1][j][True] + dp[i-1][j][False] digit < K[i]
    dp[i][(j+digit)%D][False] += dp[i-1][j][False]        digit == K[i]
    """
    K = list(map(int, input().strip()))
    D = read_int()
    dp = [[[0, 0] for _ in range(D)]
           for _ in range(len(K)+1)]
    dp[0][0][0] = 1
    modulo = 10**9+7
    for i in range(len(K)):
        for j in range(D):
            for digit in range(10):
                dp[i+1][(j+digit)%D][True] += dp[i][j][True]
                if digit < K[i]:
                    dp[i+1][(j+digit)%D][True] += dp[i][j][False]
                if digit == K[i]:
                    dp[i+1][(j+digit)%D][False] += dp[i][j][False]
                dp[i+1][(j+digit)%D][False] %= modulo
                dp[i+1][(j+digit)%D][True] %= modulo
    return (dp[-1][0][0]+dp[-1][0][1]-1)%modulo


if __name__ == '__main__':
    print(solve())

Solution (Python):
def add(a, b):
    mod = 1e9+7
    c = a + b
    if c >= mod:
        c -= mod
    return c
def subtract(a, b):
    mod = 1e9+7
    c = a - b
    if c < 0:
        c += mod
    return c

K = input()

D = int(input())



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

str_len = len(K)

dp[0][0] = 1

for where in range(str_len):
    new_dp = [[0 for _ in range(2)] for _ in range(D)]
    for sum_so_far in range(D):
        for smaller_already in [0, 1]:
            for digit in range(10):
                K_digit = ord(K[where]) - ord('0')
                if digit > K_digit and smaller_already == 0:
                    break
                new_sum = (sum_so_far + digit) % D
                new_smaller = 1 if smaller_already == 1 or digit < K_digit else 0
                new_dp[new_sum][new_smaller] = add(new_dp[new_sum][new_smaller], dp[sum_so_far][smaller_already])
    dp = new_dp
                
                
answer = add(dp[0][0], dp[0][1])

answer = int(subtract(answer, 1))

print(answer)


"""

using namespace std;

using ll = long long; 

/*
30
4

brute-force -> look one by one -> from 1 to 30 -> if the digit sum is multiple of 4, then add
O(K * log K)


dp[d] - how many ways to get to remainder is d

dp[0] is the ans

dp[d] - how many ways to get to digit_sum as d

*/


int add(int a, int b) {
    const int mod = 1e9+7;
    int c = a + b;
    if (c >= mod) {
        c -= mod;
    }
    return c;
}

int subtract(int a, int b) {
    const int mod = 1e9+7;
    int c = a - b;
    if (c < 0) {
        c += mod;
    }
    return c;
}

int main() {
    const int nax = 10123;
    char K[nax];
    int D;
    scanf("%s", K);
    scanf("%d", &D);
    int len = strlen(K);
    vector<vector<int>> dp(D, vector<int>(2));
    // dp[sum][smaller_already] - no. of ways to choose digits so far
    // such that digits sum % D = sum and smaller_already means if the number
    // is already less than K
    dp[0][0] = 1;
    
    for (int where = 0; where < len; where++) {
        vector<vector<int>> new_dp(D, vector<int>(2));
        for (int sum = 0; sum < D; sum++) {
            for (bool sm_already : {false, true}) {
                for (int digit = 0; digit < 10; digit++) {
                    if (digit > K[where] - '0' && !sm_already) {
                        break;
                    }
                    int new_sum = (sum + digit) % D;
                    bool smaller = sm_already || digit < (K[where] - '0');
                    new_dp[new_sum][smaller] = add(new_dp[new_sum][smaller], dp[sum][sm_already]);
                }
            }
        }
        dp = new_dp;
    }
    
    int answer = add(dp[0][false], dp[0][true]);
    
    answer = subtract(answer, 1);
    
    printf("%d", answer);
    /*
    int ans = 0;
    for (int i = 1; i <= K; i++) {
        if (digit_sum(i) % D == 0) {
            ans += 1;
        }
    }
    printf("%d", ans);
    */
    
}
"""

Solution (Python):
mod = 10 ** 9 + 7

K = map(int, input())
D = int(input())

s = 0
dp = [0] * D
for k in K:
    ndp = [0] * D
    for d in range(10):
        for i, dpi in enumerate(dp, d):
            ndp[i % D] += dpi

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

    s = (s + k) % D
    dp = [x % mod for x in ndp]

print((dp[0] - (s != 0)) % mod)

Solution (Python):
mod = 10 ** 9 + 7

K = map(int, input())
D = int(input())

s = 0
dp = [0] * D
for k in K:
    ndp = [0] * D
    for d in range(10):
        for i, dpi in enumerate(dp):
            ndp[(i + d) % D] += dpi

    for d in range(k):
        ndp[(s + d) % D] += 1

    s = (s + k) % D
    dp = [x % mod for x in ndp]

print((dp[0] - (s != 0)) % mod)

Solution (Python):
def main():
    mod = 10 ** 9 + 7

    K = map(int, input())
    D = int(input())

    s = 0
    dp = [0] * D
    for k in K:
        ndp = [0] * D
        for d in range(10):
            for i, dpi in enumerate(dp):
                ndp[(i + d) % D] += dpi

        for d in range(k):
            ndp[(s + d) % D] += 1

        s = (s + k) % D
        dp = [x % mod for x in ndp]

    print((dp[0] - (s != 0)) % mod)

main()

Solution (Python):
def main():
    mod = 10 ** 9 + 7

    K = map(int, iter(input()))
    D = int(input())

    s = 0
    dp = [0] * D
    for k in K:
        ndp = [0] * D
        for d in range(10):
            for i, dpi in enumerate(dp):
                ndp[(i + d) % D] += dpi

        for d in range(k):
            ndp[(s + d) % D] += 1

        s = (s + k) % D
        dp = [x % mod for x in ndp]

    print((dp[0] - (s != 0)) % mod)

main()

Solution (Python):
mod = 10 ** 9 + 7

K = map(int, iter(input()))
D = int(input())

s = 0
dp = [0] * D
for k in K:
    ndp = [0] * D
    for d in range(10):
        for i, dpi in enumerate(dp):
            ndp[(i + d) % D] += dpi

    for d in range(k):
        ndp[(s + d) % D] += 1

    s = (s + k) % D
    dp = [x % mod for x in ndp]

print((dp[0] - (s != 0)) % mod)

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

MOD = 10**9+7
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):
    k = int(K[i])
    for j in range(D):
        dp[i+1][(j+k)%D][0] = dp[i][j][0]
        dp[i+1][(j+k)%D][0] %= MOD
        for d in range(10):
            dp[i+1][(j+d)%D][1] += dp[i][j][1]
            if d < k:
                dp[i+1][(j+d)%D][1] += dp[i][j][0]
            dp[i+1][(j+d)%D][1] %= MOD

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

Solution (Python):
MOD = 10**9 + 7

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):
    k = int(K[i])
    for j in range(D):
        dp[i+1][(j+k)%D][0] += dp[i][j][0]
        dp[i+1][(j+k)%D][0] %= MOD
        for d in range(10):
            dp[i+1][(j+d)%D][1] += dp[i][j][1]
            if d < k:
                dp[i+1][(j+d)%D][1] += dp[i][j][0]
            dp[i+1][(j+d)%D][1] %= MOD

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

Solution (Python):
mod=10**9+7
n=input()
D=int(input())
N=len(n)+1
dp=[[[0 for i in range(2)] for j in range(D)] for k in range(len(n)+1)]
dp[0][0][0]=1
for a in range(N-1):
  x=int(n[a])
  for b in range(D):
    for d in range(10):
      if d<x:
        dp[a+1][(b+d)%D][1]+=dp[a][b][0]+dp[a][b][1]
      elif d==x:
        dp[a+1][(b+d)%D][0]+=dp[a][b][0]
        dp[a+1][(b+d)%D][1]+=dp[a][b][1]
      else:
        dp[a+1][(b+d)%D][1]+=dp[a][b][1]
      dp[a+1][(b+d)%D][1]%=mod
      dp[a+1][(b+d)%D][0]%=mod
ans=sum(dp[-1][0])
print((ans-1)%mod)

Solution (Python):
mod = 10 ** 9 + 7

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

s = 0
dp = [0] * D
for k in K:
    T = [0] * D
    for i, dpi in enumerate(dp):
        for x in range(10):
            T[(i + x) % D] = (T[(i + x) % D] + dpi) % mod
    for x in range(k):
        T[(s + x) % D] += 1

    s = (s + k) % D
    dp = T

print((dp[0] + (-1 if s != 0 else 0)) % mod)

Solution (Python):
mod = 10 ** 9 + 7

K = input()
D = int(input())

s = 0
dp = [0] * D
for k in K:
    k = int(k)

    T = [0] * D
    for i, dpi in enumerate(dp):
        for x in range(10):
            T[(i + x) % D] = (T[(i + x) % D] + dpi) % mod
    for x in range(k):
        T[(s + x) % D] += 1

    s = (s + k) % D
    dp = T

print((dp[0] + (-1 if s != 0 else 0)) % mod)

Solution (Python):
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
r=(D+9)//D
for i in range(N):
    dc=d[i]
    dc2=d2[i]
    for j in range(r):
        dc=np.concatenate((dc,d[i]))
        dc2=np.concatenate((dc2,d2[i]))
    dc,dc2=np.cumsum(dc),np.cumsum(dc2)
    x=int(K[i])
    d[i+1]=np.roll(d[i],x)
    d2[i+1]=(dc[r*D:]-dc[r*D-x:(r+1)*D-x]+dc2[r*D:]-dc2[r*D-10:(r+1)*D-10])%m
print((d[-1,0]+d2[-1,0]-1)%m)

Solution (Python):
n = list(map(int, input()))
d = int(input())
l = len(n)
MOD = 10**9+7
dp = [[[0]*d for i in range(l+1)] for j in range(2)]
dp[0][0][0] = 1
for i in range(l):
  for j in range(d):
    for k in range(10):
      if k < n[i]:
        dp[1][i+1][j] += dp[0][i][(j-k)%d] + dp[1][i][(j-k)%d]
      elif k == n[i]:
        dp[0][i+1][j] += dp[0][i][(j-k)%d]
        dp[1][i+1][j] += dp[1][i][(j-k)%d]
      else:
        dp[1][i+1][j] += dp[1][i][(j-k)%d]
    dp[1][i+1][j] %= MOD
ans = dp[0][l][0] + dp[1][l][0] - 1
ans %= MOD
print(ans)

Solution (Python):
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
	x = []
	for c in rll()[0]:
		x.append(int(c))
	d = int(rl())
	ans = 0

	dp = [[0 for __ in range(2)] for _ in range(d)]
	dp[0][1] = 1
	for i in range(len(x)):
		ndp = [[0 for __ in range(2)] for _ in range(d)]
		for digsum in range(d):
			for tight in range(2):
				for nd in range(x[i]+1 if tight else 10):
					ns = (digsum + nd) % d 
					ntight = 1 if tight and nd == x[i] else 0
					ndp[ns][ntight] += dp[digsum][tight]
					ndp[ns][ntight] %= MOD
		dp = ndp

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

if __name__ == "__main__":
	main()

Solution (Python):
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
	x = []
	for c in rll()[0]:
		x.append(int(c))
	d = int(rl())
	ans = 0

	dp = [[0]*2 for _ in range(d)]
	dp[0][1] = 1
	for i in range(len(x)):
		ndp = [[0]*2 for _ in range(d)]
		for digsum in range(d):
			for tight in range(2):
				for nd in range(x[i]+1 if tight else 10):
					ns = (digsum + nd) % d 
					ntight = 1 if tight and nd == x[i] else 0
					ndp[ns][ntight] += dp[digsum][tight]
					ndp[ns][ntight] %= MOD
		dp = ndp

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

if __name__ == "__main__":
	main()

Solution (Python):
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
	x = []
	for c in rll()[0]:
		x.append(int(c))
	d = int(rl())
	ans = 0

	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):
					ns = (digsum + dig) % d 
					ntight = 1 if tight and dig == x[i] else 0
					dp[i+1][ns][ntight] += dp[i][digsum][tight]
					dp[i+1][ns][ntight] %= MOD

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

if __name__ == "__main__":
	main()

Solution (Python):
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):
					ns = (digsum + dig) % d 
					ntight = 1 if tight and dig == x[i] else 0
					dp[i+1][ns][ntight] += dp[i][digsum][tight]
					dp[i+1][ns][ntight] %= MOD

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

if __name__ == "__main__":
	main()

Solution (Python):
import sys
input = sys.stdin.readline

K = input()[:-1]
D = int(input())
L = len(K)
dp = [[[0]*D for _ in range(2)] for _ in range(L+1)]
dp[0][0][0] = 1
MOD = 10**9+7

for i in range(L):
    Ki = int(K[i])
    
    for j in range(2):
        for k in range(D):
            for d in range(10 if j else Ki+1):
                dp[i+1][j|(d<Ki)][(k+d)%D] += dp[i][j][k]
                dp[i+1][j|(d<Ki)][(k+d)%D] %= MOD

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

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    k=input()
    len_k=len(k)
    d=int(input())
    mod=10**9+7
    dp_0=[[0]*d for _ in range(len_k+1)]
    dp_1=[[0]*d for _ in range(len_k+1)] 
    dp_0[0][0]=1
    for i in range(len_k):
        ni=int(k[i])
        for j in range(d):
            for dig in range(10):
                dp_1[i+1][(j+dig)%d]=(dp_1[i+1][(j+dig)%d]+dp_1[i][j])%mod
            for dig in range(ni):
                dp_1[i+1][(j+dig)%d]=(dp_1[i+1][(j+dig)%d]+dp_0[i][j])%mod
            dp_0[i+1][(j+ni)%d]=(dp_0[i+1][(j+ni)%d]+dp_0[i][j])%mod
    print((dp_0[len_k][0]+dp_1[len_k][0]-1)%mod)

if __name__=='__main__':
    main()

Solution (Python):
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[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)%mod)

Solution (Python):


def submit():
    k = input()
    lenk = len(k)
    d = int(input())
    f = lambda x: x % d
    modp = 10 ** 9 + 7

    dp = [[[0 for _ in range(d)],
           [0 for _ in range(d)]] for _ in range(lenk)]

    curr = int(k[0])
    for j in range(10):
        if j < curr:
            dp[0][0][f(j)] += 1
        if j == curr:
            dp[0][1][f(j)] += 1
            break

    for i in range(1, lenk):
        curr = int(k[i])
        for s in range(d):
            
            for j in range(10):
                dp[i][0][f(s + j)] += dp[i - 1][0][s]
                dp[i][0][f(s + j)] %= modp
            
            
            for j in range(curr + 1):
                dp[i][j == curr][f(s + j)] += dp[i - 1][1][s]
                dp[i][j == curr][f(s + j)] %= modp
                
    ans = dp[lenk - 1][0][0] + dp[lenk - 1][1][0] - 1
    print(ans % modp)

submit()

Solution (Python):
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

ans = dp[n][0][0] + dp[n][0][1] - 1
print(ans % mod)

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF = float("inf")
MOD = 10**9 + 7 
input = lambda:sys.stdin.readline().rstrip()
from itertools import product
def resolve():
    k = input()
    modulo = int(input())
    dp = [[0] * 2 for _ in range(modulo)]
    dp[0][0] = 1

    for d in k:
        d = int(d)
        ndp = [[0] * 2 for _ in range(modulo)]
        for r, lt in product(range(modulo), range(2)):
            for x in range(10):
                if (not lt) and x > d:
                    continue
                nlt = max(lt, x < d)
                nr = (r + x) % modulo
                ndp[nr][nlt] += dp[r][lt]
                if ndp[nr][nlt] >= MOD:
                    ndp[nr][nlt] -= MOD
        dp = ndp

    print((dp[0][0] + dp[0][1] - 1) % MOD)
resolve()

Solution (Python):
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()

Solution (Python):
s = input()
n = len(s)
d = int(input())
dp = [[[0,0] for _ in range(d)] for _ in range(n+1)]
mod = 10**9 + 7
dp[0][0][1] = 1

for i in range(n):
    for j in range(d):
        for k in range(10):
            dp[i+1][(j+k)%d][0] += dp[i][j][0]
            dp[i+1][(j+k)%d][0] %= mod
        for k in range(int(s[i])):
            dp[i+1][(j+k)%d][0] += dp[i][j][1]
            dp[i+1][(j+k)%d][0] %= mod
        dp[i+1][(j+int(s[i]))%d][1] += dp[i][j][1]
print((sum(dp[n][0])-1)%mod)

Solution (Python):

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



DP=[[[0]*(D) for index1 in range(2)] for index2 in range(N+1)]

DP[0][0][0]=1


for i in range(1,N+1):
    for j in range(D):
        for k in range(10):
            DP[i][1][(j+k)%D]=(DP[i][1][(j+k)%D]+DP[i-1][1][j])%P
        for l in range(int(K[i-1])):
            DP[i][1][(j+l)%D]=(DP[i][1][(j+l)%D]+DP[i-1][0][j])%P
        DP[i][0][(j+int(K[i-1]))%D]=(DP[i][0][(j+int(K[i-1]))%D]+DP[i-1][0][j])%P


print((DP[N][0][0]+DP[N][1][0]-1)%P)

Solution (Python):
MOD = 10**9 + 7


def main():
    
    S = [s for s in input()]
    N = len(S)
    D = int(input())
    dp = [[[0]*D for _ in range(2)] for _ in range(N+1)]
    dp[0][0][0] = 1
    from itertools import product
    for i, smaller, dsum in product(range(N), range(2), range(D)):
        lim = 9 if smaller else int(S[i])
        for d in range(lim+1):
            dp[i+1][smaller or d < lim][(dsum+d) % D] += dp[i][smaller][dsum]
            dp[i+1][smaller or d < lim][(dsum+d) % D] %= MOD
    print((dp[N][0][0] + dp[N][1][0] - 1) % MOD)


if __name__ == '__main__':
    main()

Solution (Python):
MOD = 10**9 + 7


def main():
    
    S = [s for s in input()]
    N = len(S)
    D = int(input())
    dp = [[[0]*D for _ in range(2)] for _ in range(N+1)]
    dp[0][0][0] = 1
    from itertools import product
    for i, smaller, dsum in product(range(N), [True, False], range(D)):
        lim = 9 if smaller else int(S[i])
        for d in range(lim+1):
            dp[i+1][smaller or d < lim][(dsum+d) % D] += dp[i][smaller][dsum]
            dp[i+1][smaller or d < lim][(dsum+d) % D] %= MOD
    print((dp[N][0][0] + dp[N][1][0] - 1) % MOD)


if __name__ == '__main__':
    main()

Solution (Python):
MOD = 10**9 + 7


def main():
    
    S = input()
    N = len(S)
    D = int(input())
    dp = [[[0]*D for _ in range(2)] for _ in range(N+1)]
    dp[0][0][0] = 1
    from itertools import product
    for i, smaller, dsum in product(range(N), [True, False], range(D)):
        lim = 9 if smaller else int(S[i])
        for d in range(lim+1):
            dp[i+1][smaller or d < lim][(dsum+d) % D] += dp[i][smaller][dsum]
            dp[i+1][smaller or d < lim][(dsum+d) % D] %= MOD
    print((dp[N][0][0] + dp[N][1][0] - 1) % MOD)


if __name__ == '__main__':
    main()