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

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <algorithm>

#define IOS ios::sync_with_stdio(false)

using namespace std;

#define inf (0x3f3f3f3f)

typedef long long int LL;



#include <iostream>

#include <sstream>

#include <vector>

#include <set>

#include <map>

#include <queue>

#include <string>

const int maxn = 1e6 + 20;

int dp[maxn];

void work() {

    int n, t;

    scanf("%d%d", &n, &t);

    if (n == 1) while(1);

    int mi = (1LL << 31) - 1;

    int mx = -((1LL << 31) - 1);

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

        int x;

        scanf("%d", &x);

        dp[i] = max(0, x - mi);

        mi = min(mi, x);

        mx = max(mx, dp[i]);

    }

    int tim = 0;

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

        tim += dp[i] == mx;

    }

    int ans = tim;

    cout << ans << endl;

}



int main() {

#ifdef local

    freopen("data.txt","r",stdin);

#endif

    work();

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.230424581120068x):
#include <cstdio>

#include <algorithm>

using namespace std;

const int MAXN=110000;

const int INF=0X3F3F3F3F;

int a[MAXN];

int main()

{

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

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

	int n, t;

	scanf("%d%d", &n, &t);

	for (int i=1; i<=n; i++) scanf("%d", &a[i]);

	int mx=0, ans=0;

	for (int i=1, mi=INF; i<=n; i++)

	{

		mi=min(mi, a[i]);

		if (a[i]-mi>mx) mx=a[i]-mi, ans=0;

		if (a[i]-mi==mx) ans++;

	}

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

	return 0;

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

using namespace std;



const int offset = 1 << 20;

int st[2 * offset];

int in[offset];



int minimum(int a, int b) {

    a += offset;

    b += offset;



    int rv = 1e9 + 7;

    while(a <= b) {

        if(a % 2 == 1) rv = min(rv, st[a++]);

        if(b % 2 == 0) rv = min(rv, st[b--]);

        a /= 2; b /= 2;

    }

    return rv;

}





void add(int k, int x) {

    k += offset;

    st[k] = x;

    for(k /= 2; k >= 1; k /= 2) {

        st[k] = min(st[k * 2], st[k * 2 + 1]);

    }

}



int main() {

    int n, k;

    scanf("%d %d", &n, &k);



    for(int i = offset; i < offset * 2; i++) st[i] = 1e9 + 7;

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

        scanf("%d", &in[i]);

        add(i, in[i]);

    }



    int maxx = 0;

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

        int v = minimum(0, i - 1);

        if(in[i] - v > maxx) {

           maxx = in[i] - v;

        }

    }



    int res = 0;

    set< int> st;

    st.insert(in[0]);

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

        if(st.count(in[i] - maxx)) res++;

        st.insert(in[i]);

    }

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

}

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

using namespace std;



const int offset = 1 << 20;

int st[2 * offset];

int in[offset];



int minimum(int a, int b) {

    a += offset;

    b += offset;



    int rv = 1e9 + 7;

    while(a <= b) {

        if(a % 2 == 1) rv = min(rv, st[a++]);

        if(b % 2 == 0) rv = min(rv, st[b--]);

        a /= 2; b /= 2;

    }

    return rv;

}





void add(int k, int x) {

    k += offset;

    st[k] = x;

    for(k /= 2; k >= 1; k /= 2) {

        st[k] = min(st[k * 2], st[k * 2 + 1]);

    }

}



int main() {

    int n, k;

    scanf("%d %d", &n, &k);



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

        scanf("%d", &in[i]);

        add(i, in[i]);

    }



    int maxx = 0;

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

        int v = minimum(0, i - 1);

        if(in[i] - v > maxx) {

           maxx = in[i] - v;

        }

    }



    int res = 0;

    set< int> st;

    st.insert(in[0]);

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

        if(st.count(in[i] - maxx)) res++;

        st.insert(in[i]);

    }

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

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



using namespace std;



// Header files, namespaces,

// macros as defined above

#include <ext/pb_ds/assoc_container.hpp>

#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;



#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>





#define f first

#define s second

#define db long double

#define pb push_back

#define sz(c) (c).size()

#define all(c) (c).begin(),(c).end()



typedef long long ll;

typedef pair <int , int> ii;

typedef pair <ii , int> iii;

typedef vector <int> vi;

typedef vector <ii> vii;

typedef vector <iii> viii;

typedef vector <vi> vvi;

typedef vector <vii> vvii;



const ll mod = 1e9+7;

const int MAXN = 1e4+5;

const int MAXK = 1e2+5;

const db eps = 1e-13;



int memo[MAXN][MAXK], n , k;

string num;

