#include <bits/stdc++.h>
using namespace std;
int dy[] = {0, 0, 1, -1, 1, 1, -1, -1};
int dx[] = {1, -1, 0, 0, 1, -1, -1, 1};
string A, B;
long long M;
long long dp[1000][2][4][10][1000];
long long mod = 10000;
int main() {
  cin >> A >> B;
  cin >> M;
  long long n = B.length();
  dp[0][0][0][0][0] = 1;
  for (int i = 0; i < (n); i++) {
    for (int j = 0; j < (2); j++) {
      for (int k = 0; k < (4); k++) {
        for (int l = 0; l < (10); l++) {
          for (int m = 0; m < (M); m++) {
            long long lim = (j ? 9 : B[i] - '0');
            for (int d = 0; d < (lim + 1); d++) {
              if (k == 0) {
                if (d == 0) {
                  (dp[i + 1][j || d < lim][0][d][(m * 10 + d) % M] +=
                   dp[i][j][k][l][m]) %= mod;
                  continue;
                }
                (dp[i + 1][j || d < lim][1][d][(m * 10 + d) % M] +=
                 dp[i][j][k][l][m]) %= mod;
              } else if (k == 1) {
                if (d == l) {
                  continue;
                }
                long long e = 2 + (d > l);
                (dp[i + 1][j || d < lim][e][d][(m * 10 + d) % M] +=
                 dp[i][j][k][l][m]) %= mod;
              } else if (k == 2) {
                if (d <= l) {
                  continue;
                }
                (dp[i + 1][j || d < lim][3][d][(m * 10 + d) % M] +=
                 dp[i][j][k][l][m]) %= mod;
              } else if (k == 3) {
                if (d >= l) {
                  continue;
                }
                (dp[i + 1][j || d < lim][2][d][(m * 10 + d) % M] +=
                 dp[i][j][k][l][m]) %= mod;
              }
            }
          }
        }
      }
    }
  }
  long long ans = 0;
  for (int j = 0; j < (2); j++) {
    for (int k = 0; k < (4); k++) {
      for (int l = 0; l < (10); l++) {
        (ans += dp[n][j][k][l][0]) %= mod;
      }
    }
  }
  n = A.length();
  for (int i = 0; i < (n + 1); i++) {
    for (int j = 0; j < (2); j++) {
      for (int k = 0; k < (4); k++) {
        for (int l = 0; l < (10); l++) {
          for (int m = 0; m < (M); m++) {
            dp[i][j][k][l][m] = 0;
          }
        }
      }
    }
  }
  dp[0][0][0][0][0] = 1;
  for (int i = 0; i < (n); i++) {
    for (int j = 0; j < (2); j++) {
      for (int k = 0; k < (4); k++) {
        for (int l = 0; l < (10); l++) {
          for (int m = 0; m < (M); m++) {
            long long lim = (j ? 9 : A[i] - '0');
            for (int d = 0; d < (lim + 1); d++) {
              if (k == 0) {
                if (d == 0) {
                  (dp[i + 1][j || d < lim][0][d][(m * 10 + d) % M] +=
                   dp[i][j][k][l][m]) %= mod;
                  continue;
                }
                (dp[i + 1][j || d < lim][1][d][(m * 10 + d) % M] +=
                 dp[i][j][k][l][m]) %= mod;
              } else if (k == 1) {
                if (d == l) {
                  continue;
                }
                long long e = 2 + (d > l);
                (dp[i + 1][j || d < lim][e][d][(m * 10 + d) % M] +=
                 dp[i][j][k][l][m]) %= mod;
              } else if (k == 2) {
                if (d <= l) {
                  continue;
                }
                (dp[i + 1][j || d < lim][3][d][(m * 10 + d) % M] +=
                 dp[i][j][k][l][m]) %= mod;
              } else if (k == 3) {
                if (d >= l) {
                  continue;
                }
                (dp[i + 1][j || d < lim][2][d][(m * 10 + d) % M] +=
                 dp[i][j][k][l][m]) %= mod;
              }
            }
          }
        }
      }
    }
  }
  for (int k = 0; k < (4); k++) {
    for (int l = 0; l < (10); l++) {
      (ans += mod - dp[n][1][k][l][0]) %= mod;
    }
  }
  cout << ans << endl;
  return 0;
}
