#include <bits/stdc++.h>
using namespace std;
string A, B;
int a[511], b[511];
int M, N;
int dp[501][501][10][3][3];
int lth(int num, int n) { return (num * 10 + n) % M; }
int solve(int no, int m, int zg, int zgf, int fl, bool uz) {
  if (no == N) {
    if (m == 0 && uz)
      return 1;
    else
      return 0;
  }
  if (dp[no][m][zg][zgf][fl] != -1) return dp[no][m][zg][zgf][fl];
  int ret = 0;
  for (int i = 0; i <= 9; i++) {
    if (zgf == 1 && zg < i) continue;
    if (zgf == 2 && zg > i) continue;
    if (zg == i && uz) continue;
    if (i < a[no] && (fl & 1)) continue;
    if (i > b[no] && (fl & 2)) continue;
    int fl2 = fl;
    if (i != a[no]) fl2 = fl2 & ~1;
    if (i != b[no]) fl2 = fl2 & ~2;
    int zgf2;
    if (zg < i)
      zgf2 = 1;
    else
      zgf2 = 2;
    if (!uz) zgf2 = 0;
    ret += solve(no + 1, lth(m, i), i, zgf2, fl2, uz || i != 0);
    ret %= (10000);
  }
  return dp[no][m][zg][zgf][fl] = ret;
}
int solve() {
  int ret = 0;
  for (int i = 0; i <= 9; i++) {
    int fl = 3;
    if (i < a[0]) continue;
    if (i > b[0]) continue;
    if (i != a[0]) fl = fl & ~1;
    if (i != b[0]) fl = fl & ~2;
    ret += solve(1, i % M, i, 0, fl, i != 0);
    ret %= (10000);
  }
  return ret;
}
int main() {
  memset(dp, -1, sizeof(dp));
  cin >> A >> B >> M;
  N = B.size();
  for (int i = 0; i < N; i++) {
    b[i] = B[i] - '0';
    if (N - (int)A.size() <= i) a[i] = A[i - (N - (int)A.size())] - '0';
  }
  cout << solve() << "\n";
}
