#include <bits/stdc++.h>
using namespace std;
const short mod = 10000;
string A, B;
short M;
short dp[501][2][500][3][10];
short solve(const string& s, short idx, short lt, short m, short zg,
            short prev) {
  if (idx == s.size()) return m == 0;
  short& ret = dp[idx][lt][m][zg][prev];
  if (~ret) return ret;
  ret = 0;
  short lim = lt ? 9 : s[idx] - '0';
  for (short d = 0; d < (short)(lim + 1); d++) {
    short zgzg = 0;
    if (zg == 0) {
      if (d == prev) {
        if (d != 0)
          continue;
        else
          zgzg = 0;
      } else if (d < prev)
        zgzg = 1;
      else if (d > prev)
        zgzg = 2;
    } else if (zg == 1) {
      if (d <= prev)
        continue;
      else
        zgzg = 2;
    } else if (zg == 2) {
      if (d >= prev)
        continue;
      else
        zgzg = 1;
    }
    (ret += solve(s, idx + 1, lt || d < lim, (m * 10 + d) % M, zgzg, d)) %= mod;
  }
  return ret % mod;
}
signed main() {
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);
  cin >> A >> B >> M;
  for (short i = (short)A.size() - 1; i >= 0; i--) {
    if (A[i] == '0') {
      A[i] = '9';
    } else {
      A[i]--;
      break;
    }
  }
  memset(dp, -1, sizeof(dp));
  short a = solve(A, 0, 0, 0, 0, 0);
  memset(dp, -1, sizeof(dp));
  short b = solve(B, 0, 0, 0, 0, 0);
  cout << (b - a + mod) % mod << endl;
  return 0;
}
