#include <bits/stdc++.h>
template <typename T>
void fill_all(T& i, const T& v) {
  i = v;
}
template <typename U, typename T, size_t N>
void fill_all(T (&arr)[N], const U& v) {
  for (auto& i : arr) {
    fill_all(i, v);
  }
}
int N = 0;
char TOP[5001];
std::string BTM;
int BACE;
int16_t dp[2][2][2][10][2][500][1000];
int16_t func(bool is_zero, bool is_bef_less, bool is_bef_biger, int8_t bef,
             bool is_upper, int16_t mod, int16_t i);
int16_t func_run(bool is_zero, bool is_bef_less, bool is_bef_biger, int8_t bef,
                 bool is_upper, int16_t mod, int16_t i) {
  auto call = [&](bool l, bool b, int8_t v) {
    return func(is_zero && (v == 0), l, b, v, !is_upper, (mod * 10 + v) % BACE,
                i + 1);
  };
  int res = 0;
  int fend = 9;
  int fbegin = 0;
  if (is_upper) {
    fbegin = bef + 1;
  } else {
    fend = bef - 1;
  }
  if (!is_bef_less) {
    auto top = TOP[i] - '0';
    if (fbegin <= top && top <= fend) {
      res += call(false, is_bef_biger || BTM[i] < TOP[i], top);
    }
    fend = std::min(fend, top - 1);
  }
  if (!is_bef_biger) {
    auto btm = BTM[i] - '0';
    if (fbegin <= btm && btm <= fend) {
      res += call(is_bef_less || BTM[i] < TOP[i], false, btm);
    }
    fbegin = std::max(fbegin, btm + 1);
  }
  for (int i = fbegin; i <= fend; ++i) {
    res += call(true, true, i);
  }
  return (res % 10000);
}
inline int16_t func(bool is_zero, bool is_bef_less, bool is_bef_biger,
                    int8_t bef, bool is_upper, int16_t mod, int16_t i) {
  if (i >= N) {
    return (is_zero || mod % BACE) ? 0 : 1;
  }
  auto& memo = dp[is_zero ? 1 : 0][is_bef_less ? 1 : 0][is_bef_biger ? 1 : 0]
                 [bef][is_upper ? 1 : 0][mod][i];
  if (memo >= 0) {
    return memo;
  }
  return memo = func_run(is_zero, is_bef_less, is_bef_biger, bef, is_upper, mod,
                         i);
}
int main() {
  fill_all<int16_t>(dp, -1);
  std::cin >> BTM >> TOP >> BACE;
  while (TOP[N] != '\0') {
    ++N;
  }
  BTM.insert(BTM.begin(), N - BTM.size(), '0');
  int res = 0;
  res += func_run(true, false, false, -1, true, 0, 0);
  res += func_run(true, false, false, 10, false, 0, 0);
  std::cout << res % 10000 << std::endl;
}
