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: Runtime Error

Solution code:
def f(i,s,e,d):
  if i==n:
    return s==0
  if (i,s,e) not in d:
    d[i,s,e]=sum(f(i+1,(s+j)%r,e and j==a[i],d) for j in xrange(a[i]+1 if e else 10))%(pow(10,9)+7)
  return d[i,s,e]
a=map(int,list(raw_input().strip()))
n=len(a)
r=input()
print (f(0,0,True,{})-1)%(pow(10,9)+7)

Submission status: Runtime Error

Solution code:
def f(i,s,e,d):
  if i==n:
    return s==0
  if (i,s,e) not in d:
    d[i,s,e]=sum(f(i+1,(s+j)%r,e and j==a[i]) for j in xrange(a[i]+1 if e else 10))%(pow(10,9)+7)
  return d[i,s,e]
a=map(int,list(raw_input().strip()))
n=len(a)
r=input()
print (f(0,0,True,{})-1)%(pow(10,9)+7)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10000)
n = int(input())
d = int(input())
p = 10**9+7
DP = {}
DP[-1] = [0]*d
DP[0] = [0]*d
DP[0][0] = 1
def dp(i):
    try:
        return DP[i]
    except:
        pass
    q, r = i//10, i % 10
    DP[i] = []
    for j in range(d):
        tmp = 0
        for k in range(r+1):
            tmp += dp(q)[(j-k) % d]
        for k in range(r+1, 10):
            tmp += dp(q-1)[(j-k) % d]
        DP[i].append(tmp)
    return DP[i]
print((dp(n)[0]-1) % p)

Submission status: Runtime Error

Solution code:
n = int(input())
d = int(input())
p = 10**9+7
DP = {}
DP[-1] = [0]*d
DP[0] = [0]*d
DP[0][0] = 1
def dp(i):
    try:
        return DP[i]
    except:
        pass
    q, r = i//10, i % 10
    DP[i] = []
    for j in range(d):
        tmp = 0
        for k in range(r+1):
            tmp += dp(q)[(j-k) % d]
        for k in range(r+1, 10):
            tmp += dp(q-1)[(j-k) % d]
        DP[i].append(tmp)
    return DP[i]
print((dp(n)[0]-1) % p)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env pypy3
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    K=list(input())
    D=I()
    N=len(str(K))
    
    #dp[i][j]はi桁目まで見て，総和のmodがj，tight&lose
    dpt=[[0]*D for _ in range(N+1)]
    dpl=[[0]*D for _ in range(N+1)]
    
    start=int(K[0])
    
    #初期化
    dpt[0][0]=1
            
    #推移
    now=0#tが0ではない位置
    
    for i in range(N):
        num=(int(K[i]))
        #t
        dpt[i+1][(now+num)%D]=1
        for k in range(num):
            dpl[i+1][(now+k)%D]+=1
        now=(now+num)%D
                    
        
        #l，尺取り
        S=0
        for j in range(10):#初期化，0~9までの和
            S+=dpl[i][j%D]
            
        for j in range(D):#あまりが10~D-1,0~9の順に配る
            dpl[i+1][(j+9)%D]+=S
            dpl[i+1][(j+9)%D]%=mod
            S+=dpl[i][(j+10)%D]-dpl[i][j%D]
        
                
    #0もカウントしているmので1ひく
    print((dpt[-1][0]+dpl[-1][0]-1)%mod)
    
    
            
    
    

main()

Submission status: Runtime Error

Solution code:
s,d=int(input()),input()
n=[int(i) for i in s]
l=len(s)
mod=10**9+7
dp=[[[0]*d,[0]*d] for i in range(l+1)]
dp[0][0][0]=1
for i in range(l):
    for smaller in range(2):
        for j in range(d):
            for x in range(10 if smaller else n[i]+1):
                dp[i+1][smaller or x<n[i]][(j+x)%d] += dp[i][smaller][j]
                dp[i+1][smaller or x<n[i]][(j+x)%d]%=mod
print((dp[l][0][0]+dp[l][1][0]-1)%mod)

Submission status: Runtime Error

Solution code:
#if tight==1 it is not possible to go over k[idx]
#if tight==0 we can go from 0 to 9
import sys
sys.setrecursionlimit(10**4+1)
from functools import lru_cache
m = 10**9+7
@lru_cache(None)
def solve(idx,rem,tight):
    if idx==len(k):
        if rem==0:
            return 1
        return 0
    lim = 9 if tight==0 else int(k[idx])
    ans = 0
    for i in range(0,lim+1):
        curTight = tight 
        if i<int(k[idx]):
            curTight=0
        ans+=solve(idx+1,(rem+i)%d,curTight)
        ans%=m
    return ans
