#include <bits/stdc++.h>
using namespace std;
int dp[550][2][3][10][550];
int zig(string s, int m) {
  int up, mod, ub;
  for (int i = 0; i <= s.size(); i++)
    for (int j = 0; j < 3; j++)
      for (int k = 0; k < 10; k++)
        for (int l = 0; l < m; l++) dp[i][0][j][k][l] = dp[i][1][j][k][l] = 0;
  dp[0][1][1][0][0] = 1;
  for (int i = 0; i < s.size(); i++) {
    for (int j = 0; j < 2; j++) {
      if (j == 1)
        up = s[i] - '0';
      else
        up = 9;
      for (int k = 0; k < 3; k++) {
        for (int l = 0; l < 10; l++) {
          for (int x = 0; x <= up; x++) {
            if (k == 0 && x <= l) continue;
            if (k == 2 && l <= x) continue;
            for (int y = 0; y < m; y++) {
              mod = (y * 10 + x) % m;
              if (j == 1 && x == up)
                ub = 1;
              else
                ub = 0;
              if (k == 1 && l == 0) {
                dp[i + 1][ub][1][x][mod] += dp[i][j][k][l][y];
                dp[i + 1][ub][1][x][mod] %= 10000;
              } else if (x < l) {
                dp[i + 1][ub][0][x][mod] += dp[i][j][k][l][y];
                dp[i + 1][ub][0][x][mod] %= 10000;
              } else if (x > l) {
                dp[i + 1][ub][2][x][mod] += dp[i][j][k][l][y];
                dp[i + 1][ub][2][x][mod] %= 10000;
              }
            }
          }
        }
      }
    }
  }
  int ans = 0;
  for (int i = 0; i < 2; i++)
    for (int j = 0; j < 3; j++)
      for (int k = 0; k < 10; k++) {
        ans += dp[s.size()][i][j][k][0];
        ans %= 10000;
      }
  return ans;
}
string dec(string a) {
  int n = a.size() - 1;
  while (a[n] == '0') {
    a[n--] = '9';
  }
  a[n]--;
  if (a[n] == '0') a = a.substr(1, n - 1);
  return a;
}
int main() {
  string a, b;
  int m;
  cin >> a >> b >> m;
  cout << (zig(b, m) - zig(dec(a), m) + 10000) % 10000 << endl;
}