int dp( int pos , int sum , int d , bool ok ) {



    if( !ok && (d > (num[pos]-48)) )

        return 0;



    if( pos == (n-1) ) {

        return sum==0;

    }





    ok |= (d < (num[pos]-48));

    int &res = memo[pos][sum];



    if( ok && res != -1 )

        return res;



    res = 0;



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

        res = ( res + dp( pos+1, (sum + dig)%k , dig , ok ) ) % mod;

    }



    return res;

}





int main()

{

	ios_base::sync_with_stdio(0);

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

    cout<<setprecision(11)<<fixed;

    memset( memo , -1 , sizeof memo );

    cin>>num;

    n = sz(num);

    cin>>k;



    int ans = 0;

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

        ans = ( ans + dp( 0 , dig%k , dig , false ) )%mod;

    cout<<( ans - 1 + mod ) % mod<<"\n";

}

/*

10

8 5

10 8

6 5

1 5

4 8

2 10

3 6

9 2

1 7

*/

// Faster C++ solution for the same problem (measured speedup: 4.983000889568501x):
//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;

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



using namespace std;



using ll = long long;



constexpr int MAX_LEN = 10010, MAX_D = 100;

constexpr int MOD = 1e9 + 7;

int dp[MAX_LEN][2][10][MAX_D];



int main() {

    cin.tie(0); ios::sync_with_stdio(false);



    string K;

    int D;



    cin >> K >> D;



    const int len = K.size();

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

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

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

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

                for (int l = 0; l < D; ++l) {

                    if (dp[i][j][k][l] == 0) continue;



                    if (j == 0) { //制限なし

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

                            (dp[i + 1][0][m][(l + m) % D] += dp[i][j][k][l]) %= MOD;

                    }

                    else { // 制限あり

                        const int ub = (int)(K[i] - '0');

                        for (int m = 0; m < ub; ++m)

                            (dp[i + 1][0][m][(l + m) % D] += dp[i][j][k][l]) %= MOD;

                        (dp[i + 1][1][ub][(l + ub) % D] += dp[i][j][k][l]) %= MOD;

                    }

                }

            }

        }

    }



    ll res = 0;

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

        (res += dp[len][0][i][0]) %= MOD;

        (res += dp[len][1][i][0]) %= MOD;

    }

    cout << (res - 1 + MOD) % MOD << endl;



    return 0;

}

 

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



using namespace std;



using ll = long long;



constexpr int MAX_LEN = 10010, MAX_D = 100;

constexpr int MOD = 1e9 + 7;

int dp[MAX_LEN][2][MAX_D];



int main() {

    cin.tie(0); ios::sync_with_stdio(false);



    string K;

    int D;



    cin >> K >> D;



    const int len = K.size();

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

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

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

            for (int l = 0; l < D; ++l) {

                if (dp[i][j][l] == 0) continue;



                if (j == 0) { //制限なし

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

                        (dp[i + 1][0][(l + m) % D] += dp[i][j][l]) %= MOD;

                }

                else { // 制限あり

                    const int ub = (int)(K[i] - '0');

                    for (int m = 0; m < ub; ++m)

                        (dp[i + 1][0][(l + m) % D] += dp[i][j][l]) %= MOD;

                    (dp[i + 1][1][(l + ub) % D] += dp[i][j][l]) %= MOD;

                }

            }

        }

    }



    ll res = (dp[len][0][0] + dp[len][1][0]) % MOD;

    cout << (res - 1 + MOD) % MOD << endl;



    return 0;

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

#define mn(a, b) (a < b ? a : b)

#define mx(a, b) (a > b ? a : b)

#define f first

#define s second

#define all(v) (v).begin(), (v).end()

#define base 331



using namespace std;



typedef long long ll;

typedef unsigned long long ull;



int const MAXn = 1e4 + 2, MOD = 1e9 + 7;



ll dp[MAXn][102][11];



int main(){



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

    ios_base::sync_with_stdio(0);

    cin.tie(0);

    cout.tie(0);

    string k;

    int d;

    cin>>k>>d;

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

    reverse(all(k));

    int ts = k.size();

    k = "0" + k;

    for(int i = 1; i <= ts; i++){

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

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

                for(int o = 0; o <= 9; o++)

                    dp[i][(m + l) % d][l] = (dp[i][(m + l) % d][l] + dp[i - 1][m][o]) % MOD;

            }

        }

    }

    ll sol = 0;

    int sum = 0;

    for(int i = ts; i >= 1; i--){

        for(int y = 0; y < k[i] - '0'; y++){

            sol = (sol + dp[i][(d - sum) % d][y]) % MOD;

        }

        sum = (sum + k[i] - '0') % d;

    }

    if(sum){

        sol = (sol - 1 + MOD) % MOD;

    }

    cout<<sol;

    return 0;

}


