#include <bits/stdc++.h>
constexpr int MOD = 10000;
constexpr int MAX_N = 501, MAX_M = 500;
std::string a, b;
std::vector<int> A, B;
int n, m;
int memo[MAX_N][MAX_M][10][2][2][2];
int solve(int pos, int mod, int num, int updown, int onA, int onB) {
  if (memo[pos][mod][num][updown][onA][onB] >= 0)
    return memo[pos][mod][num][updown][onA][onB];
  if (pos == n - 1) {
    if (mod == 0)
      return 1;
    else
      return 0;
  }
  int res = 0;
  for (int i = (updown ? 0 : num + 1); i < (updown ? num : 10); ++i) {
    if (!onA && A[pos + 1] > i || !onB && B[pos + 1] < i) continue;
    res += solve(pos + 1, (mod * 10 + i) % m, i, !updown,
                 (onA                ? 1
                  : (A[pos + 1] < i) ? 1
                                     : 0),
                 (onB                ? 1
                  : (B[pos + 1] > i) ? 1
                                     : 0));
    res %= MOD;
  }
  return memo[pos][mod][num][updown][onA][onB] = res;
}
int main() {
  std::cin.tie(0);
  std::ios::sync_with_stdio(false);
  std::cin >> a >> b >> m;
  char ch;
  n = b.size();
  a = std::string(n - a.size(), '0') + a;
  for (int i = 0; i < a.size(); ++i) {
    ch = a[i];
    A.emplace_back(atoi(&ch));
  }
  for (int i = 0; i < b.size(); ++i) {
    ch = b[i];
    B.emplace_back(atoi(&ch));
  }
  std::memset(memo, -1, sizeof(memo));
  int ans = 0;
  for (int i = 0; i < 10; ++i) {
    for (int j = 0; j < 2; ++j) {
      if (A[0] > i || B[0] < i) continue;
      ans += solve(0, i % m, i, j, ((A[0] < i) ? 1 : 0), ((B[0] > i) ? 1 : 0));
      ans %= MOD;
    }
  }
  if (n == 1) ans /= 2;
  std::cout << ans << std::endl;
  return 0;
}
