#include <bits/stdc++.h>
using namespace std;
static const long long INF = 1LL << 61LL;
static const int mod = 10000;
int M;
int mem[550];
long long ans;
string str1, str2;
char s[] = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'};
bool comp(string num1, string num2) {
  int t = num1.size();
  int k = num2.size();
  int i = 0;
  while (k) {
    if (t > num2.size()) return false;
    if (t < num2.size()) return true;
    if (num1[i] > num2[i]) return false;
    if (num1[i] < num2[i]) return true;
    k--;
    i++;
  }
  return true;
}
bool MOD(string num) {
  bool res = false;
  long long k = num.size();
  long long mod;
  int i = -1;
  long long n = 0;
  while (k) {
    n = (n * 10) + num[i + 1] - '0';
    mod = n % M;
    n = mod;
    k--;
    i++;
  }
  if (mod == 0) return true;
  return false;
}
int cal(int n, string str) {
  long long res = 0;
  if (!comp(str, str2)) return 0;
  if (n == 0) {
    for (int i = 0; i < 10; ++i) {
      string temp;
      temp = str;
      temp += s[i];
      if (str[n] < s[i] || str[n] > s[i]) {
        if (MOD(temp) && comp(str1, temp) && comp(temp, str2)) {
          res += cal(n + 1, temp) + 1;
        } else
          res += cal(n + 1, temp);
      }
    }
  } else {
    for (int i = 0; i < 10; ++i) {
      string temp;
      temp = str;
      temp += s[i];
      if (str[n] < str[n - 1] && str[n] - '0' < i) {
        if (MOD(temp) && comp(str1, temp) && comp(temp, str2)) {
          res += cal(n + 1, temp) + 1;
        } else
          res += cal(n + 1, temp);
      } else if (str[n] > str[n - 1] && str[n] - '0' > i) {
        if (MOD(temp) && comp(str1, temp) && comp(temp, str2)) {
          res += cal(n + 1, temp) + 1;
        } else
          res += cal(n + 1, temp);
      }
    }
  }
  return res % mod;
}
int main() {
  cin >> str1 >> str2;
  cin >> M;
  for (int i = 1; i <= 9; ++i) {
    string c;
    c += s[i];
    if (comp(str1, c) && comp(c, str2) && MOD(c)) {
      ans += 1;
    }
    ans += cal(0, c) % mod;
  }
  cout << ans % mod << endl;
  return 0;
}
