#include <bits/stdc++.h>
using namespace std;
struct data {
  int sum, surp;
};
data dp[500][10][500][2];
const int dir[2] = {1, -1};
int main() {
  int lenA, lenB, M;
  char a[502], b[502], A[502], B[502];
  cin >> A >> B;
  cin >> M;
  lenA = strlen(A);
  lenB = strlen(B);
  for (int i = 0; i < lenA; i++) a[i] = A[lenA - i - 1] - '0';
  for (int i = 0; i < lenB; i++) b[i] = B[lenB - i - 1] - '0';
  for (int i = 0; i < lenA; i++) {
    if (a[i] == 0) {
      a[i] = 9;
      continue;
    }
    a[i] -= 1;
  }
  if (a[lenA - 1] == 0) lenA--;
  int ansA = 0;
  for (int i = 0; i <= a[0]; i++) {
    dp[0][i][i % M][0].sum = dp[0][i][i % M][1].sum = 1;
    if (i != 0) ansA += dp[0][i][0][0].sum;
  }
  for (int i = a[0] + 1; i < 10; i++) {
    dp[0][i][i % M][0].surp = dp[0][i][i % M][1].surp = 1;
  }
  if (lenA == 1) goto NEXT;
  ansA = 0;
  for (int i = 0; i < lenA - 1; i++) {
    for (int j = 1; j < 10; j++) {
      ansA += dp[i][j][0][0].sum + dp[i][j][0][0].surp + dp[i][j][0][1].sum +
              dp[i][j][0][1].surp;
    }
    if (i == 0) ansA /= 2;
    ansA %= 10000;
    for (int j = 0; j < 10; j++) {
      for (int k = 0; k < M; k++) {
        for (int l = 0; l < 2; l++) {
          dp[i][j][k][l].sum %= 10000;
          dp[i][j][k][l].surp %= 10000;
          for (int m = j + dir[l]; 0 <= m && m < 10; m += dir[l]) {
            data &dpp = dp[i][j][k][l],
                 &_dpp = dp[i + 1][m][(m * 10 + k) % M][(l + 1) & 1];
            if (m < a[i + 1])
              _dpp.sum += dpp.sum + dpp.surp;
            else if (m == a[i + 1])
              _dpp.sum += dpp.sum, _dpp.surp += dpp.surp;
            else
              _dpp.surp += dpp.sum + dpp.surp;
          }
        }
      }
    }
  }
  for (int i = 1; i <= a[lenA - 1]; i++) {
    ansA += dp[lenA - 1][i][0][0].sum + dp[lenA - 1][i][0][1].sum;
  }
  ansA %= 10000;
NEXT:
  for (int i = 0; i < lenB; i++)
    for (int j = 0; j < 10; j++)
      for (int k = 0; k < M; k++)
        for (int l = 0; l < 2; l++)
          dp[i][j][k][l].sum = dp[i][j][k][l].surp = 0;
  int ansB = 0;
  for (int i = 0; i <= b[0]; i++) {
    dp[0][i][i % M][0].sum = dp[0][i][i % M][1].sum = 1;
    if (i != 0) ansB += dp[0][i][0][0].sum;
  }
  for (int i = b[0] + 1; i < 10; i++) {
    dp[0][i][i % M][0].surp = dp[0][i][i % M][1].surp = 1;
  }
  if (lenB == 1) goto END;
  ansB = 0;
  for (int i = 0; i < lenB - 1; i++) {
    for (int j = 1; j < 10; j++) {
      ansB += dp[i][j][0][0].sum + dp[i][j][0][0].surp + dp[i][j][0][1].sum +
              dp[i][j][0][1].surp;
    }
    if (i == 0) ansB /= 2;
    ansB %= 10000;
    for (int j = 0; j < 10; j++) {
      for (int k = 0; k < M; k++) {
        for (int l = 0; l < 2; l++) {
          dp[i][j][k][l].sum %= 10000;
          dp[i][j][k][l].surp %= 10000;
          for (int m = j + dir[l]; 0 <= m && m < 10; m += dir[l]) {
            data &dpp = dp[i][j][k][l],
                 &_dpp = dp[i + 1][m][(m * 10 + k) % M][(l + 1) & 1];
            if (m < b[i + 1])
              _dpp.sum += dpp.sum + dpp.surp;
            else if (m == b[i + 1])
              _dpp.sum += dpp.sum, _dpp.surp += dpp.surp;
            else
              _dpp.surp += dpp.sum + dpp.surp;
          }
        }
      }
    }
  }
  for (int i = 1; i <= b[lenB - 1]; i++) {
    ansB += dp[lenB - 1][i][0][0].sum + dp[lenB - 1][i][0][1].sum;
  }
  ansB %= 10000;
END:
  printf("%d\n", (ansB + 10000 - ansA) % 10000);
}
