#include <bits/stdc++.h>
using namespace std;
static const long long INF = 1LL << 61LL;
static const int MOD = 10000;
char c[] = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'};
long long vl = 0;
long long vr = 0;
string str1, str2;
int M;
int sum;
string str;
int mem1[501][10][2][501];
int mem2[501][10][2][501][3];
int cal1(int n, int p, int pp, int mod, string s) {
  int res = 0;
  if (n == str.size() - 2) {
    return 0;
  } else if (n == 0) {
    for (int i = 0; i < 10; ++i) {
      int temp = mod * 10;
      temp += i;
      if (i > p || i < p) {
        int a;
        if (i < p)
          a = 1;
        else if (i > p)
          a = 0;
        if (!(temp % M)) {
          sum++;
          res += cal1(n + 1, i, a, 0, s + c[i]) + 1;
        } else
          res += cal1(n + 1, i, a, temp % M, s + c[i]);
      }
    }
  } else {
    for (int i = 0; i < 10; ++i) {
      int temp = mod * 10;
      temp += i;
      if (pp && p < i) {
        if (!(temp % M)) {
          sum++;
          res += cal1(n + 1, i, 0, 0, s + c[i]) + 1;
        } else
          res += cal1(n + 1, i, 0, temp % M, s + c[i]);
      } else if (!(pp) && p > i) {
        if (!(temp % M)) {
          sum++;
          res += cal1(n + 1, i, 1, 0, s + c[i]) + 1;
        } else
          res += cal1(n + 1, i, 1, temp % M, s + c[i]);
      }
    }
  }
  return mem1[n][p][pp][mod] = res % MOD;
}
int cal(int n, int p, int pp, int mod, int f, string s) {
  int res = 0;
  if (mem2[n][p][pp][mod][f] != -1) {
    return mem2[n][p][pp][mod][f];
  }
  if (n == str.size() - 1 && mod == 0) {
    return 1;
  } else if (n == str.size() - 1)
    return 0;
  for (int i = 0; i < 10; ++i) {
    int b = f;
    if (b == 1) {
      if (str[n + 1] - '0' > i) {
        b = 0;
      }
      if (str[n + 1] - '0' == i) {
        b = 1;
      }
      if (str[n + 1] - '0' < i) {
        continue;
      }
    }
    int temp = mod * 10;
    temp += i;
    if (n == 0) {
      if (i > p || i < p) {
        int a = (i < p);
        res += cal(n + 1, i, a, temp % M, b, s + c[i]);
      }
    } else {
      if ((pp && p < i) || (n == 0 && p < i)) {
        res += cal(n + 1, i, 0, temp % M, b, s + c[i]);
      } else if ((!(pp) && p > i) || (n == 0 && p > i)) {
        res += cal(n + 1, i, 1, temp % M, b, s + c[i]);
      }
    }
  }
  return mem2[n][p][pp][mod][f] = res % MOD;
}
int main() {
  long long ans = 0;
  cin >> str1 >> str2;
  cin >> M;
  memset(mem1, -1, sizeof(mem1));
  memset(mem2, -1, sizeof(mem2));
  for (int i = 0; i < 2; ++i) {
    for (int j = 1; j <= 9; ++j) {
      string s;
      if (i == 0) {
        str = str1;
        if (j % M == 0 && str.size() != 1 && str[0] > j) vl++;
        if (str.size() != 1) vl += cal1(0, j, 0, j % M, s + c[j]);
        if (str[0] - '0' > j) vl += cal(0, j, 0, j % M, 0, s + c[j]);
        if (str[0] - '0' == j) vl += cal(0, j, 0, j % M, 1, s + c[j]);
        if (j == str[0] - '0' && str.size() == 1) vl--;
      } else {
        str = str2;
        if (j % M == 0 && (str.size() > 1 || str[0] >= j)) vr++;
        vr += cal1(0, j, 0, j % M, s + c[j]);
        if (str[0] - '0' > j)
          vr += cal(0, j, 0, j % M, 0, s + c[j]);
        else if (str[0] - '0' == j)
          vr += cal(0, j, 0, j % M, 1, s + c[j]);
      }
    }
  }
  cout << (vr - vl) % MOD << endl;
}
