#include<fstream>

using namespace std;

const char iname[]="cifre.in";
const char oname[]="cifre.out";
const int maxn=15;

ifstream f(iname);
ofstream g(oname);

int a,b,c,k,i,j,cnt[10][10],cnt0[10][10],p,pows[10],rez;

void precalc()
{
    cnt[1][1]=1;
    cnt[1][0]=9;
    for(i=2;i<10;++i)
        for(j=0;j<=i;++j)
            cnt[i][j]=cnt[i-1][j]*9+(j>0?cnt[i-1][j-1]:0);
    cnt0[1][1]=1;
    cnt0[1][0]=9;
    for(i=2;i<10;++i)
        for(j=0;j<=i;++j)
            if(c==0)
                cnt0[i][j]=9*cnt[i-1][j]+(j>0?cnt0[i-1][j]:0);
            else
                cnt0[i][j]=8*cnt[i-1][j]+(j>0?cnt[i-1][j-1]:0)+cnt0[i-1][j];
    pows[0]=1;
    for(p=1,i=0;b/p>=10;p*=10,++i,pows[i]=p);
}

int comp(int x,int type,int pow,int many)
{
    if(pow==0)
        if(x>=c)
            if(many==1)
                return 1;
            else
                return x;
        else
            return 0;
    if(type==0)
        if(c==0)
            if(x<pows[pow])
                return comp(x,type,pow-1,many);
            else
                return (x/pows[pow]-1>=0?x/pows[pow]-1:0)*cnt[pow-1][many]+cnt0[pow][many]+comp(x%pows[pow],1,pow-1,many);
        else
        {
            int y=(x/pows[pow]-1);
            if(y<0)
                return comp(x,type,pow-1,many);
            if(y>=c)
                return (y-1)*cnt[pow-1][many]+cnt[pow-1][many-1]+cnt0[pow][many]+comp(x%pows[pow],1,pow-1,many);
            if(y+1==c)
                return y*cnt[pow-1][many]+cnt0[pow][many]+comp(x%pows[pow],1,pow-1,many-1);
            return y*cnt[pow-1][many]+cnt0[pow][many]+comp(x%pows[pow],1,pow-1,many);
        }
    int y=x/pows[pow];
    if(y>=c)
        if(y==0)
            return comp(x,type,pow-1,many-1);
        else
            return (y-1)*cnt[pow-1][many]+comp(x%pows[pow],1,pow-1,many-1);
    return y*cnt[pow-1][many]+comp(x%pows[pow],1,pow-1,many);
}



int main()
{
    f>>a>>b>>c>>k;
    precalc();
    for(j=k;j<=i;++j)
    {
        rez+=comp(b,0,i,j);
        rez-=comp(a-1,0,i,j);
    }
    g<<rez<<"\n";

    f.close();
    g.close();

    return 0;
}