stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include<cstdio>

#include<cstring>

#include<string>

#include<vector>

#include<iostream>

#include<algorithm>

using namespace std;

typedef long long ll;

const int maxn=1e4+10;

const ll mod=1e9+7;

ll dp[maxn][120];

int a[maxn],d;

char num[maxn];

ll dfs(int pos,int sum,bool limit)

{

    if(pos==-1)

        return sum%d==0?1:0;

    if(!limit&&dp[pos][sum]!=-1)

        return dp[pos][sum];

    int up=limit?a[pos]:9;

    ll ans=0;

    for(int i=0; i<=up; i++)

    {

        int tmp=0;

        tmp=(i+sum)%d;

        ans=(ans+dfs(pos-1,tmp,limit&&i==a[pos]))%mod;

    }

    if(!limit)

        dp[pos][sum]=ans%mod;

    return ans%mod;

}

ll solve()

{

    int pos=0;

    int len=strlen(num);

    for(int i=len-1; i>=0; i--)

        a[pos++]=num[i]-'0';

    return dfs(pos-1,0,true);

}

int main()

{

    memset(dp,-1,sizeof(dp));

    scanf("%s",num);

    scanf("%d",&d);

    printf("%lld\n",(solve()-1+mod)%mod);

    return 0;

}


// Faster C++ solution for the same problem (measured speedup: 10.24064125983954x):
#include <bits/stdc++.h>

using namespace std;

const int N = (int)1e4 + 100;

const int mod = (int)1e9 + 7;

const long long INF = (long long)1e18;

int dd;

long long d[N][100];

long long get(string s){

    int n = s.size();

    for(int i = 0;i < 10;i++)d[1][(i % dd)]++;

    for(int i = 2;i <= n;i++){

        for(int m = 0;m < dd;m++){

            for(int j = 0;j < 10;j++){

                d[i][m] += d[i - 1][(((m - j) % dd) + dd) % dd];

                d[i][m] %= mod;

            }

        }

    }

    long long ans = 0;

    int ss = 0;

    for(int i = 0;i < n;i++){

        for(int j = 0;j < (s[i] - '0');j++){

             ss += j;

            if((i == n - 1) && ((ss % dd) == 0))ans++;

            ans += d[n - i - 1][(((dd - ss) % dd) + dd) % dd];

            ans %= mod;

            ss-=j;

        }

        ss += (s[i] - '0');

        if((i == n - 1) && ((ss % dd) == 0))ans++;

    }

    return (ans - 1 + mod) % mod;

}

int main(){

	ios_base::sync_with_stdio(0);

	cin.tie(0);

	cout.tie(0);

    string s;

    cin >> s >> dd;

    cout << get(s);

    return 0;

}
// Slower C++ solution:
#include<cstdio>

#include<cstring>

#include<string>

#include<vector>

#include<iostream>

#include<algorithm>

using namespace std;

typedef long long ll;

const int maxn=1e4+10;

const ll mod=1e9+7;

ll dp[maxn][120];

int a[maxn],d;

char num[maxn];

ll dfs(int pos,int sum,bool limit)

{

    if(pos==-1)

        return sum%d==0?1:0;

    if(!limit&&dp[pos][sum]!=-1)

        return dp[pos][sum];

    int up=limit?a[pos]:9;

    ll ans=0;

    for(int i=0; i<=up; i++)

    {

        int tmp=0;

        tmp=(i+sum)%d;

        ans=(ans+dfs(pos-1,tmp,limit&&i==a[pos]))%mod;

    }

    if(!limit)

        dp[pos][sum]=ans%mod;

    return ans%mod;

}

ll solve()

{

    int pos=0;

    int len=strlen(num);

    for(int i=len-1; i>=0; i--)

        a[pos++]=num[i]-'0';

    return dfs(pos-1,0,true);

}

int main()

{

    memset(dp,-1,sizeof(dp));

    scanf("%s",num);

    scanf("%d",&d);

    printf("%lld\n",(solve()-1+mod)%mod);

    return 0;

}


// Faster C++ solution for the same problem (measured speedup: 1.129880821656163x):
#include <bits/stdc++.h>

#define ll long long

#define re register

#define IL inline

using namespace std;

const int maxn=1e4+5;

const int maxd=100+5;

const int mod=1e9+7;

