#include <bits/stdc++.h>
using namespace std;
static const long long INF = 1 << 61;
static const long long MOD = 10000;
char c[] = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'};
string num1, num2;
string s;
long long m;
long long mem[500][500][10][2][3];
long long cal(long long n, long long mod, long long p, long long pp,
              long long f) {
  long long res = 0;
  if (mem[n][mod][p][pp][f] != 0) return mem[n][mod][p][pp][f];
  if (n == s.size()) return 0;
  for (long long i = 0; i <= 9; ++i) {
    long long b = pp;
    long long t = f;
    long long temp = (mod * 10);
    temp += i;
    if (n == 0) {
      if (i == 0) continue;
      if (i > s[n] - '0')
        t = 1;
      else if (i < s[n] - '0')
        t = 2;
      else
        t = 0;
      if (s.size() == 1) {
        if (s[0] - '0' > i && i % m == 0) res += cal(n + 1, i % m, i, b, t) + 1;
      } else {
        if (i % m == 0) {
          res += cal(n + 1, i % m, i, b, t) + 1;
        } else
          res += cal(n + 1, i % m, i, b, t);
      }
    } else if (n == 1) {
      if (t == 0) {
        if (i > s[n] - '0')
          t = 1;
        else if (i < s[n] - '0')
          t = 2;
      }
      if (p == i)
        continue;
      else if (p < i)
        b = 1;
      else if (p > i)
        b = 0;
      if (temp % m == 0) {
        res += cal(n + 1, temp % m, i, b, t) + 1;
      } else
        res += cal(n + 1, temp % m, i, b, t);
    } else if (n == s.size() - 1) {
      if (t == 0) {
        if (i > s[n] - '0')
          t = 1;
        else if (i < s[n] - '0')
          t = 2;
      }
      if (t == 2) {
        if (b == 1) {
          if (p > i) {
            if (temp % m == 0) {
              res += cal(n + 1, temp % m, i, b, t) + 1;
            }
          }
        } else if (b == 0) {
          if (p < i) {
            if (temp % m == 0) {
              res += cal(n + 1, temp % m, i, b, t) + 1;
            }
          }
        }
      }
      if (t == 0) {
        if (b == 1) {
          if (p > i && s[n] - '0' > i) {
            if (temp % m == 0) {
              res += cal(n + 1, temp % m, i, b, t) + 1;
            }
          }
        } else if (b == 0) {
          if (p < i && s[n] - '0' > i) {
            if (temp % m == 0) {
              res += cal(n + 1, temp % m, i, b, t) + 1;
            }
          }
        }
      }
    } else {
      if (t == 0) {
        if (i > s[n] - '0')
          t = 1;
        else if (i < s[n] - '0')
          t = 2;
      }
      if (b == 1) {
        if (p > i) {
          b = 0;
          if (temp % m == 0) {
            res += cal(n + 1, temp % m, i, b, t) + 1;
          } else
            res += cal(n + 1, temp % m, i, b, t);
        }
      } else if (b == 0) {
        if (p < i) {
          b = 1;
          if (temp % m == 0) {
            res += cal(n + 1, temp % m, i, b, t) + 1;
          } else
            res += cal(n + 1, temp % m, i, b, t);
        }
      }
    }
  }
  return mem[n][mod][p][pp][f] = res % MOD;
}
long long vr, vl;
signed main() {
  cin >> num1 >> num2;
  cin >> m;
  s = num1;
  vl = cal(0, 0, 0, 0, 0);
  memset(mem, 0, sizeof(mem));
  s = num2;
  vr = cal(0, 0, 0, 0, 0);
  cout << (vr + MOD - vl) % MOD << endl;
  return 0;
}
