#include <cstdio>

int a, b, c;

int dinamic[10][10];
int pow10[10];

int calcDinamic(int k, int x) {
	if (x < 0) return 0;
	if (x < 10) return 1;
	
	int log = 0;
	for (; pow10[log] < x; ++log);
	--log;
	 
	int cif = x / log;
	x %= log;

	int val;
	if (cif == c) {
		val = calcDinamic(k - 1, x);
	} else {
		val = calcDinamic(k, x);
	}
	val += dinamic[k][log] * cif;
	if (c && cif > c) {
		val += dinamic[k-1][log] - dinamic[k][log];
	}

}

int main(){
	int k;
	FILE * fin = fopen("cifre.in", "r");
	FILE * fout = fopen("cifre.out", "w");

	for (int i = 1; i < 10; ++i) {
		pow10[i] = pow10[i-1] * 10;
	}
	fscanf(fin, "%d%d%d%d", &a, &b,&c, &k);

	dinamic[0][0] = 1;
	if (c) {
		for (int i = 1; i < 10; ++i) {
			dinamic[0][i] = dinamic[0][i-1] * 9;
			for (int j = 1; j < i; ++j) {
				dinamic[j][i] = dinamic[j][i-1] * 9 + dinamic[j-1][i-1];
			}
		}
	} else {
		return -1;
	}

	fprintf(fout, "%d\n", calcDinamic(k, b) - calcDinamic(k, a-1));

	fclose(fin);
	fclose(fout);
}