template<typename T> void fread(T &x){

	T f=1;x=0;

	char s=getchar();

	while(s<'0' || s>'9'){if(s=='-') f=-1;s=getchar();}

	while(s>='0' && s<='9'){x=(x<<3)+(x<<1)+s-48;s=getchar();}

	x*=f;

}

string s;

int d,pos[maxn];

ll dp[maxn][maxd];

ll dfs(int st,int sta,bool lim){

	if(st==s.size()) return dp[st][sta]=(sta==0);

	if(!lim && dp[st][sta]!=-1) return dp[st][sta];

	int up=lim?pos[st]:9;

	ll ret=0;

	for(re int i=0;i<=up;i++){

		(ret+=dfs(st+1,(sta+i)%d,lim&&(i==pos[st])))%=mod;

	}

	if(!lim) dp[st][sta]=ret;

	return ret;

}

int main(){

	//freopen(".in","r",stdin);

	//freopen(".out","w",stdout);

	memset(dp,-1,sizeof dp);

	cin>>s>>d;

	for(re int i=0;i<s.size();i++) pos[i]=s[i]-'0';

	cout<<(dfs(0,0,1)-1+mod)%mod<<endl;

	return 0;

}
// Slower C++ solution:
#include <iostream>

#include <sstream>

#include <algorithm>

#include <cstdio>

#include <math.h>

#include <set>

#include <map>

#include <queue>

#include <string>

#include <string.h>

#include <bitset>

#define REP(i,a,n) for(int i=a;i<=n;++i)

#define PER(i,a,n) for(int i=n;i>=a;--i)

#define hr putchar(10)

#define pb push_back

#define lc (o<<1)

#define rc (lc|1)

#define mid ((l+r)>>1)

#define ls lc,l,mid

#define rs rc,mid+1,r

#define x first

#define y second

#define io std::ios::sync_with_stdio(false)

#define endl '\n'

#define DB(a) ({REP(__i,1,n) cout<<a[__i]<<' ';hr;})

using namespace std;

typedef long long ll;

typedef pair<int,int> pii;

const int P = 1e9+7, INF = 0x3f3f3f3f;

ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}

ll qpow(ll a,ll n) {ll r=1%P;for (a%=P;n;a=a*a%P,n>>=1)if(n&1)r=r*a%P;return r;}

ll inv(ll x){return x<=1?1:inv(P%x)*(P-P/x)%P;}

inline int rd() {int x=0;char p=getchar();while(p<'0'||p>'9')p=getchar();while(p>='0'&&p<='9')x=x*10+p-'0',p=getchar();return x;}

//head







const int N = 1e4+10;

int d, n;

char s[N];

int dp[N][111];



int solve(int x,int sum,bool z,bool lim) {

	if (x==n) return !sum;

	if (!lim&&!z&&~dp[x][sum]) return dp[x][sum];

	int ans = 0, mx=lim?s[x]-'0':9;

	REP(i,0,mx) (ans+=solve(x+1,(sum+i)%d,z&&!i,lim&&i==mx))%=P;

	return !lim&&!z?dp[x][sum]=ans:ans;

}



int main() {

	cin>>s>>d;

	memset(dp,-1,sizeof dp);

	n = strlen(s);

	int ans = solve(0,0,1,1)-1;

	if (ans<0) ans+=P;

	printf("%d\n", ans);

}
















// Faster C++ solution for the same problem (measured speedup: 5.449149026397749x):
#include<bits/stdc++.h>

#define REP(x,y,z) for(int x=y;x<=z;x++)

#define MSET(x,y) memset(x,y,sizeof(x))

#define M 10005

#define MOD 1000000007

using namespace std;

using LL = long long;

char in[M];

int dp[M][102][2], d, n;

int main()

{

    scanf("%s %d", in+1, &d);

    n = strlen(in+1);



    REP(i,0,in[1]-'0'-1) dp[1][i%d][0] += 1;

    dp[1][(in[1]-'0')%d][1] += 1;



    REP(i,1,n-1) REP(j,0,d-1) REP(k,0,1) if (dp[i][j][k]) {



        int cd = in[i+1] - '0';

        REP(nd,0,9) {

            if (k==1 && nd>cd) continue;



            int i2 = i+1;

            int j2 = (j + nd) % d;

            int k2 = k==1 && nd==cd;

            dp[i2][j2][k2] += dp[i][j][k];

            dp[i2][j2][k2] %= MOD;

        }

    }



    int ans = 0;

    ans = (ans + dp[n][0][0]) % MOD;

    ans = (ans + dp[n][0][1]) % MOD;

    printf("%d\n", (ans+MOD-1)%MOD);

    return 0;

}
// Slower C++ solution:
#include<cstdio>

