DigitDP

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

#define fast ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL)
#define ll long long
#define ld long double
#define pb push_back
#define fe first
#define se second
#define nl "\n"
#define pp pair < ll , ll >
#define sz(x) (ll)x.size()
#define st(x) sort(x.begin(),x.end())
#define rst(x) sort(x.rbegin(), x.rend())
#define all(x) x.begin(),x.end()
long double pi = 3.14159265358979323;

const double EPS = 1e-12;
const int N = 1e6 + 5;
const int mod = 1e9 + 7;

//DigitDp
ll a , b;
ll k,d;
/// How many numbers x are there in the range a to b, where the digit d occurs exactly k times in x?

ll dp[20][20][2];
// DP[p][c][f] = Number of valid numbers <= b from this state
/// p = current position from left side (zero based)
/// c = number of times we have placed the digit d so far
/// f = the number we are building has already become smaller than b? [0 = no, 1 = yes]

vector < int > num;


ll recur(ll pos ,ll cnt,bool f){

            if(cnt > k){
                //cout << pos << " " << cnt << " " << f << "\n";
                return 0;   }
            if(pos == sz(num)){
                if(cnt == k)return 1;
                return 0;    }
            if(dp[pos][cnt][f] != -1)return dp[pos][cnt][f];

            ll lmt = 9;
           // cout << lmt;
            //cout << pos << " ";
            if(f == 0){
                // Digits we placed so far matches with the prefix of b
/// So if we place any digit > num[pos] in the current position, then the number will become greater than b
             //  cout << num[pos]  << " ";
                lmt = num[pos];
            }
            //cout << lmt << " ";
            ll res = 0 ;
            for(int i = 0 ; i <= lmt ;i++ ){
                    bool nf = f;
                    ll ncnt = cnt;
                    if(i < lmt)nf = 1;
                    if(i == d)ncnt++;
                    if(cnt <= k)res += recur(pos + 1 , ncnt , nf);
            }
            return dp[pos][cnt][f] = res;
}

ll solve(ll n){
    num.clear();
    while(n){
        num.pb(n%10);
        n /= 10;
    }
    reverse(all(num));
   // cout << num[0];
   // for(auto it : num)cout << it ;
    memset(dp,-1,sizeof(dp));
    return recur(0,0,0);
}
int main()
{
    fast;
    //string a , b;
    cin >> a >> b >> d >> k ;
    //cout << k ;
    //cout << a << " " << b ;
    memset(dp , -1 , sizeof(dp));
   // cout << b <<  " ";
    cout << solve(b)- solve(a-1);
   // cout << solve(0,0,0,b) - solve(0,0,0,a);























    return 0;

}