#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using PII = pair<int, int>;
using PLL = pair<ll, ll>;
ll MOD = 1e9 + 7;
int M;
string s, s1;
int dp[505][500][2][3][10];
int dfs(int dig, int md, int tight, int ud, int be) {
  if (dig == s.size()) return md ? 0 : 1;
  if (~dp[dig][md][tight][ud][be]) return dp[dig][md][tight][ud][be];
  ll res = 0;
  int lim = tight ? s[dig] : 9;
  for (int i = 0; i < (lim + 1); i++) {
    int nd = 0;
    if (ud == 0) {
      if (be && be == i) continue;
      if (be == i)
        res += dfs(dig + 1, (md * 10 + i) % M, tight & (i == lim), 0, i);
      else {
        res += dfs(dig + 1, (md * 10 + i) % M, tight & (i == lim), 1, i);
        res += dfs(dig + 1, (md * 10 + i) % M, tight & (i == lim), 2, i);
      }
    } else if (ud == 1) {
      if (be <= i) continue;
      res += dfs(dig + 1, (md * 10 + i) % M, tight & (i == lim), 2, i);
    } else {
      if (be >= i) continue;
      res += dfs(dig + 1, (md * 10 + i) % M, tight & (i == lim), 1, i);
    }
    res %= 10000;
  }
  return dp[dig][md][tight][ud][be] = res;
}
void dec1() {
  int i = s1.size() - 1;
  while (1) {
    if (s1[i] == 0) {
      s1[i] = 9;
    } else {
      s1[i]--;
      break;
    }
    i--;
  }
}
int main(void) {
  cin >> s1 >> s >> M;
  for (int i = 0; i < (s.size()); i++) s[i] -= '0';
  for (int i = 0; i < (s1.size()); i++) s1[i] -= '0';
  memset(dp, -1, sizeof dp);
  ll res1 = dfs(0, 0, 1, 0, 0);
  dec1();
  s = s1;
  memset(dp, -1, sizeof dp);
  ll res2 = dfs(0, 0, 1, 0, 0);
  cout << (res1 - res2 + 10000) % 10000 << endl;
}
