#include <bits/stdc++.h>
int dp[500][10][3][2];
int dp2[500][10][3][2];
char a[555];
char b[555];
int aw[500];
int bw[500];
int main() {
  int m;
  scanf("%s", a);
  scanf("%s", b);
  scanf("%d", &m);
  int l1 = strlen(a);
  int l2 = strlen(b);
  for (int i = 0; i < l1; i++) {
    aw[i] = a[i] - '0';
  }
  for (int i = 0; i < l2; i++) {
    bw[i] = b[i] - '0';
  }
  for (int i = 0; i < 500; i++) {
    for (int ii = 0; ii < 10; ii++) {
      for (int iii = 0; iii < 3; iii++) {
        dp[i][ii][iii][0] = 0;
        dp[i][ii][iii][1] = 0;
      }
    }
  }
  for (int i = 1; i < 10; i++) {
    if (i < bw[0]) {
      dp[i % m][i][0][0] = 1;
      dp[i % m][i][0][1] = 1;
    } else if (i == bw[0]) {
      dp[i % m][i][1][0] = 1;
      dp[i % m][i][1][1] = 1;
    }
  }
  for (int i = 1; i < l2 - l1 + 1; i++) {
    for (int j = 0; j < 500; j++) {
      for (int jj = 0; jj < 10; jj++) {
        for (int jjj = 0; jjj < 3; jjj++) {
          dp2[j][jj][jjj][0] = 0;
          dp2[j][jj][jjj][1] = 0;
        }
      }
    }
    for (int ii = 0; ii < 10; ii++) {
      for (int j = 0; j < 10; j++) {
        for (int jj = 0; jj < m; jj++) {
          if (ii < j) {
            dp2[(jj * 10 + ii) % m][ii][0][0] += dp[jj][j][0][1];
          } else if (ii > j) {
            dp2[(jj * 10 + ii) % m][ii][0][1] += dp[jj][j][0][0];
          }
          if (ii < bw[i]) {
            if (ii < j) {
              dp2[(jj * 10 + ii) % m][ii][0][0] += dp[jj][j][1][1];
            } else if (ii > j) {
              dp2[(jj * 10 + ii) % m][ii][0][1] += dp[jj][j][1][0];
            }
          }
          if (ii == bw[i]) {
            if (ii < j) {
              dp2[(jj * 10 + ii) % m][ii][1][0] += dp[jj][j][1][1];
            } else if (ii > j) {
              dp2[(jj * 10 + ii) % m][ii][1][1] += dp[jj][j][1][0];
            }
          }
        }
      }
    }
    if (i != l2 - l1) {
      for (int j = 1; j < 10; j++) {
        dp2[j % m][j][0][0] += 1;
        dp2[j % m][j][0][1] += 1;
      }
    } else {
      for (int j = aw[0] + 1; j < 10; j++) {
        dp2[j % m][j][0][0] += 1;
        dp2[j % m][j][0][1] += 1;
      }
      dp2[aw[0] % m][aw[0]][2][0] += 1;
      dp2[aw[0] % m][aw[0]][2][0] += 1;
    }
    for (int j = 0; j < 500; j++) {
      for (int jj = 0; jj < 10; jj++) {
        for (int jjj = 0; jjj < 3; jjj++) {
          dp[j][jj][jjj][0] = dp2[j][jj][jjj][0] % 10000;
          dp[j][jj][jjj][1] = dp2[j][jj][jjj][1] % 10000;
        }
      }
    }
  }
  for (int i = l1 - l2 + 1; i < l2; i++) {
    for (int j = 0; j < 500; j++) {
      for (int jj = 0; jj < 10; jj++) {
        for (int jjj = 0; jjj < 3; jjj++) {
          dp2[j][jj][jjj][0] = 0;
          dp2[j][jj][jjj][1] = 0;
        }
      }
    }
    for (int ii = 0; ii < 10; ii++) {
      for (int j = 0; j < 10; j++) {
        for (int jj = 0; jj < m; jj++) {
          if (ii < j) {
            dp2[(jj * 10 + ii) % m][ii][0][0] += dp[jj][j][0][1];
          } else if (ii > j) {
            dp2[(jj * 10 + ii) % m][ii][0][1] += dp[jj][j][0][0];
          }
          if (ii < bw[i]) {
            if (ii < j) {
              dp2[(jj * 10 + ii) % m][ii][0][0] += dp[jj][j][1][1];
            } else if (ii > j) {
              dp2[(jj * 10 + ii) % m][ii][0][1] += dp[jj][j][1][0];
            }
          }
          if (ii == bw[i]) {
            if (ii < j) {
              dp2[(jj * 10 + ii) % m][ii][1][0] += dp[jj][j][1][1];
            } else if (ii > j) {
              dp2[(jj * 10 + ii) % m][ii][1][1] += dp[jj][j][1][0];
            }
          }
          if (ii > aw[i - l2 + l1]) {
            if (ii < j) {
              dp2[(jj * 10 + ii) % m][ii][0][0] += dp[jj][j][2][1];
            } else if (ii > j) {
              dp2[(jj * 10 + ii) % m][ii][0][1] += dp[jj][j][2][0];
            }
          }
          if (ii == aw[i - l2 + l1]) {
            if (ii < j) {
              dp2[(jj * 10 + ii) % m][ii][2][0] += dp[jj][j][2][1];
            } else if (ii > j) {
              dp2[(jj * 10 + ii) % m][ii][2][1] += dp[jj][j][2][0];
            }
          }
        }
      }
    }
    for (int j = 0; j < 500; j++) {
      for (int jj = 0; jj < 10; jj++) {
        for (int jjj = 0; jjj < 3; jjj++) {
          dp[j][jj][jjj][0] = dp2[j][jj][jjj][0] % 10000;
          dp[j][jj][jjj][1] = dp2[j][jj][jjj][1] % 10000;
        }
      }
    }
  }
  int max = 0;
  for (int i = 0; i < 10; i++) {
    for (int ii = 0; ii < 3; ii++) {
      max += dp[0][i][ii][0];
      max %= 10000;
      max += dp[0][i][ii][1];
      max %= 10000;
    }
  }
  printf("%d\n", max);
  return 0;
}