#include<cstring>

#include<string>

#include<vector>

#include<iostream>

#include<algorithm>

using namespace std;

typedef long long ll;

const int maxn=1e4+10;

const ll mod=1e9+7;

ll dp[maxn][120];

int a[maxn],d;

char num[maxn];

ll dfs(int pos,int sum,bool limit)

{

    if(pos==-1)

        return sum%d==0?1:0;

    if(!limit&&dp[pos][sum]!=-1)

        return dp[pos][sum];

    int up=limit?a[pos]:9;

    ll ans=0;

    for(int i=0; i<=up; i++)

    {

        int tmp=0;

        tmp=(i+sum)%d;

        ans=(ans+dfs(pos-1,tmp,limit&&i==a[pos]))%mod;

    }

    if(!limit)

        dp[pos][sum]=ans%mod;

    return ans%mod;

}

ll solve()

{

    int pos=0;

    int len=strlen(num);

    for(int i=len-1; i>=0; i--)

        a[pos++]=num[i]-'0';

    return dfs(pos-1,0,true);

}

int main()

{

    memset(dp,-1,sizeof(dp));

    scanf("%s",num);

    scanf("%d",&d);

    printf("%lld\n",(solve()-1+mod)%mod);

    return 0;

}


// Faster C++ solution for the same problem (measured speedup: 10.846194261138319x):
#include<bits/stdc++.h>

#define REP(x,y,z) for(int x=y;x<=z;x++)

#define MSET(x,y) memset(x,y,sizeof(x))

#define M 10005

#define MOD 1000000007

using namespace std;

using LL = long long;

char in[M];

int dp[M][102][2], d, n;

int main()

{

    scanf("%s %d", in+1, &d);

    n = strlen(in+1);



    REP(i,0,in[1]-'0'-1) dp[1][i%d][0] += 1;

    dp[1][(in[1]-'0')%d][1] += 1;



    REP(i,1,n-1) REP(j,0,d-1) REP(k,0,1) if (dp[i][j][k]) {



        int cd = in[i+1] - '0';

        REP(nd,0,9) {

            if (k==1 && nd>cd) continue;



            int i2 = i+1;

            int j2 = (j + nd) % d;

            int k2 = k==1 && nd==cd;

            dp[i2][j2][k2] += dp[i][j][k];

            dp[i2][j2][k2] %= MOD;

        }

    }



    int ans = 0;

    ans = (ans + dp[n][0][0]) % MOD;

    ans = (ans + dp[n][0][1]) % MOD;

    printf("%d\n", (ans+MOD-1)%MOD);

    return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

#define ll long long

#define re register

#define IL inline

using namespace std;

const int maxn=1e4+5;

const int maxd=100+5;

const int mod=1e9+7;

template<typename T> void fread(T &x){

	T f=1;x=0;

	char s=getchar();

	while(s<'0' || s>'9'){if(s=='-') f=-1;s=getchar();}

	while(s>='0' && s<='9'){x=(x<<3)+(x<<1)+s-48;s=getchar();}

	x*=f;

}

string s;

int d,pos[maxn];

ll dp[maxn][maxd];

ll dfs(int st,int sta,bool lim){

	if(st==s.size()) return dp[st][sta]=(sta==0);

	if(!lim && dp[st][sta]!=-1) return dp[st][sta];

	int up=lim?pos[st]:9;

	ll ret=0;

	for(re int i=0;i<=up;i++){

		(ret+=dfs(st+1,(sta+i)%d,lim&&(i==pos[st])))%=mod;

	}

	if(!lim) dp[st][sta]=ret;

	return ret;

}

int main(){

	//freopen(".in","r",stdin);

	//freopen(".out","w",stdout);

	memset(dp,-1,sizeof dp);

	cin>>s>>d;

	for(re int i=0;i<s.size();i++) pos[i]=s[i]-'0';

	cout<<(dfs(0,0,1)-1+mod)%mod<<endl;

	return 0;

}


// Faster C++ solution for the same problem (measured speedup: 9.599414427833302x):
#include<bits/stdc++.h>

#define REP(x,y,z) for(int x=y;x<=z;x++)

#define MSET(x,y) memset(x,y,sizeof(x))

#define M 10005

#define MOD 1000000007

using namespace std;

using LL = long long;

char in[M];

int dp[M][102][2], d, n;

int main()

{

    scanf("%s %d", in+1, &d);

    n = strlen(in+1);



    REP(i,0,in[1]-'0'-1) dp[1][i%d][0] += 1;

    dp[1][(in[1]-'0')%d][1] += 1;



    REP(i,1,n-1) REP(j,0,d-1) REP(k,0,1) if (dp[i][j][k]) {



        int cd = in[i+1] - '0';

        REP(nd,0,9) {

            if (k==1 && nd>cd) continue;



            int i2 = i+1;

            int j2 = (j + nd) % d;

            int k2 = k==1 && nd==cd;

            dp[i2][j2][k2] += dp[i][j][k];

            dp[i2][j2][k2] %= MOD;

        }

    }



    int ans = 0;

    ans = (ans + dp[n][0][0]) % MOD;

    ans = (ans + dp[n][0][1]) % MOD;

    printf("%d\n", (ans+MOD-1)%MOD);

    return 0;

}
// Slower C++ solution:
#include <map>

#include <set>

#include <ctime>

#include <cmath>

#include <queue>

#include <stack>

#include <ctime>

#include <string>

#include <vector>

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <algorithm>

//#include <random>

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

typedef double db;

#define PB push_back

#define MP make_pair

#define INF 1073741824

#define inf 1152921504606846976

#define pi 3.14159265358979323846

//#pragma comment(linker,"/STACK:10240000,10240000")

//mt19937 rand_(time(0));

const int N=3e5+7,M=2e6;

const long long mod=1e9+7;

inline int read(){int ret=0;char ch=getchar();bool f=1;for(;!isdigit(ch);ch=getchar()) f^=!(ch^'-');for(;isdigit(ch);ch=getchar()) ret=(ret<<1)+(ret<<3)+ch-48;return f?ret:-ret;}

ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}