// Faster C++ solution for the same problem (measured speedup: 1.2188853513282256x):
#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 cnt_digits(int x) {

    vector<int> dp2[2];

    dp2[0] = vector<int> (102);

    dp2[1] = vector<int> (102);

    dp2[0][0] = 1;

    int fr=0, cur=1;



    REP(i,0,x-1) {

        fill(dp2[cur].begin(), dp2[cur].end(), 0);



        REP(j,0,d-1) REP(k,0,9) {

            dp2[cur][(j+k)%d] += dp2[fr][j];

            dp2[cur][(j+k)%d] %= MOD;

        }

        swap(cur, fr);

    }

    return (dp2[fr][0] + MOD - 1) % MOD;

}

int main()

{

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

    n = strlen(in+1);



    REP(i,1,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 = cnt_digits(n-1);

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

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

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

    return 0;

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

using namespace std;

string arr;

int d;

int mod=1e9+7;

long long getsum(int ind,int sum,int flag,vector<vector<vector<long long> > >&dp){

	if(ind==arr.size()) {

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

		return 0;

	}

	if(dp[ind][sum][flag]!=-1) return dp[ind][sum][flag];

	int limit=9;

	if(!flag) limit=arr[ind]-'0';

	long long res=0;

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

		if(flag||i<limit){

			res+=getsum(ind+1,(sum+i)%d,1,dp);

		}

		else res+=getsum(ind+1,(sum+i)%d,0,dp);

	}

	dp[ind][sum][flag]=res%mod;

	return res%mod;

	

	

}

int main() {

	

		

		cin>>arr;

	    cin>>d;

	

		

		

		

			vector<vector<vector<long long> > >dp(arr.size()+1,vector<vector<long long> >(200,vector<long long>(2,-1)));

		long long u=getsum(0,0,0,dp);

		

		

		cout<<(u-1+mod)%mod<<endl;

		

		

	

	

	return 0;

}

//hari

// Faster C++ solution for the same problem (measured speedup: 1.2835280135626177x):
#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 cnt_digits(int x) {

    vector<int> dp2[2];

    dp2[0] = vector<int> (102);

    dp2[1] = vector<int> (102);

    dp2[0][0] = 1;

    int fr=0, cur=1;



    REP(i,0,x-1) {

        fill(dp2[cur].begin(), dp2[cur].end(), 0);



        REP(j,0,d-1) REP(k,0,9) {

            dp2[cur][(j+k)%d] += dp2[fr][j];

            dp2[cur][(j+k)%d] %= MOD;

        }

        swap(cur, fr);

    }

    return (dp2[fr][0] + MOD - 1) % MOD;

}

int main()

{

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

    n = strlen(in+1);



    REP(i,1,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 = cnt_digits(n-1);

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

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

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

    return 0;

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

#include <cstdio>

#include <cstring>

#include <string>

using namespace std;



typedef long long llt;



const int MaxN = 10000 + 5, MaxD = 100 + 5;

const llt Mod = 1e9 + 7;



string K;

int N, D;

int A[MaxN];

llt dp[MaxN][MaxD][2];

bool vis[MaxN][MaxD][2];



void init() {

  cin >> K >> D;

  N = K.length();

  for (int i = 1; i <= N; ++i) A[i] = K[i - 1] - '0';

}



// 到了第 x 高位，数字和在模 D 意义下和为 d，是否有上限

llt dfs(int x, int d, int lim) {

  if (x > N) {

    if (d == 0) return 1;

    else return 0;

  }

  if (vis[x][d][lim] == true) return dp[x][d][lim];

  vis[x][d][lim] = true;



  if (lim == 0) {

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

      int s = (d + i) % D;

      dp[x][d][lim] = (dp[x][d][lim] + dfs(x + 1, s, 0)) % Mod;

    }

  } else {

    for (int i = 0; i < A[x]; ++i) {

      int s = (d + i) % D;

      dp[x][d][lim] = (dp[x][d][lim] + dfs(x + 1, s, 0)) % Mod;

    }

    int s = (d + A[x]) % D;

    dp[x][d][lim] = (dp[x][d][lim] + dfs(x + 1, s, 1)) % Mod;

  }

  return dp[x][d][lim];

}



void solve() {

  llt ans = dfs(1, 0, 1);



  ans = ((ans - 1) % Mod + Mod) % Mod;

  cout << ans << endl;

}



int main() {

  init();

  solve();

  return 0;

}

// Faster C++ solution for the same problem (measured speedup: 4.389292066592246x):
#include <cstdio>

#include <cstring>



const int MaxN = 10000 + 5;

const int MaxD = 100 + 5;

const int Mod = 1000000007;



int N, D;

char K[MaxN];

int Dp[MaxN][MaxD][2];

bool Vis[MaxN][MaxD][2];



inline int add(int x, int y) { return (x += y) >= Mod ? x - Mod : x; }

inline int sub(int x, int y) { return (x -= y) < 0 ? x + Mod : x; }

inline void inc(int &x, int y = 1) { x = add(x, y); }



void init() {

  scanf("%s", K + 1);

  N = strlen(K + 1);

  scanf("%d", &D);

}



int dfs(int x, int s, bool limit) {

  if (x > N) return s == 0;

  if (Vis[x][s][limit] == true) return Dp[x][s][limit];

  Vis[x][s][limit] = true;

  int mx = 9;

  if (limit == true) mx = K[x] - '0';

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

    bool new_lim = limit && (d == mx);

    int new_s = (s + d) % D;

    inc(Dp[x][s][limit], dfs(x + 1, new_s, new_lim));

  }

  return Dp[x][s][limit];

}



