#include <bits/stdc++.h>
using namespace std;
long long m;
long long dp[501][500][10][4][2] = {};
long long calc(string s) {
  for (long long i = 0; i <= s.length(); i++) {
    for (long long j = 0; j < m; j++) {
      for (long long k = 0; k < 10; k++) {
        for (long long l = 0; l < 4; l++) {
          for (long long o = 0; o < 2; o++) dp[i][j][k][l][o] = 0;
        }
      }
    }
  }
  dp[0][0][0][3][1] = 1;
  for (long long i = 0; i < s.length(); i++) {
    for (long long j = 0; j < m; j++) {
      for (long long k = 0; k < 10; k++) {
        for (long long l = 0; l < 10; l++) {
          if (k < l) {
            (dp[i + 1][(j * 10 + l) % m][l][0][0] +=
             dp[i][j][k][1][0] + dp[i][j][k][2][0]) %= 10000;
            if (l < s[i] - '0')
              (dp[i + 1][(j * 10 + l) % m][l][0][0] +=
               dp[i][j][k][1][1] + dp[i][j][k][2][1]) %= 10000;
            else if (l == s[i] - '0')
              (dp[i + 1][(j * 10 + l) % m][l][0][1] +=
               dp[i][j][k][1][1] + dp[i][j][k][2][1]) %= 10000;
          } else if (k > l) {
            (dp[i + 1][(j * 10 + l) % m][l][1][0] +=
             dp[i][j][k][0][0] + dp[i][j][k][2][0]) %= 10000;
            if (l < s[i] - '0')
              (dp[i + 1][(j * 10 + l) % m][l][1][0] +=
               dp[i][j][k][0][1] + dp[i][j][k][2][1]) %= 10000;
            else if (l == s[i] - '0')
              (dp[i + 1][(j * 10 + l) % m][l][1][1] +=
               dp[i][j][k][0][1] + dp[i][j][k][2][1]) %= 10000;
          }
          if (!k) {
            if (!l)
              (dp[i + 1][j][0][3][0] +=
               dp[i][j][k][3][0] + dp[i][j][k][3][1]) %= 10000;
            else {
              (dp[i + 1][(j * 10 + l) % m][l][2][0] += dp[i][j][k][3][0]) %=
                  10000;
              if (l < s[i] - '0')
                (dp[i + 1][(j * 10 + l) % m][l][2][0] += dp[i][j][k][3][1]) %=
                    10000;
              else if (l == s[i] - '0')
                (dp[i + 1][(j * 10 + l) % m][l][2][1] += dp[i][j][k][3][1]) %=
                    10000;
            }
          }
        }
      }
    }
  }
  long long ans = 0;
  for (long long i = 0; i < 10; i++) {
    for (long long j = 0; j < 3; j++) {
      for (long long k = 0; k < 2; k++) {
        ans = (ans + dp[s.length()][0][i][j][k]) % 10000;
      }
    }
  }
  return ans;
}
signed main() {
  string a, b;
  cin >> a >> b >> m;
  for (long long i = a.length() - 1; i >= 0; i--) {
    if (a[i] != '0') {
      a[i]--;
      if (!i && a[i] == '0') a = a.substr(1, a.length() - 1);
      break;
    }
    a[i] = '9';
  }
  cout << (calc(b) - calc(a) + 10000) % 10000 << endl;
  return 0;
}