ll ksm(ll a,ll b,ll mod){int ans=1;while(b){if(b&1) ans=(ans*a)%mod;a=(a*a)%mod;b>>=1;}return ans;}

ll inv2(ll a,ll mod){return ksm(a,mod-2,mod);}//逆元

//int head[N],NEXT[M],ver[M],tot;void link(int u,int v){ver[++tot]=v;NEXT[tot]=head[u];head[u]=tot;}



char str[12000];

int num[12000];

ll dp[12000][120];

int k;

ll dfs(int pos,bool up,int sum){

    if(pos==1){

        if(sum%k==0) return 1;

        return 0;

    }

    if(dp[pos][sum]!=-1&&!up) return dp[pos][sum];

    ll res=0;

    for(int i=0;i<=(up?num[pos-1]:9);i++){

        if(up&&i==num[pos-1]){

            res+=dfs(pos-1,1,(sum+i)%k);

        }

        else {

            res+=dfs(pos-1,0,(sum+i)%k);

        }

//        cout<<res<<endl;

        res%=mod;

    }

//    cout<<pos<<' '<<sum<<' '<<res<<endl;

    if(!up) dp[pos][sum]=res;

    return res;

}

ll solve(){

    int len=strlen(str);

    int ant=0;

    for(int i=len-1;i>=0;i--){

        num[++ant]=str[i]-'0';

//        cout<<num[ant]<<' ';

    }

//    cout<<endl;

    return dfs(ant+1,1,0);

}

int main(){

    //freopen("1.txt","r",stdin);

    //ios::sync_with_stdio(false);

    scanf("%s",str);

    scanf("%d",&k);

    memset(dp,-1,sizeof(dp));

    printf("%lld\n",(solve()-1+mod)%mod);

    //cout << "time: " << (long long)clock() * 1000 / CLOCKS_PER_SEC << " ms" << endl;

    return 0;

}








// Faster C++ solution for the same problem (measured speedup: 12.472634329381181x):
#include <bits/stdc++.h>

using namespace std;

const int N = 10050;

const long long mod = 1e9 + 7;

int d, n;

string num;

long long mem[N][105][2];

bool vis[N][105][2];



