#include<fstream>
#include<cstring>

using namespace std;
typedef int64_t var;

ifstream fin("cifre.in");
ofstream fout("cifre.out");

char a[12], b[12];
var c, k;
var NR[12][12];

var solve(char *num, var i, var nrc, var k) {
    if(num[i] == 0) return 0;

    if(k == 0) {
        return (num[i]-'0') * NR[nrc-1][k] + solve(num, i+1, nrc-1, k);
    }

    if(c == num[i]-'0') {
        return (num[i]-'0') * NR[nrc-1][k] + solve(num, i+1, nrc-1, k-1);
    }
    if(c > num[i]-'0') {
        return (num[i]-'0') * NR[nrc-1][k] + solve(num, i+1, nrc-1, k);
    }
    return (num[i] -'0'- 1) * NR[nrc-1][k] + NR[nrc-1][k-1] + solve(num, i+1, nrc-1, k);
}


int main() {

    fin>>a>>b>>c>>k;
    var p = 10;
    NR[0][0] = 1;
    for(var i=1; i<=10; i++) {
        NR[i][0] = p;
        p *= 10;
    }
    NR[1][1] = 1;
    for(var i=1; i<=10; i++) {
        for(var j=1; j<=10; j++) {
            NR[i][j] += 10*NR[i-1][j] + NR[i-1][j-1];
        }
    }

    var t=0;
    strrev(a);
    while(a[t] == '0') {
        a[t++] = '9';
    }
    a[t]--;
    if(a[strlen(a) - 1] == '0') a[strlen(a) - 1] = 0;
    strrev(a);

    //fout<<a;

    fout<<solve(b, 0, strlen(b), k) - solve(a, 0, strlen(a), k);
    //fout<<solve(a, 0, strlen(a), k);
    return 0;
}