#include <bits/stdc++.h>
using namespace std;
string A, BS, B;
int M;
int mod = 10000;
int dp1[502][10][502];
int dp2[502][10][502];
int re[502];
int sss = 0;
void init() {
  re[0] = 1;
  for (int i = 1; i < 502; i++) {
    re[i] = re[i - 1] * 10;
    re[i] %= M;
  }
}
int solve(int num, int ke, int K) {
  int res = 0;
  for (int i = 0; i < 502; i++) {
    for (int j = 0; j < 10; j++) {
      for (int k = 0; k < 502; k++) {
        dp1[i][j][k] = 0;
        dp2[i][j][k] = 0;
      }
    }
  }
  for (int i = 1; i < num; i++) {
    dp1[0][i][(i * re[ke - 1]) % M] = 1;
    dp2[0][i][(i * re[ke - 1]) % M] = 1;
  }
  for (int i = 1; i < ke; i++) {
    for (int j = 0; j < 10; j++) {
      for (int k = 0; k < M; k++) {
        for (int l = 0; l < j; l++) {
          dp1[i][j][k] += dp2[i - 1][l][(10 * M + k - j * re[ke - 1 - i]) % M];
        }
        for (int l = j + 1; l < 10; l++) {
          dp2[i][j][k] += dp1[i - 1][l][(10 * M + k - j * re[ke - 1 - i]) % M];
        }
      }
    }
  }
  for (int i = 0; i < 10; i++) {
    res += dp1[ke - 1][i][K];
    res += dp2[ke - 1][i][K];
    res %= mod;
  }
  if (ke == 1) return res / 2;
  return res;
}
int solve1(int start, string S, int ke, int sss1, int K) {
  for (int i = 0; i < (int)S.length() - 1; i++) {
    if (S[i] == S[i + 1]) return 0;
  }
  for (int i = 0; i < (int)S.length() - 2; i++) {
    if (S[i] - '0' <= S[i + 1] - '0' && S[i + 1] - '0' <= S[i + 2] - '0')
      return 0;
    if (S[i] - '0' >= S[i + 1] - '0' && S[i + 1] - '0' >= S[i + 2] - '0')
      return 0;
  }
  int res = 0;
  for (int i = 0; i < 502; i++) {
    for (int j = 0; j < 10; j++) {
      for (int k = 0; k < 502; k++) {
        dp1[i][j][k] = 0;
        dp2[i][j][k] = 0;
      }
    }
  }
  if (S.length() == 1) {
    dp1[start][S[S.length() - 1] - '0'][sss1] = 1;
    dp2[start][S[S.length() - 1] - '0'][sss1] = 1;
  } else if (S[S.length() - 2] - '0' < S[S.length() - 1] - '0')
    dp1[start][S[S.length() - 1] - '0'][sss1] = 1;
  else
    dp2[start][S[S.length() - 1] - '0'][sss1] = 1;
  for (int i = start + 1; i < ke; i++) {
    for (int j = 0; j < 10; j++) {
      for (int k = 0; k < M; k++) {
        for (int l = 0; l < j; l++) {
          dp1[i][j][k] += dp2[i - 1][l][(10 * M + k - j * re[ke - 1 - i]) % M];
        }
        for (int l = j + 1; l < 10; l++) {
          dp2[i][j][k] += dp1[i - 1][l][(10 * M + k - j * re[ke - 1 - i]) % M];
        }
      }
    }
  }
  for (int i = 0; i < 10; i++) {
    res += dp1[ke - 1][i][K];
    res += dp2[ke - 1][i][K];
    res %= mod;
  }
  if (ke == 1) return res / 2;
  return res;
}
bool F(string S) {
  int rem = 0;
  for (int i = 0; i < S.length(); i++) {
    rem += re[S.length() - 1 - i] * (S[i] - '0');
  }
  if (rem % M != 0) return false;
  for (int i = 0; i < S.length() - 2; i++) {
    if (S[i] - '0' <= S[i + 1] - '0' && S[i + 1] - '0' <= S[i + 2] - '0')
      return false;
    if (S[i] - '0' >= S[i + 1] - '0' && S[i + 1] - '0' >= S[i + 2] - '0')
      return false;
  }
  return true;
}
int main() {
  cin >> A >> B;
  scanf("%d", &M);
  int pos = A.length() - 1;
  while (A[pos] == '0') {
    A[pos] = '9';
    pos--;
  }
  A[pos] = ((A[pos] - '0') - 1) + '0';
  if (pos == 0 && A[pos] == '0') A.erase(A.begin());
  init();
  int ans1 = 0;
  int ans2 = 0;
  for (int i = 0; i < A.length(); i++) {
    ans1 += solve(10, i + 1, 0);
    ans1 %= mod;
  }
  string S1 = "";
  for (int i = 0; i < A.length(); i++) {
    for (int j = (A[i] - '0') + 1; j < 10; j++) {
      ans1 += mod;
      int sss1 = sss;
      sss1 += j * re[A.length() - 1 - i];
      sss1 %= M;
      string S2 = S1;
      S2 += j + '0';
      ans1 -= solve1(i, S2, A.length(), sss1, 0);
      ans1 %= mod;
    }
    sss += (A[i] - '0') * re[A.length() - 1 - i];
    sss %= M;
    S1 += A[i];
  }
  for (int i = 0; i < B.length(); i++) {
    ans2 += solve(10, i + 1, 0);
    ans2 %= mod;
  }
  sss = 0;
  S1 = "";
  for (int i = 0; i < B.length(); i++) {
    for (int j = (B[i] - '0') + 1; j < 10; j++) {
      ans2 += mod;
      int sss1 = sss;
      sss1 += j * re[B.length() - 1 - i];
      sss1 %= M;
      string S2 = S1;
      S2 += j + '0';
      ans2 -= solve1(i, S2, B.length(), sss1, 0);
      ans2 %= mod;
    }
    S1 += B[i];
    sss += (B[i] - '0') * re[B.length() - 1 - i];
    sss %= M;
  }
  printf("%d\n", (ans2 - ans1 + mod) % mod);
  return 0;
}
