#include <bits/stdc++.h>
using namespace std;
int dp1[501][2][10][500][3], dp2[501][2][10][500][3], m;
void solve(int dp[][2][10][500][3], string& a) {
  dp[0][0][0][0][0] = 1;
  for (int i = 0; i < a.size(); i++)
    for (int j = 0; j < 2; j++)
      for (int k = 0; k < 10; k++)
        for (int l = 0; l < m; l++)
          for (int d = 0; d < 3; d++) {
            int s, g, p = a[i] - '0';
            if (d == 1) {
              s = k + 1;
              g = (j ? 9 : p);
            } else if (d == 2) {
              s = 0;
              g = (j ? k - 1 : min(k - 1, p));
            } else {
              s = 0;
              g = (j ? 9 : p);
            }
            for (int x = s; x <= g; x++) {
              if (x && k == x) continue;
              int y;
              if (d == 1)
                y = 2;
              else if (d == 2)
                y = 1;
              else {
                if (k == 0)
                  y = 0;
                else if (x < k)
                  y = 1;
                else
                  y = 2;
              }
              (dp[i + 1][j || x < p][x][(l * 10 + x) % m][y] +=
               dp[i][j][k][l][d]) %= 10000;
            }
          }
}
int main() {
  string a, b;
  cin >> a >> b >> m;
  int d = a.size() - 1;
  while (a[d] == '0') {
    a[d] = '9';
    d--;
  }
  a[d]--;
  if (*a.begin() == '0') a = a.substr(1);
  solve(dp1, a);
  solve(dp2, b);
  int sum1 = 0, sum2 = 0;
  for (int i = 0; i < 2; i++)
    for (int j = 0; j < 10; j++)
      for (int t = 0; t < 3; t++) {
        (sum1 += dp1[a.size()][i][j][0][t]) %= 10000;
        (sum2 += dp2[b.size()][i][j][0][t]) %= 10000;
      }
  printf("%d\n", (sum2 + 10000 - sum1) % 10000);
}
