#include <bits/stdc++.h>
using namespace std;
const int MOD = 10000;
string a, b;
int m;
int dp[2][5000][2][2][2];
int ans = 0;
string inttostring1(int n) {
  string ret = "";
  stringstream ss;
  ss << n;
  ss >> ret;
  return ret;
}
string inttostring2(int n) {
  string ret = "", s = inttostring1(n);
  stringstream ss;
  if (n < m) {
    string s2 = inttostring1(m);
    for (int i = 0; i < s.size() - s2.size(); i++) ret += '0';
  }
  return ret + s;
}
bool xisbigger1(char x) {
  if (x >= a[a.size() - 1]) return true;
  return false;
}
bool xissmaller1(char x) {
  if (x <= b[b.size() - 1]) return true;
  return false;
}
bool xisbigger2(char x, int keta, bool used) {
  if (x > a[a.size() - 1 - keta]) return true;
  if (x < a[a.size() - 1 - keta]) return false;
  return used;
}
bool xissmaller2(char x, int keta, bool used) {
  if (x < b[b.size() - 1 - keta]) return true;
  if (x > b[b.size() - 1 - keta]) return false;
  return used;
}
bool xisbigger3(string x, int keta) {
  if (x.size() + keta > a.size()) return true;
  if (x.size() + keta < a.size()) return false;
  string s = "";
  for (int i = 0; i < a.size() - keta; i++) s += a[i];
  if (x >= s) return true;
  return false;
}
bool xissmaller3(string x, int keta) {
  if (x.size() + keta < b.size()) return true;
  if (x.size() + keta > b.size()) return false;
  string s = "";
  for (int i = 0; i < b.size() - keta; i++) s += b[i];
  if (x <= s) return true;
  return false;
}
bool xisbigger4(string x, int keta) {
  if (x.size() + keta > a.size()) return true;
  if (x.size() + keta < a.size()) return false;
  string s = "";
  for (int i = 0; i < b.size() - keta; i++) s += b[i];
  if (x > s) return true;
  return false;
}
bool xissmaller4(string x, int keta) {
  if (x.size() + keta < b.size()) return true;
  if (x.size() + keta > b.size()) return false;
  string s = "";
  for (int i = 0; i < b.size() - keta; i++) s += b[i];
  if (x < s) return true;
  return false;
}
bool zigzag_judge1(string s) {
  if (s.size() == 1) return true;
  for (int i = 0; i < s.size() - 1; i++)
    if (s[i] == s[i + 1]) return false;
  bool leftisbigger = s[0] > s[1];
  for (int i = 1; i < s.size() - 1; i++)
    if ((i & 1 ^ leftisbigger) != (s[i] > s[i + 1])) return false;
  return true;
}
bool zigzag_judge2(string s, bool standard) {
  if (s.size() == 1) return true;
  for (int i = 0; i < s.size() - 1; i++)
    if (s[i] == s[i + 1]) return false;
  for (int i = 1; i <= s.size() - 1; i++)
    if ((i & 1 ^ standard) != (s[s.size() - i - 1] > s[s.size() - i]))
      return false;
  return true;
}
int main() {
  cin >> a >> b;
  cin >> m;
  for (int i = 0; i <= 9; i++) {
    int startnum = i * m;
    dp[0][startnum][0][xisbigger1(startnum % 10 + '0')]
      [xissmaller1(startnum % 10 + '0')] = 1;
    dp[0][startnum][1][xisbigger1(startnum % 10 + '0')]
      [xissmaller1(startnum % 10 + '0')] = 1;
    if (zigzag_judge1(inttostring2(startnum)) &&
        xisbigger3(inttostring1(startnum), 0) &&
        xissmaller3(inttostring1(startnum), 0))
      ans++;
  }
  for (int i = 1; i < b.size(); i++) {
    memset(dp[i & 1], 0, sizeof dp[i & 1]);
    for (int j = 0; j < 10 * m; j++) {
      for (int k1 = 0; k1 <= 1; k1++) {
        for (int k2 = 0; k2 <= 1; k2++) {
          for (int k3 = 0; k3 <= 1; k3++) {
            for (int l = 0; l <= 9; l++) {
              int nownum = j + l * m * 10;
              if (nownum % 100 / 10 != nownum % 10 &&
                  k1 != (nownum % 100 / 10 > nownum % 10))
                dp[i & 1][nownum / 10][nownum % 100 / 10 > nownum % 10]
                  [xisbigger2(nownum % 100 / 10 + '0', i, k2)]
                  [xissmaller2(nownum % 100 / 10 + '0', i, k3)] +=
                    dp[!(i & 1)][j][k1][k2][k3];
            }
          }
        }
      }
    }
    for (int j = 0; j < m * 10; j++)
      for (int k1 = 0; k1 <= 1; k1++)
        for (int k2 = 0; k2 <= 1; k2++)
          for (int k3 = 0; k3 <= 1; k3++) dp[i & 1][j][k1][k2][k3] %= MOD;
    for (int j = m; j < 10 * m; j++) {
      for (int k1 = 0; k1 <= 1; k1++) {
        if (zigzag_judge2(inttostring2(j), k1) &&
            xisbigger3(inttostring1(j), i) && xissmaller3(inttostring1(j), i)) {
          ans += dp[i & 1][j][k1][1][1];
          if (xisbigger4(inttostring1(j), i)) ans += dp[i & 1][j][k1][0][1];
          if (xissmaller4(inttostring1(j), i)) ans += dp[i & 1][j][k1][1][0];
          ans %= MOD;
        }
      }
    }
  }
  cout << ans << endl;
  return 0;
}
