#include <cstdio>

int p10[] = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000};
int comb[10][10];

int factorial(int n) {
  int r = 1;
  for(int i = 1; i <= n; ++i)
    r = r * i;
  return r;
}

int query(int i, int j, int pref, int comp, int c, int k) {
  int rez, a, b;
  a = pref * p10[comp];
  b = (pref + 1) * p10[comp] - 1;
  if(b < i || j < a)
    return 0;
  else if(i <= a && b <= j) {
    if(k < 0)
      return b - a + 1;
    if(comp < k)
      return 0;
    rez = 0;
    for(; k <= comp; ++k)
      rez = rez + factorial(comp) / factorial(k) / factorial(comp - k) * p10[comp - k];
    return rez;
  } else {
    rez = 0;
    for(int cf = 0; cf < 10; ++cf)
      rez = rez + query(i, j, pref * 10 + cf, comp - 1, c, k - (cf == c));
    return rez;
  }
}

int main() {
  int a, b, c, k;
  FILE *fin = fopen("cifre.in", "r");
  fscanf(fin, "%d%d%d%d", &a, &b, &c, &k);
  fclose(fin);

  FILE *fout = fopen("cifre.out", "w");
  fprintf(fout, "%d", query(a, b, 0, 9, c, k));
  fclose(fout);
  return 0;
}