k = input().strip()
d = int(input())
print((solve(0,0,1)-1)%m)

Submission status: Runtime Error

Solution code:
#if tight==1 it is not possible to go over k[idx]
#if tight==0 we can go from 0 to 9
from functools import lru_cache
m = 10**9+7
@lru_cache(None)
def solve(idx,rem,tight):
    if idx==len(k):
        if rem==0:
            return 1
        return 0
    lim = 9 if tight==0 else int(k[idx])
    ans = 0
    for i in range(0,lim+1):
        curTight = tight 
        if i<int(k[idx]):
            curTight=0
        ans+=solve(idx+1,(rem+i)%d,curTight)
        ans%=m
    return ans
k = input().strip()
d = int(input())
print((solve(0,0,1)-1)%m)

Submission status: Runtime Error

Solution code:
def digit_dp(n, m):
    # dp[i][j][k] -> i: 現在見ている桁数
    #                j: n以下が保証されているかどうか
    #                k: m で割った余りの総和
    n = list(map(int, list(str(n))))
    n_len = len(n)
    dp_table = [[[0 for k in range(m)] for j in range(2)] for i in range(n_len + 1)]
    dp_table[0][0][0] = 1

    for i in range(n_len):
        for j in range(2):
            for k in range(m):
                for d in range(0, 10 if j else n[i] + 1):
                    dp_table[i + 1][j or (d < n[i])][(k + d % m) % m] += dp_table[i][j][k]

    return dp_table[-1][0][0] + dp_table[-1][1][0] - 1
    #0 の分、1を減算


a, b = map(int, input().split())
mod = 10**9 + 7
print(digit_dp(a, b) % mod)

Submission status: Runtime Error

Solution code:
string = input()
nums = [int(v) for v in string]
length = len(string) - 1
k = int(string)
d = int(input())

if length < 5:
    raise Exception()

Submission status: Runtime Error

Solution code:
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 * 100)] 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: Runtime Error

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

Submission status: Runtime Error

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


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

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
using namespace std; void solve(); int main(){cin.tie(0); ios::sync_with_stdio(false); cout<<fixed<<setprecision(10); solve();}
using ll=int_fast64_t; using ld=long double; using pll=pair<ll,ll>; using pld=pair<ld,ld>;
#define fi first
#define se second
#define SELECTOR(_1,_2,_3,SELECT,...) SELECT
#define rep(...) SELECTOR(__VA_ARGS__,_rep1,_rep0)(__VA_ARGS__)
#define _rep0(i,n) for(ll i=0;i<n;++i)
#define _rep1(i,k,n) for(ll i=k;i<n;++i)
template<class T> void vecout(const T &v){for(auto it=v.begin();it!=v.end();++it,cout<<(it!=v.end()?" ":"\n"))cout<<*it;}
template<class T> vector<T> make_v(size_t a,T b){return vector<T>(a,b);}
template<class... Ts> auto make_v(size_t a,Ts... ts){return vector<decltype(make_v(ts...))>(a,make_v(ts...));}

template <std::uint_fast64_t Modulus> class modint {
public:
  ll a;
  constexpr modint(const ll x = 0) noexcept : a(x % Modulus) {}
  constexpr ll &value() noexcept { return a; }
  constexpr const ll &value() const noexcept { return a; }
  constexpr modint operator+(const modint rhs) const noexcept {
    return modint(*this) += rhs;
  }
  constexpr modint operator-(const modint rhs) const noexcept {
    return modint(*this) -= rhs;
  }
  constexpr modint operator*(const modint rhs) const noexcept {
    return modint(*this) *= rhs;
  }
  constexpr modint operator/(const modint rhs) const noexcept {
    return modint(*this) /= rhs;
  }
  constexpr modint &operator+=(const modint rhs) noexcept {
    a += rhs.a;
    if (a >= Modulus) {
      a -= Modulus;
    }
    return *this;
  }
  constexpr modint &operator-=(const modint rhs) noexcept {
    if (a < rhs.a) {
      a += Modulus;
    }
    a -= rhs.a;
    return *this;
  }
  constexpr modint &operator*=(const modint rhs) noexcept {
    a = a * rhs.a % Modulus;
    return *this;
  }
  constexpr modint &operator/=(modint rhs) noexcept {
    ll exp = Modulus - 2;
    while (exp) {
      if (exp % 2) {
        *this *= rhs;
      }
      rhs *= rhs;
      exp /= 2;
    }
    return *this;
  }
};

