stablegradients/pie-gem5-bysrc huggingface dataset:
// Original C++ solution (slower):
#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;

}

 

// Optimized solution to the same problem (faster):
#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;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#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;

}


// Optimized solution to the same problem (faster):
#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;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#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

// Optimized solution to the same problem (faster):
#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;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#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;

}

// Optimized solution to the same problem (faster):
#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;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#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;

}

// Optimized solution to the same problem (faster):
#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;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#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);

}
















// Optimized solution to the same problem (faster):
#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;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#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;

}


// Optimized solution to the same problem (faster):
#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;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#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;

}


// Optimized solution to the same problem (faster):
#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;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#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;

}

// Optimized solution to the same problem (faster):
#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;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <climits>

#include <iostream>

#include <vector>

#include <string>

#include <sstream>

#include <algorithm>

#include <utility>

#include <set>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <functional>



using namespace std;



#define int long long



#define fst first

#define scd second

#define PB push_back

#define MP make_pair

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

#define rall(a) a.rbegin(),a.rend()

#define omajinai ios::sync_with_stdio(false);cin.tie(0)

#define rep(i,x) for(int i=0;i<(int)(x);++i)

#define rep1(i,x) for(int i=1;i<=(int)(x);++i)



typedef long long ll;

typedef long double ld;

typedef vector<int> vi;

typedef vector<vi> vvi;

typedef pair<int, int> pii;

typedef vector<pii> vpii;



template<typename T>T& max(T&a,T&b){if(a>=b)return a;return b;}

template<typename T>T& min(T&a,T&b){if(a<b)return a;return b;}

template<typename T>bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}

template<typename T>bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}

template<typename T>T get(){T a;cin>>a;return a;}

template<typename T>T rev(T a){reverse(all(a));return a;}

template<typename T>vector<T>&sort(vector<T>&a){sort(all(a));return a;}



const int inf = 3e18;

const ll linf = 3e18;

const double eps = 1e-9;



int N, M, K;

int A[20005];

int memo[20005];



int rec(int now)

{

    if (~memo[now]) return memo[now];



    int res = inf;

    int mi = inf, ma = -inf;

    

    for (int i = 0; i < min(N - now, M); ++i) {

        mi = min(mi, A[now + i]);

        ma = max(ma, A[now + i]);



        res = min(res, K + (ma - mi) * (i + 1) + rec(now + i + 1));

    }



    if (res == inf) res = 0;



    return memo[now] = res;

}



signed main()

{ // #define int long long ?????????????????§scanf???????????¨???????????????????????\?????????????????????

    cin >> N >> M >> K;



    rep(i, N) {

        cin >> A[i];

    }



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



    cout << rec(0) << endl;

}

// Optimized solution to the same problem (faster):
#include <iostream>



using namespace std;



#define int long long



int a[20005];

int dp[20005];



signed main()

{

    int N, M, K; cin >> N >> M >> K;



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

        cin >> a[i];

        dp[i + 1] = 3e18;

    }



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

        int mi = 1e9, ma = -1e9;



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

            if (i + j >= N) continue;



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

            ma = max(ma, a[i + j]);



            dp[i + j + 1] = min(dp[i + j + 1], dp[i] + (j + 1) * (ma - mi) + K);

        }

    }



    cout << dp[N] << endl;

}

// Fastest known solution for this problem: