#include <bits/stdc++.h>
using namespace std;
string str[2];
const int mod = 10000;
int dmod;
int dp[501][501][11][3][3];
int dp2[501][501][11][3][3];
void dfs(int a, int div, int c, int d, int e) {}
int main(void) {
  memset(dp, 0, sizeof(dp));
  memset(dp2, 0, sizeof(dp2));
  cin >> str[0];
  cin >> str[1];
  cin >> dmod;
  for (int i = 0; i <= (str[1][0] - '0'); i++) {
    int b = i % dmod;
    if (i == 0)
      continue;
    else if (i != (str[1][0] - '0'))
      dp[0][b][i][2][0] = 1;
    else
      dp[0][b][i][2][1] = 1;
  }
  for (int a = 1; a < str[1].size(); a++) {
    for (int c = 1; c <= 9; c++) {
      dp[a][c % dmod][c][2][0] = 1;
    }
    for (int b = 0; b < dmod; b++) {
      for (int c = 0; c <= 9; c++) {
        for (int pc = 0; pc <= 9; pc++) {
          int div = (b * 10 + c) % dmod;
          if (c > pc) {
            dp[a][div][c][0][0] =
                (dp[a][div][c][0][0] + dp[a - 1][b][pc][1][0] +
                 dp[a - 1][b][pc][2][0]) %
                mod;
            if (pc == 0)
              dp[a][div][c][0][0] =
                  (dp[a][div][c][0][0] + dp[a][b][pc][2][2]) % mod;
            if (c < (str[1][a] - '0')) {
              dp[a][div][c][0][0] =
                  (dp[a][div][c][0][0] + dp[a - 1][b][pc][1][1] +
                   dp[a - 1][b][pc][2][1]) %
                  mod;
            }
            if (c == (str[1][a] - '0')) {
              dp[a][div][c][0][1] =
                  (dp[a][div][c][0][1] + dp[a - 1][b][pc][1][1] +
                   dp[a - 1][b][pc][2][1]) %
                  mod;
            }
          }
          if (c < pc) {
            dp[a][div][c][1][0] =
                (dp[a][div][c][1][0] + dp[a - 1][b][pc][0][0] +
                 dp[a - 1][b][pc][2][0]) %
                mod;
            if (c < (str[1][a] - '0')) {
              dp[a][div][c][1][0] =
                  (dp[a][div][c][1][0] + dp[a - 1][b][pc][0][1] +
                   dp[a - 1][b][pc][2][1]) %
                  mod;
            }
            if (c == (str[1][a] - '0')) {
              dp[a][div][c][1][1] =
                  (dp[a][div][c][1][1] + dp[a - 1][b][pc][0][1] +
                   dp[a - 1][b][pc][2][1]) %
                  mod;
            }
          }
        }
      }
    }
  }
  for (int i = 0; i <= (str[0][0] - '0'); i++) {
    int b = i % dmod;
    if (i == 0)
      continue;
    else if (i != (str[0][0] - '0'))
      dp2[0][b][i][2][0] = 1;
    else
      dp2[0][b][i][2][1] = 1;
  }
  for (int a = 1; a < str[0].size(); a++) {
    for (int c = 1; c <= 9; c++) {
      dp2[a][c % dmod][c][2][0] = 1;
    }
    for (int b = 0; b < dmod; b++) {
      for (int c = 0; c <= 9; c++) {
        for (int pc = 0; pc <= 9; pc++) {
          int div = (b * 10 + c) % dmod;
          if (c > pc) {
            dp2[a][div][c][0][0] =
                (dp2[a][div][c][0][0] + dp2[a - 1][b][pc][1][0] +
                 dp2[a - 1][b][pc][2][0]) %
                mod;
            if (pc == 0)
              dp2[a][div][c][0][0] =
                  (dp2[a][div][c][0][0] + dp2[a][b][pc][2][2]) % mod;
            if (c < (str[0][a] - '0')) {
              dp2[a][div][c][0][0] =
                  (dp2[a][div][c][0][0] + dp2[a - 1][b][pc][1][1] +
                   dp2[a - 1][b][pc][2][1]) %
                  mod;
            }
            if (c == (str[0][a] - '0')) {
              dp2[a][div][c][0][1] =
                  (dp2[a][div][c][0][1] + dp2[a - 1][b][pc][1][1] +
                   dp2[a - 1][b][pc][2][1]) %
                  mod;
            }
          }
          if (c < pc) {
            dp2[a][div][c][1][0] =
                (dp2[a][div][c][1][0] + dp2[a - 1][b][pc][0][0] +
                 dp2[a - 1][b][pc][2][0]) %
                mod;
            if (c < (str[0][a] - '0')) {
              dp2[a][div][c][1][0] =
                  (dp2[a][div][c][1][0] + dp2[a - 1][b][pc][0][1] +
                   dp2[a - 1][b][pc][2][1]) %
                  mod;
            }
            if (c == (str[0][a] - '0')) {
              dp2[a][div][c][1][1] =
                  (dp2[a][div][c][1][1] + dp2[a - 1][b][pc][0][1] +
                   dp2[a - 1][b][pc][2][1]) %
                  mod;
            }
          }
        }
      }
    }
  }
  int ans = 0;
  for (int i = 0; i < 10; i++) {
    ans =
        (ans + dp[str[1].size() - 1][0][i][0][0] +
         dp[str[1].size() - 1][0][i][0][1] + dp[str[1].size() - 1][0][i][1][0] +
         dp[str[1].size() - 1][0][i][1][1] + dp[str[1].size() - 1][0][i][2][0] +
         dp[str[1].size() - 1][0][i][2][1]) %
        mod;
  }
  int ans2 = 0;
  for (int i = 0; i < 10; i++) {
    ans = (ans + mod * 5 - dp2[str[0].size() - 1][0][i][0][0] -
           dp2[str[0].size() - 1][0][i][1][0] -
           dp2[str[0].size() - 1][0][i][2][0]) %
          mod;
  }
  cout << ans << endl;
  return 0;
}
