#include <bits/stdc++.h>
using namespace std;
signed main() {
  char a[502], b[502];
  int m;
  int ans = 0;
  scanf("%s %s %d", a, b, &m);
  int alen = strlen(a), blen = strlen(b);
  bool mmm = 0;
  for (int i = (0); (alen) > i; i++) {
    a[i] -= '0';
    mmm = (mmm * 10 + a[i]) % m;
  }
  bool zii = 1;
  for (int i = 1; alen > i; i++) {
    if ((i % 2) && a[i] > a[i - 1]) {
      zii = 0;
      break;
    }
    if (!(i % 2) && a[i] < a[i - 1]) {
      zii = 0;
      break;
    }
  }
  if (zii) {
    for (int i = 1; alen > i; i++) {
      if (!(i % 2) && a[i] > a[i - 1]) {
        zii = 0;
        break;
      }
      if ((i % 2) && a[i] < a[i - 1]) {
        zii = 0;
        break;
      }
    }
  }
  if (zii && (!mmm)) ans++;
  for (int i = (0); (blen) > i; i++) b[i] -= '0';
  map<pair<int, int>, int> pnum;
  for (int i = 1; b[0] > i; i++) {
    pnum[{i, i % m}]++;
  }
  pnum[{b[0], -(b[0] % m) - 1}]++;
  for (int i = 1; blen > i; i++) {
    map<pair<int, int>, int> next;
    for (auto cur : pnum) {
      if (cur.first.second < 0) {
        if (i % 2) {
          for (int j = cur.first.first + 1; b[i] > j; j++) {
            next[{j, (-(cur.first.second + 1) * 10 + j) % m}] += cur.second;
            next[{j, (-(cur.first.second + 1) * 10 + j) % m}] %= 10000;
          }
          if (b[i] > cur.first.first) {
            next[{b[i], -(((-(cur.first.second + 1)) * 10 + b[i]) % m) - 1}] +=
                cur.second;
            next[{b[i], -(((-(cur.first.second + 1)) * 10 + b[i]) % m) - 1}] %=
                10000;
          }
        } else {
          for (int j = min(cur.first.first, (int)b[i]) - 1; 0 <= j; j--) {
            next[{j, (-(cur.first.second + 1) * 10 + j) % m}] += cur.second;
            next[{j, (-(cur.first.second + 1) * 10 + j) % m}] %= 10000;
          }
          if (b[i] < cur.first.first) {
            next[{b[i], -(((-(cur.first.second + 1)) * 10 + b[i]) % m) - 1}] +=
                cur.second;
            next[{b[i], -(((-(cur.first.second + 1)) * 10 + b[i]) % m) - 1}] %=
                10000;
          }
        }
      } else {
        if (i % 2) {
          for (int j = cur.first.first + 1; 9 >= j; j++) {
            next[{j, (cur.first.second * 10 + j) % m}] += cur.second;
            next[{j, (cur.first.second * 10 + j) % m}] %= 10000;
          }
        } else {
          for (int j = cur.first.first - 1; 0 <= j; j--) {
            next[{j, (cur.first.second * 10 + j) % m}] += cur.second;
            next[{j, (cur.first.second * 10 + j) % m}] %= 10000;
          }
        }
      }
    }
    for (int i = 1; 9 >= i; i++) {
      next[{i, i % m}]++;
      next[{i, i % m}] %= 10000;
    }
    pnum.swap(next);
  }
  for (auto cur : pnum) {
    if (cur.first.second == 0 || cur.first.second == -1) {
      ans += cur.second;
      ans %= 10000;
    }
  }
  pnum.clear();
  if (blen > 1) {
    for (int i = 1; b[0] > i; i++) {
      pnum[{i, i % m}]++;
    }
    pnum[{b[0], -(b[0] % m) - 1}]++;
    for (int i = 1; blen > i; i++) {
      map<pair<int, int>, int> next;
      for (auto cur : pnum) {
        if (cur.first.second < 0) {
          if (!(i % 2)) {
            for (int j = cur.first.first + 1; b[i] > j; j++) {
              next[{j, (-(cur.first.second + 1) * 10 + j) % m}] += cur.second;
              next[{j, (-(cur.first.second + 1) * 10 + j) % m}] %= 10000;
            }
            if (b[i] > cur.first.first) {
              next[{b[i], -(((-(cur.first.second + 1)) * 10 + b[i]) % m) -
                              1}] += cur.second;
              next[{b[i], -(((-(cur.first.second + 1)) * 10 + b[i]) % m) -
                              1}] %= 10000;
            }
          } else {
            for (int j = min(cur.first.first, (int)b[i]) - 1; 0 <= j; j--) {
              next[{j, (-(cur.first.second + 1) * 10 + j) % m}] += cur.second;
              next[{j, (-(cur.first.second + 1) * 10 + j) % m}] %= 10000;
            }
            if (b[i] < cur.first.first) {
              next[{b[i], -(((-(cur.first.second + 1)) * 10 + b[i]) % m) -
                              1}] += cur.second;
              next[{b[i], -(((-(cur.first.second + 1)) * 10 + b[i]) % m) - 1}] %
                  10000;
            }
          }
        } else {
          if (!(i % 2)) {
            for (int j = cur.first.first + 1; 9 >= j; j++) {
              next[{j, (cur.first.second * 10 + j) % m}] += cur.second;
              next[{j, (cur.first.second * 10 + j) % m}] %= 10000;
            }
          } else {
            for (int j = cur.first.first - 1; 0 <= j; j--) {
              next[{j, (cur.first.second * 10 + j) % m}] += cur.second;
              next[{j, (cur.first.second * 10 + j) % m}] %= 10000;
            }
          }
        }
      }
      if (i < (blen - 1)) {
        for (int i = 1; 9 >= i; i++) {
          next[{i, i % m}]++;
          next[{i, i % m}] %= 10000;
        }
      } else {
        printf("");
      }
      pnum.swap(next);
    }
    for (auto cur : pnum) {
      if (cur.first.second == 0 || cur.first.second == -1) {
        ans += cur.second;
        ans %= 10000;
      }
    }
    pnum.clear();
  }
  for (int i = 1; a[0] > i; i++) {
    pnum[{i, i % m}]++;
  }
  pnum[{a[0], -(a[0] % m) - 1}]++;
  for (int i = 1; alen > i; i++) {
    map<pair<int, int>, int> next;
    for (auto cur : pnum) {
      if (cur.first.second < 0) {
        if (i % 2) {
          for (int j = cur.first.first + 1; a[i] > j; j++) {
            next[{j, (-(cur.first.second + 1) * 10 + j) % m}] += cur.second;
            next[{j, (-(cur.first.second + 1) * 10 + j) % m}] %= 10000;
          }
          if (a[i] > cur.first.first) {
            next[{a[i], -(((-(cur.first.second + 1)) * 10 + b[i]) % m) - 1}] +=
                cur.second;
            next[{a[i], -(((-(cur.first.second + 1)) * 10 + b[i]) % m) - 1}] %=
                10000;
          }
        } else {
          for (int j = min(cur.first.first, (int)a[i]) - 1; 0 <= j; j--) {
            next[{j, (-(cur.first.second + 1) * 10 + j) % m}] += cur.second;
            next[{j, (-(cur.first.second + 1) * 10 + j) % m}] %= 10000;
          }
          if (a[i] < cur.first.first) {
            next[{a[i], -(((-(cur.first.second + 1)) * 10 + b[i]) % m) - 1}] +=
                cur.second;
            next[{a[i], -(((-(cur.first.second + 1)) * 10 + b[i]) % m) - 1}] %=
                10000;
          }
        }
      } else {
        if (i % 2) {
          for (int j = cur.first.first + 1; 9 >= j; j++) {
            next[{j, (cur.first.second * 10 + j) % m}] += cur.second;
            next[{j, (cur.first.second * 10 + j) % m}] %= 10000;
          }
        } else {
          for (int j = cur.first.first - 1; 0 <= j; j--) {
            next[{j, (cur.first.second * 10 + j) % m}] += cur.second;
            next[{j, (cur.first.second * 10 + j) % m}] %= 10000;
          }
        }
      }
    }
    for (int i = 1; 9 >= i; i++) {
      next[{i, i % m}]++;
      next[{i, i % m}] %= 10000;
    }
    pnum.swap(next);
  }
  for (auto cur : pnum) {
    if (cur.first.second == 0 || cur.first.second == -1) {
      ans -= cur.second;
      ans %= 10000;
    }
  }
  pnum.clear();
  if (alen > 1) {
    for (int i = 1; a[0] > i; i++) {
      pnum[{i, i % m}]++;
    }
    pnum[{a[0], -(a[0] % m) - 1}]++;
    for (int i = 1; alen > i; i++) {
      map<pair<int, int>, int> next;
      for (auto cur : pnum) {
        if (cur.first.second < 0) {
          if (!(i % 2)) {
            for (int j = cur.first.first + 1; a[i] > j; j++) {
              next[{j, (-(cur.first.second + 1) * 10 + j) % m}] += cur.second;
              next[{j, (-(cur.first.second + 1) * 10 + j) % m}] %= 10000;
            }
            if (a[i] > cur.first.first) {
              next[{a[i], -(((-(cur.first.second + 1)) * 10 + b[i]) % m) -
                              1}] += cur.second;
              next[{a[i], -(((-(cur.first.second + 1)) * 10 + b[i]) % m) -
                              1}] %= 10000;
            }
          } else {
            for (int j = min(cur.first.first, (int)a[i]) - 1; 0 <= j; j--) {
              next[{j, (-(cur.first.second + 1) * 10 + j) % m}] += cur.second;
              next[{j, (-(cur.first.second + 1) * 10 + j) % m}] %= 10000;
            }
            if (a[i] < cur.first.first) {
              next[{a[i], -(((-(cur.first.second + 1)) * 10 + b[i]) % m) -
                              1}] += cur.second;
              next[{a[i], -(((-(cur.first.second + 1)) * 10 + b[i]) % m) -
                              1}] %= 10000;
            }
          }
        } else {
          if (!(i % 2)) {
            for (int j = cur.first.first + 1; 9 >= j; j++) {
              next[{j, (cur.first.second * 10 + j) % m}] += cur.second;
              next[{j, (cur.first.second * 10 + j) % m}] %= 10000;
            }
          } else {
            for (int j = cur.first.first - 1; 0 <= j; j--) {
              next[{j, (cur.first.second * 10 + j) % m}] += cur.second;
              next[{j, (cur.first.second * 10 + j) % m}] %= 10000;
            }
          }
        }
      }
      if (i < (alen - 1)) {
        for (int i = 1; 9 >= i; i++) {
          next[{i, i % m}]++;
          next[{i, i % m}] %= 10000;
        }
      }
      pnum.swap(next);
    }
    for (auto cur : pnum) {
      if (cur.first.second == 0 || cur.first.second == -1) {
        ans -= cur.second;
        ans %= 10000;
      }
    }
  }
  if (ans < 0) {
    ans += 10000;
  }
  printf("%d\n", ans);
  return 0;
}