void solve() {

  printf("%d\n", sub(dfs(1, 0, 1), 1));

}



int main() {

  init();

  solve();

  return 0;

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

using namespace std;

using ll=long long;

const int MAX_N=11000;

const int MOD=1e9+7;

string S;

int D;



ll dp[MAX_N][111];



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

{

	if(pos==(int)S.length()) return m==0;

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

	ll res = 0;

	int ub = limit ? S[pos]-'0' : 9;

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

		res = (res + dfs(pos+1, (m+i)%D, (limit && i==ub)))%MOD;

	}

	res %= MOD;

	if(!limit) dp[pos][m]=res;

	return res;

}



void solve()

{

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

	int ans = dfs(0, 0, true) % MOD;

	cout << (ans-1+MOD)%MOD << endl;

}



int main()

{

	cin >> S >> D;

	solve();

	return 0;

}

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

using namespace std;

using ll = long long;



const int MOD = 1e9+7;

const int MAX_N = 10006;

string K;

int N, D;

ll dp[MAX_N][102];



ll dfs(int at, int rem, bool zero, bool less)

{

	if(at == N){

		if(!rem) return 1;

		else return 0;

	}

	if(!zero && less){

		ll res = dp[at][rem];

		if(res != -1) return res;

	}

	ll res = 0;

	for(int i=0;i<=(less?9:K[at]-'0');++i){

		(res += dfs(at+1, (rem+i)%D, (zero&&!i), (less||(i<(K[at]-'0')))))%=MOD;

	}

	if(!zero && less) dp[at][rem]=res%MOD;

	return res;

}



void solve()

{

	N = K.length();

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

	int ans = dfs(0,0,true,false);

	cout << (ans-1+MOD)%MOD << '\n';

}



int main()

{

	cin >> K >> D;

	solve();

	return 0;

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

using namespace std;

using ll=long long;

const int MAX_N=11000;

const int MOD=1e9+7;

string S;

int D;



ll dp[MAX_N][111];



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

{

	if(pos==(int)S.length()) return m==0;

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

	ll res = 0;

	int ub = limit ? S[pos]-'0' : 9;

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

		res = (res + dfs(pos+1, (m+i)%D, (limit && i==ub)))%MOD;

	}

	res %= MOD;

	if(!limit) dp[pos][m]=res;

	return res;

}



void solve()

{

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

	int ans = dfs(0, 0, true) % MOD;

	cout << (ans-1+MOD)%MOD << endl;

}



int main()

{

	cin >> S >> D;

	solve();

	return 0;

}

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

using namespace std;

using ll = long long;



const int MOD = 1e9+7;

const int MAX_N = 10006;

string K;

int N, D;

ll dp[MAX_N][102];



ll dfs(int at, int rem, bool zero, bool less)

{

	if(at == N){

		if(!rem && !zero) return 1;

		else return 0;

	}

	if(!zero && less){

		ll res = dp[at][rem];

		if(res != -1) return res;

	}

	ll res = 0;

	for(int i=0;i<=(less?9:K[at]-'0');++i){

		(res += dfs(at+1, (rem+i)%D, (zero&&!i), (less||(i<(K[at]-'0')))))%=MOD;

	}

	if(!zero && less) dp[at][rem]=res%MOD;

	return res;

}



void solve()

{

	N = K.length();

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

	int ans = dfs(0,0,true,false);

	cout << ans << '\n';

}



int main()

{

	cin >> K >> D;

	solve();

	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.14491802444323x):
#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;

}