#include <bits/stdc++.h>
char a[503], b[503];
int la, lb;
int m;
int dp[2][2][2][10][502];
int zigzag(char *c, int len) {
  int i, j, k, s, t, x, k1, k2;
  memset(dp, 0, sizeof(dp));
  if (*c == '0') c++, len--;
  k = *c - '0';
  if (len == 1)
    for (i = 1; i <= k; i++) dp[0][0][0][i][i % m] = 1;
  else {
    for (i = 1; i < k; i++) dp[0][0][0][i][i % m] = dp[0][0][1][i][i % m] = 1;
    dp[0][1][0][k][k % m] = dp[0][1][1][k][k % m] = 1;
  }
  for (k1 = 0, k2 = 1, i = 1; i < len; i++, k1 = k2, k2 = !k2) {
    for (s = 0; s < 2; s++)
      for (t = 0; t < 2; t++)
        for (j = 0; j < 10; j++)
          for (k = 0; k < m; k++) dp[k2][s][t][j][k] = 0;
    for (k = 0; k < m; k++)
      for (j = 0; j < 10; j++) {
        for (s = j + 1; s < 10; s++) {
          x = (10 * k + s) % m;
          dp[k2][0][0][s][x] += dp[k1][0][1][j][k];
          if (s < c[i] - '0')
            dp[k2][0][0][s][x] += dp[k1][1][1][j][k];
          else if (s == c[i] - '0')
            dp[k2][1][0][s][x] += dp[k1][1][1][j][k];
        }
        for (s = j - 1; s >= 0; s--) {
          x = (10 * k + s) % m;
          dp[k2][0][1][s][x] += dp[k1][0][0][j][k];
          if (s < c[i] - '0')
            dp[k2][0][1][s][x] += dp[k1][1][0][j][k];
          else if (s == c[i] - '0')
            dp[k2][1][1][s][x] += dp[k1][1][0][j][k];
        }
      }
    for (s = 1; s < 10; s++) {
      dp[k2][0][0][s][s % m]++;
      if (i < len - 1) dp[k2][0][1][s][s % m]++;
    }
    for (s = 0; s < 2; s++)
      for (t = 0; t < 2; t++)
        for (j = 0; j < 10; j++)
          for (k = 0; k < m; k++) dp[k2][s][t][j][k] %= 10000;
  }
  for (s = 0, j = 0; j < 10; j++) {
    s += dp[k1][0][0][j][0] + dp[k1][1][0][j][0] + dp[k1][0][1][j][0] +
         dp[k1][1][1][j][0];
  }
  return s % 10000;
}
int main() {
  int i;
  scanf("%s%s%d", a, b, &m);
  la = strlen(a), lb = strlen(b);
  for (i = la - 1;; i--) {
    if (a[i] > '0') {
      a[i]--;
      break;
    }
    a[i] = '9';
  }
  printf("%d\n", zigzag(b, lb) - ((la == 1 && *a == '0') ? 0 : zigzag(a, la)));
  return 0;
}
