#include <bits/stdc++.h>
using namespace std;
int dp[500][500][10][3][3];
int main() {
  string a;
  string b;
  int m;
  cin >> a >> b >> m;
  vector<char> k(b.begin(), b.end());
  for (int i = 0; i < k.size(); i++) {
    for (int ma = 0; ma < m; ma++) {
      for (int ln = 0; ln < 10; ln++) {
        for (int ud = 0; ud < 3; ud++) {
          for (int ob = 0; ob < 3; ob++) {
            dp[i][ma][ln][ud][ob] = 0;
          }
        }
      }
    }
  }
  for (int i = 1; i < 10; i++) {
    int t = 0;
    if (k[0] - '0' == i) t = 1;
    if (k[0] - '0' < i) t = 2;
    dp[0][i % m][i][1][t] = 1;
  }
  for (int i = 0; i < k.size() - 1; i++) {
    for (int ma = 0; ma < m; ma++) {
      for (int ln = 0; ln < 10; ln++) {
        for (int ud = 0; ud < 3; ud++) {
          for (int ob = 0; ob < 3; ob++) {
            if (dp[i][ma][ln][ud][ob] > 0) {
              if (ud == 0 || ud == 1) {
                for (int nn = 0; nn < ln; nn++) {
                  int stp = ob;
                  if (stp == 1) {
                    if (nn > k[i + 1] - '0') stp = 2;
                    if (nn < k[i + 1] - '0') stp = 0;
                  }
                  dp[i + 1][(ma * 10 + nn) % m][nn][2][stp] +=
                      dp[i][ma][ln][ud][ob];
                  dp[i + 1][(ma * 10 + nn) % m][nn][2][stp] =
                      dp[i + 1][(ma * 10 + nn) % m][nn][2][stp] % 10000;
                }
              }
              if (ud == 2 || ud == 1) {
                for (int nn = 9; nn > ln; nn--) {
                  int stp = ob;
                  if (stp == 1) {
                    if (nn > k[i + 1] - '0') stp = 2;
                    if (nn < k[i + 1] - '0') stp = 0;
                  }
                  dp[i + 1][(ma * 10 + nn) % m][nn][0][stp] +=
                      dp[i][ma][ln][ud][ob];
                  dp[i + 1][(ma * 10 + nn) % m][nn][0][stp] =
                      dp[i + 1][(ma * 10 + nn) % m][nn][0][stp] % 10000;
                }
              }
            }
          }
        }
      }
    }
  }
  int st = 0;
  for (int i = 0; i < k.size(); i++) {
    for (int ln = 0; ln < 10; ln++) {
      for (int ud = 0; ud < 3; ud++) {
        for (int ob = 0; ob < 3; ob++) {
          if (i != k.size() - 1 || ob != 2) {
            st += dp[i][0][ln][ud][ob];
            st = st % 10000;
          }
        }
      }
    }
  }
  k.clear();
  copy(a.begin(), a.end(), back_inserter(k));
  int pr = k.size() - 1;
  while (pr >= 0) {
    if (k[pr] - '0' == 0) {
      k[pr] = '9';
      pr--;
    } else {
      k[pr] = k[pr] - 1;
      pr = -1;
    }
  }
  for (int i = 0; i < k.size(); i++) {
    for (int ma = 0; ma < m; ma++) {
      for (int ln = 0; ln < 10; ln++) {
        for (int ud = 0; ud < 3; ud++) {
          for (int ob = 0; ob < 3; ob++) {
            dp[i][ma][ln][ud][ob] = 0;
          }
        }
      }
    }
  }
  for (int i = 1; i < 10; i++) {
    int t = 0;
    if (k[0] - '0' == i) t = 1;
    if (k[0] - '0' < i) t = 2;
    dp[0][i % m][i][1][t] = 1;
  }
  for (int i = 0; i < k.size() - 1; i++) {
    for (int ma = 0; ma < m; ma++) {
      for (int ln = 0; ln < 10; ln++) {
        for (int ud = 0; ud < 3; ud++) {
          for (int ob = 0; ob < 3; ob++) {
            if (dp[i][ma][ln][ud][ob] > 0) {
              if (ud == 0 || ud == 1) {
                for (int nn = 0; nn < ln; nn++) {
                  int stp = ob;
                  if (stp == 1) {
                    if (nn > k[i + 1] - '0') stp = 2;
                    if (nn < k[i + 1] - '0') stp = 0;
                  }
                  dp[i + 1][(ma * 10 + nn) % m][nn][2][stp] +=
                      dp[i][ma][ln][ud][ob];
                  dp[i + 1][(ma * 10 + nn) % m][nn][2][stp] =
                      dp[i + 1][(ma * 10 + nn) % m][nn][2][stp] % 10000;
                }
              }
              if (ud == 2 || ud == 1) {
                for (int nn = 9; nn > ln; nn--) {
                  int stp = ob;
                  if (stp == 1) {
                    if (nn > k[i + 1] - '0') stp = 2;
                    if (nn < k[i + 1] - '0') stp = 0;
                  }
                  dp[i + 1][(ma * 10 + nn) % m][nn][0][stp] +=
                      dp[i][ma][ln][ud][ob];
                  dp[i + 1][(ma * 10 + nn) % m][nn][0][stp] =
                      dp[i + 1][(ma * 10 + nn) % m][nn][0][stp] % 10000;
                }
              }
            }
          }
        }
      }
    }
  }
  int mt = 0;
  for (int i = 0; i < k.size(); i++) {
    for (int ln = 0; ln < 10; ln++) {
      for (int ud = 0; ud < 3; ud++) {
        for (int ob = 0; ob < 3; ob++) {
          if (i != k.size() - 1 || ob != 2) {
            mt += dp[i][0][ln][ud][ob];
            mt = mt % 10000;
          }
        }
      }
    }
  }
  st = (st + 10000 - mt) % 10000;
  cout << st << endl;
}
