#include <bits/stdc++.h>
int main() {
  int a, b, m, i, sum = 0;
  scanf("%d%d%d", &a, &b, &m);
  for (i = a; i <= b; i++) {
    int k = i;
    if (i % m == 0) {
      int x[6] = {0, 0, 0, 0, 0, 0};
      int j = 0;
      while (i != 0) {
        x[j] = i % 10;
        i -= x[j];
        i /= 10;
        j++;
      }
      printf("%d%d%d%d%d%d", x[0], x[1], x[2], x[3], x[4], x[5]);
      if (x[0] < x[1] && x[1] > x[2] && x[2] < x[3] && x[3] > x[4] &&
          x[4] < x[5]) {
        sum++;
      }
      if (x[0] > x[1] && x[1] < x[2] && x[2] > x[3] && x[3] < x[4] &&
          x[4] > x[5]) {
        sum++;
      }
    }
    i = k;
  }
  printf("%d\n", sum % 10000);
  return 0;
}
