#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#include <gmp.h>

#define BUFFER_SIZE 555

bool isZigzag(mpz_t num) {
  char buffer[BUFFER_SIZE];
  mpz_get_str(buffer, 10, num);

  int len = strlen(buffer);
  if (len <= 1) return true; // one digit number.

  int previous = buffer[0] - '0';
  int current  = buffer[1] - '0';
  if (previous == current) return false; // same digits.
  if (len == 2) return true; // two digit number with different digits.

  bool flag = previous > current ? true : false;
  
  for (int i=2; i < len; i++) {
    previous = current;
    current = buffer[i] - '0';
    if ((flag && previous >= current) || (!flag && previous <= current))
      return false;
    else if (previous > current)
      flag = true;
    else
      flag = false;
  }

  return true;
}

int main() {
  mpz_t lower, upper, count;
  int m;
  char buffer[BUFFER_SIZE];

  // initialize values.
  mpz_init(count);
  
  fgets(buffer, BUFFER_SIZE, stdin);
  mpz_init_set_str(lower, buffer, 10);
  
  fgets(buffer, BUFFER_SIZE, stdin);
  mpz_init_set_str(upper, buffer, 10);
  
  scanf("%d", &m);
  
  // set lower to a multiple of m.
  while (!mpz_divisible_ui_p(lower, m))
    mpz_add_ui(lower, lower, 1);

  // count multiples that are also zig-zag number.
  while (mpz_cmp(lower, upper) <= 0) {
    if (isZigzag(lower)) {
      mpz_add_ui(count, count, 1);
    }
    mpz_add_ui(lower, lower, m);
  }

  // print result
  mpz_mod_ui(count, count, 10000);
  mpz_out_str(stdout, 10, count);
  puts("");
  
  // free used memories.
  mpz_clear(lower);
  mpz_clear(upper);
  mpz_clear(count);
  
  return 0;
}