void solve(){
  const ll MOD=1000000007;
  string k; cin>>k;
  ll d; cin>>d;
  ll n=k.size();
  auto dp=make_v(n+1,d,2,modint<MOD>(0));
  dp[0][0][0]=modint<MOD>(1);
  rep(i,n){
    ll a=k[i]-'0';
    rep(j,d)rep(o,10){
      dp[i+1][(j+o)%d][1]+=dp[i][j][1];
      if(o<a) dp[i+1][(j+o)%d][i]+=dp[i][j][0];
      else if(o==a) dp[i+1][(j+o)%d][i]+=dp[i][j][1];
    }
  }
  cout<<(dp[n][0][0]+dp[n][0][1]-1).a<<"\n";
}

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
K = input()
D = int(input())
N = len(K)
dp = [[0] * D for i in range(N)]
for i in range(int(K[0])):
    dp[0][i%D] += 1
tight = int(K[0])%D
for i in range(1, N):
    for j in range(D):
        for k in range(10):
            dp[i][j] += dp[i-1][(j-k)%D]
            dp[i][j] %= mod
    for k in range(int(K[i])):
        dp[i][(tight+k)%D] += 1
    tight = (tight+int(K[i]))%D
print((dp[N-1][0]+(tight==0)-1)%mod)

Submission status: Runtime Error

Solution code:
def solve(pos,sum1,f):
    
    res=0
    
    
    if(pos==len(k)):
        if(sum1%d==0):
            return 1
        else:
            return 0
    if(dp[pos][sum1][f]!=-1):
        return dp[pos][sum1][f]

    if(f==0):
        lmt=k[pos]
    else:
        lmt=9

    for dig in range(lmt+1):
        nsum=sum1
        nf=f
        if(f==0)and(dig<lmt):
            nf=1
        nsum+=dig
        nsum%=d
        res+=solve(pos+1,nsum,nf)
    if(res>mod):
        res%=mod
    dp[pos][sum1][f]=res
    return res

mod=1000000007  

    
k=list(map(int,input()))
d=int(input())
dp=[[[-1,-1] for i in range(d+7)] for j in range(len(k)+7)]


res=solve(0,0,0)
if(res==-1):
    print(mod-1)
else:
    print(res-1)


# sum<d , pos, chk-0,1 dp[pos][sum][chk]

Submission status: Runtime Error

Solution code:
def solve(pos,sum1,f):
    
    res=0
    
    
    if(pos==len(k)):
        if(sum1%d==0):
            return 1
        else:
            return 0
    if(dp[pos][sum1][f]!=-1):
        return dp[pos][sum1][f]

    if(f==0):
        lmt=k[pos]
    else:
        lmt=9

    for dig in range(lmt+1):
        nsum=sum1
        nf=f
        if(f==0)and(dig<lmt):
            nf=1
        nsum+=dig
        nsum%=d
        res+=solve(pos+1,nsum,nf)
    if(res>mod):
        res%=mod
    dp[pos][sum1][f]=res
    return res

mod=1000000007  

    
k=list(map(int,input()))
d=int(input())
dp=[[[-1,-1] for i in range(d)] for j in range(len(k)+1)]


res=solve(0,0,0)
if(res==-1):
    print(mod-1)
else:
    print(res-1)


# sum<d , pos, chk-0,1 dp[pos][sum][chk]

Submission status: Runtime Error

Solution code:
def solve(pos,sum1,f):
    
    res=0
    
    if(pos==len(k)):
        if(sum1%d==0):
            return 1
        else:
            return 0
    if(dp[pos][sum1][f]!=-1):
        return dp[pos][sum1][f]

    if(f==0):
        lmt=k[pos]
    else:
        lmt=9

    for dig in range(lmt+1):
        nsum=sum1
        nf=f
        if(f==0)and(dig<lmt):
            nf=1
        nsum+=dig
        nsum%=d
        res+=solve(pos+1,nsum,nf)
    if(res>mod):
        res%=mod
    dp[pos][sum1][f]=res
    return res

