#include<stdio.h>
#include<math.h>
#include<string.h>

int a,b,cif,cif_val[20],nr_cif,apar;
char viz[20];
int pozitii[20],rez,sol;

int cifre(int val)
{
	int nrc = 0;
	
	if(!val)
		return 1;
	
	while(val)
	{
		val /= 10;
		nrc++;
	}
	
	return nrc;
}

void verificare(int val,int total)
{
	int i;
	
	//printf("////////////////////\n");
	//printf("%d %d\n", val,total);
	
	memset(viz,0,sizeof(viz));

	for(i = 1 ; i <= total ; i++)
		viz[pozitii[i]] = 1;
	
	for(i = nr_cif ; i >= 1 ; i--)
	{
		cif_val[i] = val % 10;
		val /= 10;
	}	
	
/*	for(i=1;i<=nr_cif;i++)
		printf("%d ",viz[i]);
	printf("\n");	
	
	for(i=1;i<=nr_cif;i++)
		printf("%d ",cif_val[i]);
	printf("\n");	*/
	
	int poz_libere = nr_cif - total;
	
	for(i = 1 ; i <= nr_cif ; i++)	
		if(!viz[i])
		{
			poz_libere--;
			
			if(cif_val[i]>cif)
				rez += (cif_val[i] - 1) * pow(9,poz_libere);
			else
				rez += cif_val[i] * pow(9,poz_libere);	
			
		//	printf("Adun %d\n",rez);			
						
			if(cif_val[i] == cif)
				break;
		}	
		else
		{
			if(cif < cif_val[i])
			{
				rez += pow(9,poz_libere);
				//printf("Adun %d\n",rez);
				
				break;
			}	
			else if(cif > cif_val[i])
				break;
		}
	if(i == nr_cif + 1)	
		rez++;
	//printf("////////////////////////////\n");	
}

void back_combinari(int poz,int ramase,int val,int total)
{
	if(poz == nr_cif + 1)
	{	
		if(ramase)
			return ;

		verificare(val,total);	

		return ;		
	}
	
	back_combinari(poz + 1,ramase,val,total);
	
	if(!ramase)
		return ;
	
	pozitii[ramase] = poz;
	back_combinari(poz + 1,ramase - 1,val,total);
	pozitii[ramase] = 0;
}

int below(int val,int nr)
{
	rez=0;

	back_combinari(1,nr,val,nr);
	
	return rez;
}

int number_with_fixed(int nr)
{
	return below(b,nr) - below(a-1,nr);
}

int main ()
{
	freopen("cifre.in","r",stdin);
	freopen("cifre.out","w",stdout);
	
	scanf("%d%d%d%d", &a, &b, &cif, &apar);
		
	nr_cif = cifre(b);

	for(int i = apar ; i <= nr_cif ; i++)
		sol += number_with_fixed(i);
		
	printf("%d\n",sol);	
		
	return 0;	
}