#include <bits/stdc++.h>
using namespace std;
int m;
char a[3][512];
int k;
int dp(int p, int q, int r, int s, int t, int u) {
  int ret = 0;
  if (p == 0) {
    if (u == 0) {
      ret = 1;
    } else
      ret = 0;
  } else {
    if (q) {
      for (int i = 0; i < 10; i++) {
        if (i > a[r][k - p]) continue;
        ret += dp(p - 1, i == 0, i < a[r][k - p] ? 2 : r, i, 0, i % m);
      }
    } else {
      if (t == 0) {
        for (int i = 0; i < 10; i++) {
          if (i == s) continue;
          if (i > a[r][k - p]) continue;
          ret += dp(p - 1, q, i < a[r][k - p] ? 2 : r, i, s > i ? 1 : 2,
                    (u * 10 + i) % m);
        }
      } else if (t == 1) {
        for (int i = s + 1; i < 10; i++) {
          if (i > a[r][k - p]) continue;
          ret += dp(p - 1, q, i < a[r][k - p] ? 2 : r, i, 2, (u * 10 + i) % m);
        }
      } else {
        for (int i = 0; i < s; i++) {
          if (i > a[r][k - p]) continue;
          ret += dp(p - 1, q, i < a[r][k - p] ? 2 : r, i, 1, (u * 10 + i) % m);
        }
      }
    }
  }
  ret %= 10000;
  return ret;
}
int main() {
  scanf("%s%s%d", a[0], a[1], &m);
  int x[2];
  for (int i = 0; i < 2; i++) {
    x[i] = strlen(a[i]);
    for (int j = 0; j < x[i]; j++) a[i][j] -= '0';
  }
  for (int i = 0; i < 512; i++) a[2][i] = 9;
  k = x[0];
  int p = dp(k, 1, 0, 0, 0, 0);
  k = x[1];
  int q = dp(k, 1, 1, 0, 0, 0);
  int r = 0;
  for (int j = 0; j < 2; j++) {
    bool ok = true;
    for (int i = 0; i < x[0] - 1; i++) {
      if ((i + j) % 2 == 0 && a[0][i] >= a[0][i + 1]) ok = false;
      if ((i + j) % 2 == 1 && a[0][i] <= a[0][i + 1]) ok = false;
    }
    if (ok) r = 1;
  }
  int buf = 0;
  for (int i = 0; i < x[0]; i++) {
    buf *= 10;
    buf += a[0][i];
    buf %= m;
  }
  if (buf) r = 0;
  int ans = (q - p + r + 10000 * 100) % 10000;
  printf("%d\n", ans);
}