long long dp(int idx, int m, int last) {

	if (idx == n) {

		return (!m) ? 1 : 0;

	}

	if (vis[idx][m][last]) {

		return mem[idx][m][last];

	}

	vis[idx][m][last] = true;



	long long ans = 0;

	for (int i = 0; i < 10; i++) {

		if (last && i == num[idx] - '0') {

			ans = (ans + dp(idx + 1, (m + i) % d, 1)) % mod;

			break;

		}

		ans = (ans + dp(idx + 1, (m + i) % d, 0)) % mod;

	}



	return mem[idx][m][last] = ans;

}



int main() {

	ios_base::sync_with_stdio(0);

	cin.tie(0);

	

	cin >> num >> d;

	n = num.size();



	cout << (mod + dp(0, 0, 1) - 1) % mod << '\n';



	return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

#define ll long long

int D;

int len,a[10009];

ll dp[10009][130];

const ll mod=1e9+7;

ll dfs(int pos,int sum,int limit)

{

    if(pos>len) return sum?0:1;

    if(dp[pos][sum]!=-1&&!limit)return dp[pos][sum];

    ll ret=0;

    int res=limit?a[pos]:9;

    for(int i=0;i<=res;i++)

    {

        ret=(ret+dfs(pos+1,(sum+i)%D,limit&&(i==res)))%mod;

    }

    return (!limit)?dp[pos][sum]=ret:ret;

}

ll part(char s[])

{

    len=0;int lenn=strlen(s+1);

    for(int i=1;i<=lenn;i++)a[++len]=s[i]-'0';

    memset(dp,-1,sizeof dp);

    return dfs(1,0,1);

}

char str[10009];

int main()

{

    scanf("%s%d",str+1,&D);

    printf("%lld\n",(part(str)-1+mod)%mod);

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 11.346756569239203x):
#include <bits/stdc++.h>

using namespace std;

const int N = 10050;

const long long mod = 1e9 + 7;

int d, n;

string num;

long long mem[N][105][2];

bool vis[N][105][2];



long long dp(int idx, int m, int last) {

	if (idx == n) {

		return (!m) ? 1 : 0;

	}

	if (vis[idx][m][last]) {

		return mem[idx][m][last];

	}

	vis[idx][m][last] = true;



	long long ans = 0;

	for (int i = 0; i < 10; i++) {

		if (last && i == num[idx] - '0') {

			ans = (ans + dp(idx + 1, (m + i) % d, 1)) % mod;

			break;

		}

		ans = (ans + dp(idx + 1, (m + i) % d, 0)) % mod;

	}



	return mem[idx][m][last] = ans;

}



int main() {

	ios_base::sync_with_stdio(0);

	cin.tie(0);

	

	cin >> num >> d;

	n = num.size();



	cout << (mod + dp(0, 0, 1) - 1) % mod << '\n';



	return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

#define ll long long

int D;

int len,a[10009];

ll dp[10009][130];

const ll mod=1e9+7;

ll dfs(int pos,int sum,int limit)

{

    if(pos>len) return sum?0:1;

    if(dp[pos][sum]!=-1&&!limit)return dp[pos][sum];

    ll ret=0;

    int res=limit?a[pos]:9;

    for(int i=0;i<=res;i++)

    {

        ret=(ret+dfs(pos+1,(sum+i)%D,limit&&(i==res)))%mod;

    }

    return (!limit)?dp[pos][sum]=ret:ret;

}

ll part(char s[])

{

    len=0;int lenn=strlen(s+1);

    for(int i=1;i<=lenn;i++)a[++len]=s[i]-'0';

    memset(dp,-1,sizeof dp);

    return dfs(1,0,1);

}

char str[10009];

int main()

{

    scanf("%s%d",str+1,&D);

    printf("%lld\n",(part(str)-1+mod)%mod);

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 11.363073069419285x):
#include<bits/stdc++.h>

#define pb push_back

#define mp make_pair

#define se second

#define fi first

#define _ std::ios_base::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

typedef long double ld;

const int mod = 1e9+7;

const int LOG = 17;

const int N = 5e5+123;

const ll INF = (ll)1e18 + 7;



int dp[10010][110];



int main()

{

    string s;

    cin >> s;

    int d;

    cin >> d;

    dp[0][0] = 1;

    for (int i = 0; i < s.size(); i++) {

        for (int j = 0; j < d; j++) {

            for (int k = 0; k <= 9; k++) {

                dp[i + 1][(j + k) % d] += dp[i][j];

                dp[i + 1][(j + k) % d] %= mod;

            }

        }

    }

    int sum = 0;

    int ans = 0;

    for (int i = 0; i < s.size(); i++) {

        for (int j = 0; j < s[i] - '0'; j++) {

            ans += dp[(int)s.size() - i - 1][(d - (sum + j) % d) % d];

            ans %= mod;

        }

        sum += s[i] - '0';

    }

    if (sum % d == 0) {

        ans++;

    }

    ans += mod - 1;

    ans %= mod;

    cout << ans;

    return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

#define ll long long

int D;

int len,a[10009];

ll dp[10009][130];

const ll mod=1e9+7;

ll dfs(int pos,int sum,int limit)

{

    if(pos>len) return sum?0:1;

    if(dp[pos][sum]!=-1&&!limit)return dp[pos][sum];

    ll ret=0;

    int res=limit?a[pos]:9;

    for(int i=0;i<=res;i++)

    {

        ret=(ret+dfs(pos+1,(sum+i)%D,limit&&(i==res)))%mod;

    }

    return (!limit)?dp[pos][sum]=ret:ret;

}

ll part(char s[])

{

    len=0;int lenn=strlen(s+1);

    for(int i=1;i<=lenn;i++)a[++len]=s[i]-'0';

    memset(dp,-1,sizeof dp);

    return dfs(1,0,1);

}

char str[10009];

int main()

{

    scanf("%s%d",str+1,&D);

    printf("%lld\n",(part(str)-1+mod)%mod);

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 11.123076986898843x):
//bayemirov                                       

#include <bits/stdc++.h>

 

using namespace std;

 

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

 

typedef long long ll;

 

#define pb push_back

 

const int MOD = 1e9 + 7;

const int N = 1e5;

 

int dp[N][100];

 

void add(int& x, int y) {

	x += y;

	if (x > MOD) x -= MOD;

}

 

int main() {

	ios_base::sync_with_stdio(0);

	cin.tie(0); cout.tie(0);

	string a;

	cin >> a;

	int b;

	cin >> b;

	int k = a.size();

	dp[0][0] = 1;

	for (int i = 1; i < k; i++) 

		for (int j = 0; j < b; j++) 

			for(int x = 0; x < 10; ++x)

				add(dp[i][j], dp[i - 1][((j - x) % b + b) % b]);

	int ans = 0;

	int sum = 0;

	for (int i = 0; i < k; i++) {

		for (int j = 0; j < (a[i] - '0'); j++)

			add(ans, dp[k - i - 1][((b - sum - j) % b + b) % b]);

		sum += (a[i] - '0');

		sum %= b;

	}

	if(sum == 0)

		ans++;

	cout << ans - 1;

	return 0;

}                    

// ez
// Slower C++ solution:
#include <map>

#include <set>

#include <ctime>

#include <cmath>

#include <queue>

#include <stack>

#include <ctime>

#include <string>

#include <vector>

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <algorithm>

//#include <random>

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

typedef double db;

#define PB push_back

#define MP make_pair

#define INF 1073741824

#define inf 1152921504606846976

#define pi 3.14159265358979323846

//#pragma comment(linker,"/STACK:10240000,10240000")

//mt19937 rand_(time(0));

const int N=3e5+7,M=2e6;

const long long mod=1e9+7;

inline int read(){int ret=0;char ch=getchar();bool f=1;for(;!isdigit(ch);ch=getchar()) f^=!(ch^'-');for(;isdigit(ch);ch=getchar()) ret=(ret<<1)+(ret<<3)+ch-48;return f?ret:-ret;}

ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}

ll ksm(ll a,ll b,ll mod){int ans=1;while(b){if(b&1) ans=(ans*a)%mod;a=(a*a)%mod;b>>=1;}return ans;}

ll inv2(ll a,ll mod){return ksm(a,mod-2,mod);}//逆元

//int head[N],NEXT[M],ver[M],tot;void link(int u,int v){ver[++tot]=v;NEXT[tot]=head[u];head[u]=tot;}



char str[12000];

int num[12000];

ll dp[12000][120];

int k;

ll dfs(int pos,bool up,int sum){

    if(pos==1){

        if(sum%k==0) return 1;

        return 0;

    }

    if(dp[pos][sum]!=-1&&!up) return dp[pos][sum];

    ll res=0;

    for(int i=0;i<=(up?num[pos-1]:9);i++){

        if(up&&i==num[pos-1]){

            res+=dfs(pos-1,1,(sum+i)%k);

        }

        else {

            res+=dfs(pos-1,0,(sum+i)%k);

        }

//        cout<<res<<endl;

        res%=mod;

    }

//    cout<<pos<<' '<<sum<<' '<<res<<endl;

    if(!up) dp[pos][sum]=res;

    return res;

}

ll solve(){

    int len=strlen(str);

    int ant=0;

    for(int i=len-1;i>=0;i--){

        num[++ant]=str[i]-'0';

//        cout<<num[ant]<<' ';

    }

//    cout<<endl;

    return dfs(ant+1,1,0);

}

int main(){

    //freopen("1.txt","r",stdin);

    //ios::sync_with_stdio(false);

    scanf("%s",str);

    scanf("%d",&k);

    memset(dp,-1,sizeof(dp));

    printf("%lld\n",(solve()-1+mod)%mod);

    //cout << "time: " << (long long)clock() * 1000 / CLOCKS_PER_SEC << " ms" << endl;

    return 0;

}








// Faster C++ solution for the same problem (measured speedup: 1.3384906701751302x):
#include <bits/stdc++.h>

#define re register

#define SIZE 10005

#define LL long long 

#define MOD 1000000007

using namespace std;

string k;

int d;

int maxn[SIZE],cnt;

LL dp[SIZE][105];

inline LL dfs(int pos,int sta,bool lim)

{

	if(pos>cnt)

		return sta==0?1:0;

	if(!lim && dp[pos][sta]!=-1)

		return dp[pos][sta];

	int up=lim?maxn[pos]:9;

	LL ret=0;

	for(re int i=0;i<=up;++i)

		ret=(ret+dfs(pos+1,(sta+i)%d,lim&&(i==maxn[pos])))%MOD;

	if(!lim)

		dp[pos][sta]=ret;

	return ret;

}

inline LL work()

{

	memset(dp,-1,sizeof(dp));

	cnt=k.size()-1;

	for(re int i=0;i<=cnt;++i)

		maxn[i]=k[i]-'0'; 

	return dfs(0,0,1);

}

int main()

{

	cin>>k;

	cin>>d;

	LL ans=(work()-1+MOD)%MOD;

	printf("%lld\n",ans);

	return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;

#define ll long long

int D;

int len,a[10009];

ll dp[10009][130];

const ll mod=1e9+7;

ll dfs(int pos,int sum,int limit)

{

    if(pos>len) return sum?0:1;

    if(dp[pos][sum]!=-1&&!limit)return dp[pos][sum];

    ll ret=0;

    int res=limit?a[pos]:9;

    for(int i=0;i<=res;i++)

    {

        ret=(ret+dfs(pos+1,(sum+i)%D,limit&&(i==res)))%mod;

    }

    return (!limit)?dp[pos][sum]=ret:ret;

}

ll part(char s[])

{

    len=0;int lenn=strlen(s+1);

    for(int i=1;i<=lenn;i++)a[++len]=s[i]-'0';

    memset(dp,-1,sizeof dp);

    return dfs(1,0,1);

}

char str[10009];

int main()

{

    scanf("%s%d",str+1,&D);

    printf("%lld\n",(part(str)-1+mod)%mod);

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.21766800850551x):
#include <bits/stdc++.h>

#define re register

#define SIZE 10005

#define LL long long 

#define MOD 1000000007

using namespace std;

string k;

int d;

int maxn[SIZE],cnt;

LL dp[SIZE][105];

inline LL dfs(int pos,int sta,bool lim)

{

	if(pos>cnt)

		return sta==0?1:0;

	if(!lim && dp[pos][sta]!=-1)

		return dp[pos][sta];

	int up=lim?maxn[pos]:9;

	LL ret=0;

	for(re int i=0;i<=up;++i)

		ret=(ret+dfs(pos+1,(sta+i)%d,lim&&(i==maxn[pos])))%MOD;

	if(!lim)

		dp[pos][sta]=ret;

	return ret;

}

inline LL work()

{

	memset(dp,-1,sizeof(dp));

	cnt=k.size()-1;

	for(re int i=0;i<=cnt;++i)

		maxn[i]=k[i]-'0'; 

	return dfs(0,0,1);

}

int main()

{

	cin>>k;

	cin>>d;

	LL ans=(work()-1+MOD)%MOD;

	printf("%lld\n",ans);

	return 0;

}