#include <bits/stdc++.h>
using namespace std;
int dp[502][10][500][2][3];
int main() {
  char A[502], B[502];
  int M, lenA, lenB;
  cin >> A >> B >> M;
  lenA = strlen(A);
  lenB = strlen(B);
  for (int i = 0; i < lenB; i++) {
    B[i] -= '0';
    if (lenA - i - 1 < 0)
      A[lenB - i - 1] = 0;
    else
      A[lenB - i - 1] = A[lenA - i - 1] - '0';
  }
  if (A[0] != 0) dp[0][A[0]][A[0] % M][0][0] = dp[0][A[0]][A[0] % M][1][0] = 1;
  dp[0][B[0]][B[0] % M][0][2] = dp[0][B[0]][B[0] % M][1][2] = 1;
  for (int j = A[0] + 1; j < B[0]; j++) {
    dp[0][j][j % M][0][1] = dp[0][j][j % M][1][1] = 1;
  }
  bool flag = false;
  int latte = lenB - lenA;
  for (int i = 0; i < lenB - 1; i++) {
    if (i + 1 < latte) {
      for (int j = 1; j < 10; j++) {
        dp[i + 1][j][j % M][0][1] += 1;
        if (i + 1 != lenB - 1) dp[i + 1][j][j % M][1][1] += 1;
      }
    } else if (i + 1 == latte) {
      dp[i + 1][A[i + 1]][A[i + 1] % M][0][0] += 1;
      if (i + 1 != lenB - 1) dp[i + 1][A[i + 1]][A[i + 1] % M][1][0] += 1;
      for (int j = A[i + 1] + 1; j < 10; j++) {
        dp[i + 1][j][j % M][0][1] += 1;
        if (i + 1 != lenB - 1) dp[i + 1][j][j % M][1][1] += 1;
      }
    }
    for (int j = 0; j < 10; j++) {
      for (int k = 0; k < M; k++) {
        for (int l = j + 1; l < 10; l++) {
          dp[i + 1][l][(k * 10 + l) % M][1][1] += dp[i][j][k][0][1] % 10000;
          if (A[i + 1] < l)
            dp[i + 1][l][(k * 10 + l) % M][1][1] += dp[i][j][k][0][0] % 10000;
          else if (A[i + 1] == l)
            dp[i + 1][l][(k * 10 + l) % M][1][0] += dp[i][j][k][0][0] % 10000;
          if (B[i + 1] > l)
            dp[i + 1][l][(k * 10 + l) % M][1][1] += dp[i][j][k][0][2] % 10000;
          else if (B[i + 1] == l)
            dp[i + 1][l][(k * 10 + l) % M][1][2] += dp[i][j][k][0][2] % 10000;
        }
        for (int l = j - 1; l >= 0; l--) {
          dp[i + 1][l][(k * 10 + l) % M][0][1] += dp[i][j][k][1][1] % 10000;
          if (A[i + 1] < l)
            dp[i + 1][l][(k * 10 + l) % M][0][1] += dp[i][j][k][1][0] % 10000;
          else if (A[i + 1] == l)
            dp[i + 1][l][(k * 10 + l) % M][0][0] += dp[i][j][k][1][0] % 10000;
          if (B[i + 1] > l)
            dp[i + 1][l][(k * 10 + l) % M][0][1] += dp[i][j][k][1][2] % 10000;
          else if (B[i + 1] == l)
            dp[i + 1][l][(k * 10 + l) % M][0][2] += dp[i][j][k][1][2] % 10000;
        }
      }
    }
  }
  int ans = 0;
  for (int i = 0; i < 10; i++) {
    for (int j = 0; j < 3; j++) {
      ans += (dp[lenB - 1][i][0][0][j] + dp[lenB - 1][i][0][1][j]) % 10000;
    }
  }
  printf("%d\n", ans % 10000);
  return 0;
}
