cntx_fc87

#include<bits/stdc++.h>
#define DEBUG 0
using namespace std;

typedef long long ll;

const int MOD = 2000 + 10;
const int MLEN = 14;

ll mod, X, A, C;

ll dp[MLEN][MOD], num[MLEN][MOD];
// dp and num as describe in solution
ll special[MLEN][MOD];
// special to deal with case X = 0
ll p10[MLEN];
// p10[i] = 10 ^ i

void init()
{
    // calculate p10
    p10[0] = 1, p10[1] = 10;
    for (int i = 2; i < MLEN; i++)
        p10[i] = p10[i - 1] * p10[1];

    // base case
    num[0][0] = 1;
    for (int c = 0; c < 10; c++)
        num[1][c % mod]++;
    dp[1][X % mod]++;

    // calculate bottom up
    for (int len = 1; len + 1 < MLEN; len++)
        for (int pmod = 0; pmod < MOD; pmod++)
        {
            // special have to take from its child
            special[len][pmod] += special[len - 1][pmod];
            for (int c = 0; c < 10; c++)
            {
                ll newMod = (pmod + c * p10[len] ) % mod;
                num[len + 1][newMod] += num[len][pmod];
                dp[len + 1][newMod] += dp[len][pmod];
                if (c) special[len + 1][newMod] += dp[len][pmod];
                if (c == X) dp[len + 1][newMod] += num[len][pmod];
            }
        }
}

ll F(ll lim)
{
    if (lim < 0) return 0;
    // indigit is lim in string
    vector<int > indigit;
    ll cloneLim = lim;
    while (cloneLim)
        indigit.push_back(cloneLim % 10),
        cloneLim /= 10;

    ll result = 0;
    // accumulate = number of X from indigit.size() - 1 to cid + 1
    // currentNum = actual number from indigit.size() - 1 to cid + 1
    // to understand better, read the code below
    int accumulate = 0; ll currentNum = 0;

    for (int cid = indigit.size() - 1; cid >= 0; cid--)
    {
        // current digit
        int digit = indigit[cid];
        int start = 0;
        if (!X && cid == indigit.size() - 1) start = 1;

        for (int foo = start; foo < digit; foo++)
        {
            int remLen = cid;
            // calculate remainMod
            ll currentMod = ( currentNum * p10[remLen + 1] + foo * p10[remLen] ) % mod;
            ll remainMod  = A % mod - currentMod;
            if (remainMod < 0) remainMod += mod;

            result += dp[remLen][remainMod];
            result += (accumulate + (foo == X)) * num[remLen][remainMod];
        }
        accumulate += (digit == X);
        currentNum = currentNum * 10 + digit;
    }
    // special case when X == 0
    if (!X) result += special[indigit.size() - 1][A % mod];
    return result;
}

main()
{
    if (fopen("main.in", "r"))
        freopen("main.in", "r", stdin);
    cin >> A >> mod >> C >> X;

    init();

    ll L = A, R = A + mod * C;
    cout << F(R + 1) - F(L) << '\n';
}