#include <bits/stdc++.h>
using namespace std;
int dp[502][2][10][500][3], m, len[2];
char S[2][550];
int solve(int o) {
  memset(dp, 0, sizeof(dp));
  dp[0][0][0][0][0] = 1;
  for (int i = 0; i < len[o]; 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++) {
            if (dp[i][j][k][l][d] == 0) continue;
            int s, g, p = S[o][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 sum = 0;
  for (int i = 0; i < 2; i++)
    for (int j = 0; j < 10; j++)
      for (int t = 0; t < 3; t++) {
        if (!i && !o) continue;
        (sum += dp[len[o]][1][j][0][t]) %= 10000;
      }
  return sum;
}
int main() {
  scanf("%s%s%d", S[0], S[1], &m);
  for (int i = 0; i < 2; i++) len[i] = strlen(S[i]);
  printf("%d\n", (solve(1) + 10000 - solve(0)) % 10000);
}
