#include<iostream.h>
#include<fstream.h>
long long A,B,C,K,u,g=0;
int x[100];

int nr(int x)
{int k;
	while(x!=0)
{	x=x/10;
k++;}
return k;}
void afis(int k)
{int i,o=0,s=0;
for(i=1;i<=k;i++)
{	if(x[i]==C)
		o++;
	s=s*10+x[i];}
if(o>=K&&s>=A&&s<=B)
g++;}
int valid(int k)
{int i;
	for(i=1;i<k;i++)
	if(x[i]==x[k]&&x[k]!=C)
return 0;
	if(k==1&&x[k]==0)
		return 0;
return 1;}
void back(int k)
{int i;
for(i=0;i<=9;i++)
{	x[k]=i;
if(valid(k)==1)
	if(k==u)
		afis(k);
	else
		{
			back(k+1);}}}
int main()
{long long x,y;
	ifstream f("cifre.in");
	ofstream h("cifre.out");
f>>A>>B>>C>>K;
x=nr(A);
y=nr(B);
u=x;
while(u<y)
{back(1);
u++;}

h<<g/((B-A+1)*1.00);
return 0;}