#include <bits/stdc++.h>
using namespace std;
const int INF = 1 << 29;
const double PI = acos(-1);
const double EPS = 1e-8;
int dp[2][500][10][2][3];
const int mod = 10000;
inline void add(int &a, int b) { a = (a + b) % mod; }
int solve(const string &s, int m) {
  memset(dp, 0, sizeof(dp));
  for (int i = 0; i < (int)s.size(); ++i) {
    int now = i & 1;
    int nxt = (i + 1) & 1;
    for (int j = 0; j < (int)m; ++j)
      for (int pre = 0; pre < (int)10; ++pre)
        for (int low = 0; low < (int)2; ++low)
          for (int up = 0; up < (int)3; ++up) dp[nxt][j][pre][low][up] = 0;
    for (int j = 0; j < (int)m; ++j) {
      for (int pre = 0; pre < (int)10; ++pre) {
        for (int k = 0; k < (int)10; ++k) {
          if (k > 0 && (i != 0 || k <= s[i] - '0')) {
            bool eqlow = 1;
            if (i == 0 && k == s[i] - '0') eqlow = 0;
            dp[nxt][k % m][k][eqlow][2] = 1;
          }
          if (k < pre) {
            add(dp[nxt][(j * 10 + k) % m][k][1][1], dp[now][j][pre][1][0]);
            add(dp[nxt][(j * 10 + k) % m][k][1][1], dp[now][j][pre][1][2]);
            if (k <= s[i] - '0') {
              add(dp[nxt][(j * 10 + k) % m][k][k != s[i] - '0'][1],
                  dp[now][j][pre][0][0]);
              add(dp[nxt][(j * 10 + k) % m][k][k != s[i] - '0'][1],
                  dp[now][j][pre][0][2]);
            }
          }
          if (k > pre) {
            add(dp[nxt][(j * 10 + k) % m][k][1][0], dp[now][j][pre][1][1]);
            add(dp[nxt][(j * 10 + k) % m][k][1][0], dp[now][j][pre][1][2]);
            if (k <= s[i] - '0') {
              add(dp[nxt][(j * 10 + k) % m][k][k != s[i] - '0'][0],
                  dp[now][j][pre][0][1]);
              add(dp[nxt][(j * 10 + k) % m][k][k != s[i] - '0'][0],
                  dp[now][j][pre][0][2]);
            }
          }
        }
      }
    }
  }
  int ans = 0;
  for (int pre = 0; pre < (int)10; ++pre) {
    for (int low = 0; low < (int)2; ++low) {
      for (int up = 0; up < (int)3; ++up) {
        add(ans, dp[s.size() & 1][0][pre][low][up]);
      }
    }
  }
  return ans;
}
string sub1(string s) {
  for (int i = s.size() - 1; i >= 0; --i) {
    if (s[i] - '0' - 1 < 0) {
      s[i] = '9';
    } else {
      s[i] -= 1;
    }
  }
  return s;
}
int main() {
  string a, b;
  cin >> a >> b;
  int m;
  cin >> m;
  cout << (solve(b, m) - solve(sub1(a), m) + mod) % mod << endl;
}