mod=1000000007  

    
k=list(map(int,input()))
d=int(input())
dp=[[[-1,-1] for i in range(d)] for j in range(len(k))]


res=solve(0,0,0)
if(res==-1):
    print(mod-1)
else:
    print(res-1)


# sum<d , pos, chk-0,1 dp[pos][sum][chk]

Submission status: Runtime Error

Solution code:
# @author 

import sys

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

        k = input()
        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: Runtime Error

Solution code:
# @author 

import sys

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

        k = input()
        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: Runtime Error

Solution code:
# @author 

import sys

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

        k = input()
        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: Runtime Error

Solution code:
# @author 

import sys

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

        k = input()
        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: Runtime Error

Solution code:
# @author 

import sys

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

        k = input()
        # print(len(k))
        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):
                # print(l, r)
                # lo, hi = min((r - 1) % d, (r - 9) % d), max((r - 1) % d, (r - 9) % d)
                # assert((pre[l - 1][hi] - pre[l - 1][lo - 1]) == sum(dp[l - 1][(-lm + r) % d] for lm in range(1, 10)))
                # dp[l][r] = (dp[l - 1][r] + (pre[l - 1][hi] - pre[l - 1][lo - 1])) % 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: Runtime Error

Solution code:
# @author 

import sys

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

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

        s = len(str(k))
        dp = [[0] * d for _ in range(s)]
        dp[0][0] = 1
        for i in range(10):
            dp[1][i % d] += 1
        for l in range(2, s):
            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


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

        print((ans - 1) % MOD)

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

solver.solve()

Submission status: Runtime Error

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

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

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

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

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

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

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

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


print((answer - 1) % M)

Submission status: Runtime Error

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

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

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

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

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

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

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

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


print((answer - 1) % M)

Submission status: Runtime Error

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

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

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

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

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

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

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


print((answer - 1) % M)

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
K = list(map(int, input().strip()))
D = int(input())
mod = 10**9+7
a = 0
for i in range(1, J+1):
    if sum(map(int, str(i))) % D == 0:
        a += 1
print(a%mod)
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: Runtime Error

Solution code:
K = list(map(int, J.strip()))
D = int(input())
mod = 10**9+7
a = 0
for i in range(1, J+1):
    if sum(map(int, str(i))) % D == 0:
        a += 1
print(a%mod)
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: Runtime Error

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


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

Submission status: Runtime Error

Solution code:
# coding: utf-8

from itertools import product as prod
import sys
input = sys.stdin.readline

mod = int(1e9 + 7)

def f2(K, D):
    l = len(K)
    dp = [[[0] * D for _ in range(2)] for _ in range(l + 1)]
    dp[0][0][0] = 1

    for i, j, d in prod(range(l), range(2), range(D)):
        maxk = 9 if j else int(K[i])
        dpij = dp[i][j]
        dpi1 = dp[i + 1]
        for k in range(maxk + 1):
            dpi1j = dpi1[j or k < maxk]
            d_ = d + k
            if d_ >= D:
                d_ -= D
            dpi1j[d_] += dpij[d]
            if dpi1j[d_] >= mod:
                dpi1j[d_] -= mod
    # K = 0 の場合が含まれるので -1
    return((dp[-1][0][0] + dp[-1][1][0] - 1 + mod) % mod)

K = input().rstrip() # 1 <= K <= 10^10000
D = int(input()) # 1 <= D <= 100

print(f2(K, D))

Submission status: Runtime Error

Solution code:
# coding: utf-8

from itertools import product as prod
import sys
input = sys.stdin.readline

mod = int(1e9 + 7)

def f2(K, D):
    l = len(K)
    dp = [[[0] * D for _ in range(2)] for _ in range(l + 1)]
    dp[0][0][0] = 1

    for i, j, d in prod(range(l), range(2), range(D)):
        maxk = 9 if j else int(K[i])
        dpij = dp[i][j]
        dpi1 = dp[i + 1]
        for k in range(maxk + 1):
            dpi1j = dpi1[j or k < maxk]
            d_ = d + k
            if d_ >= D:
                d_ -= D
            dpi1j[d_] += dpij[d]
            if dpi1j[d_] >= mod:
                dpi1j[d_] -= mod
    # K = 0 の場合が含まれるので -1
    return((dp[-1][0][0] + dp[-1][1][0] - 1 + mod) % mod)

K = input().rstrip() # 1 <= K <= 10^10000
D = int(input()) # 1 <= D <= 100
print(f2(K, D))