#include <bits/stdc++.h>
using namespace std;
static const long long INF = 1LL << 61LL;
static const int MOD = 10000;
string str1, str2;
int M;
int mem1[501][10][10][501];
int mem2[501][10][10][501][2];
int cal1(int n, int p, int pp, int mod) {
  int res = 0;
  if (mem1[n][p][pp][mod] != 0) {
    return mem1[n][p][pp][mod];
  }
  if (n == str2.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) {
        if (!(temp % M) && n + 2 > str1.size()) {
          res += cal1(n + 1, i, p, 0) + 1;
        } else
          res += cal1(n + 1, i, p, temp % M);
      }
    }
  } else {
    for (int i = 0; i < 10; ++i) {
      int temp = mod * 10;
      temp += i;
      if (p < pp && p < i) {
        if (!(temp % M) && n + 1 > str1.size() - 1) {
          res += cal1(n + 1, i, p, 0) + 1;
        } else
          res += cal1(n + 1, i, p, temp % M);
      } else if (p > pp && p > i) {
        if (!(temp % M) && n + 1 > str1.size() - 1) {
          res += cal1(n + 1, i, p, 0) + 1;
        } else
          res += cal1(n + 1, i, p, temp % M);
      }
    }
  }
  return mem1[n][p][pp][mod] = res % MOD;
}
int cal2(int n, int p, int pp, int mod, int f) {
  int res = 0;
  if (mem2[n][p][pp][mod][f] != 0) return mem2[n][p][pp][mod][f];
  if (n == str1.size() - 1 && mod == 0) {
    return 1;
  } else if (n == str1.size() - 1)
    return 0;
  for (int i = 0; i < 10; ++i) {
    int b = f;
    if (b == 1) {
      if (str1[n + 1] - '0' < i) {
        b = 0;
      } else if (str1[n + 1] - '0' == i) {
        b = 1;
      } else if (str1[n + 1] - '0' > i) {
        continue;
      }
    }
    int temp = mod * 10;
    temp += i;
    if ((p < pp && p < i) || (n == 0 && p < i)) {
      res += cal2(n + 1, i, p, temp % M, b);
    } else if ((p > pp && p > i) || (n == 0 && p > i)) {
      res += cal2(n + 1, i, p, temp % M, b);
    }
  }
  return mem2[n][p][pp][mod][f] = res % MOD;
}
int cal3(int n, int p, int pp, int mod, int f) {
  int res = 0;
  if (mem2[n][p][pp][mod][f] != 0) return mem2[n][p][pp][mod][f];
  if (n == str2.size() - 1 && mod == 0) {
    return 1;
  } else if (n == str2.size() - 1)
    return 0;
  for (int i = 0; i < 10; ++i) {
    int b = f;
    if (b == 1) {
      if (str2[n + 1] - '0' > i) {
        b = 0;
      } else if (str2[n + 1] - '0' == i) {
        b = 1;
      } else if (str2[n + 1] - '0' < i) {
        continue;
      }
    }
    int temp = mod * 10;
    temp += i;
    if ((p < pp && p < i) || (n == 0 && p < i)) {
      res += cal3(n + 1, i, p, temp % M, b);
    } else if ((p > pp && p > i) || (n == 0 && p > i)) {
      res += cal3(n + 1, i, p, temp % M, b);
    }
  }
  return mem2[n][p][pp][mod][f] = res % MOD;
}
int cal4(int n, int p, int pp, int mod, int f) {
  int res = 0;
  if (mem2[n][p][pp][mod][f - 1] != 0) return mem2[n][p][pp][mod][f - 1];
  if (n == str2.size() - 1 && mod == 0) {
    return 1;
  } else if (n == str2.size() - 1)
    return 0;
  for (int i = 0; i < 10; ++i) {
    int b = f;
    if (b == 2) {
      if (str2[n + 1] - '0' > i) {
        b = 0;
      } else if (str2[n + 1] - '0' == i) {
        b = 2;
      } else if (str2[n + 1] - '0' < i || str1[n + 1] - '0' > i) {
        continue;
      }
    } else if (b == 1) {
      if (str1[n + 1] - '0' < i) {
        b = 0;
      } else if (str1[n + 1] - '0' == i) {
        b = 1;
      } else if (str2[n + 1] - '0' < i || str1[n + 1] - '0' > i) {
        continue;
      }
    }
    int temp = mod * 10;
    temp += i;
    if ((p < pp && p < i) || (n == 0 && p < i)) {
      res += cal4(n + 1, i, p, temp % M, b);
    } else if ((p > pp && p > i) || (n == 0 && p > i)) {
      res += cal4(n + 1, i, p, temp % M, b);
    }
  }
  return mem2[n][p][pp][mod][f] = res % MOD;
}
int main() {
  long long ans = 0;
  cin >> str1 >> str2;
  cin >> M;
  for (int i = 1; i <= 9; ++i) {
    if (str1.size() == str2.size()) {
      if (str1[0] - '0' < i && str2[0] - '0' > i)
        ans += cal4(0, i, 0, i % M, 0);
      else if (str1[0] - '0' == i)
        ans += cal4(0, i, 0, i % M, 1);
      else if (str2[0] - '0' == i)
        ans += cal4(0, i, 0, i % M, 2);
      continue;
    }
    ans += cal1(0, i, 0, i % M);
    if (str2[0] - '0' >= i && i != 0) {
      if (str2[0] - '0' > i)
        ans += cal3(0, i, 0, i % M, 0);
      else
        ans += cal3(0, i, 0, i % M, 1);
    }
    if (str1[0] - '0' <= i && i != 0) {
      if (str1[0] - '0' < i)
        ans += cal2(0, i, 0, i % M, 0);
      else
        ans += cal2(0, i, 0, i % M, 1);
    }
  }
  cout << ans % MOD << endl;
}
