#include <bits/stdc++.h>
using namespace std;
int x[501][501][10][2];
int main() {
  string n, m;
  int N[501];
  int M[501];
  int p[10];
  int giri[501][2][3];
  int a = 0, b = 0, c, d, e, sum, sum2;
  memset(giri, 0, sizeof(giri));
  memset(x, 0, sizeof(x));
  char T[10] = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'};
  cin >> n >> m;
  cin >> c;
  for (int i = 1; i <= n.size(); i++) {
    for (int j = 0; j < 10; j++) {
      if (n[i - 1] == T[j]) {
        N[i] = j;
      }
    }
    giri[i][0][0] = (giri[i - 1][0][0] * 10 + N[i]) % c;
    giri[i][0][1] = N[i];
    if (i >= 2) {
      if (N[i] > N[i - 1]) {
        giri[i][0][2] = 1;
      } else if (N[i - 1] > N[i]) {
        giri[i][0][2] = 2;
      } else {
        giri[i][0][2] = 0;
      }
    }
  }
  for (int i = 1; i <= m.size(); i++) {
    for (int j = 0; j < 10; j++) {
      if (m[i - 1] == T[j]) {
        M[i] = j;
      }
    }
    giri[i][1][0] = (giri[i - 1][1][0] * 10 + M[i]) % c;
    giri[i][1][1] = M[i];
    if (i >= 2) {
      if (M[i] > M[i - 1]) {
        giri[i][1][2] = 1;
      } else if (M[i - 1] > M[i]) {
        giri[i][1][2] = 2;
      } else {
        giri[i][1][2] = 0;
      }
    }
  }
  for (int i = 1; i < 10; i++) {
    if (giri[1][0][1] >= i || n.size() >= 2) {
      x[1][i % c][i][0] += 1;
    }
  }
  for (int i = 1; i < 10; i++) {
    for (int j = 0; j < 10; j++) {
      if (i > j) {
        x[2][(i * 10 + j) % c][j][0] += 1;
      } else if (i < j) {
        x[2][(i * 10 + j) % c][j][1] += 1;
      }
    }
  }
  for (int i = 3; i < n.size(); i++) {
    for (int j = 0; j < c; j++) {
      for (int k = 0; k < 10; k++) {
        if (i % 2 == 0) {
          for (int l = 0; l < k; l++) {
            x[i][(j * 10 + l) % c][l][0] += x[i - 1][j][k][0];
            x[i][(j * 10 + l) % c][l][0] %= 10000;
          }
        } else {
          for (int l = k + 1; l < 10; l++) {
            x[i][(j * 10 + l) % c][l][0] += x[i - 1][j][k][0];
            x[i][(j * 10 + l) % c][l][0] %= 10000;
          }
        }
      }
    }
  }
  for (int i = 3; i < n.size(); i++) {
    for (int j = 0; j < c; j++) {
      for (int k = 0; k < 10; k++) {
        if (i % 2 == 1) {
          for (int l = 0; l < k; l++) {
            x[i][(j * 10 + l) % c][l][1] += x[i - 1][j][k][1];
            x[i][(j * 10 + l) % c][l][1] %= 10000;
          }
        } else {
          for (int l = k + 1; l < 10; l++) {
            x[i][(j * 10 + l) % c][l][1] += x[i - 1][j][k][1];
            x[i][(j * 10 + l) % c][l][1] %= 10000;
          }
        }
      }
    }
  }
  sum = 0;
  if (n.size() >= 3) {
    for (int i = 1; i < n.size(); i++) {
      for (int j = 0; j < 10; j++) {
        sum += x[i][0][j][1];
        sum += x[i][0][j][0];
      }
    }
  } else {
    for (int i = 1; i <= n.size(); i++) {
      for (int j = 0; j < 10; j++) {
        sum += x[i][0][j][1];
        sum += x[i][0][j][0];
      }
    }
  }
  memset(x, 0, sizeof(x));
  for (int i = 1; i < 10; i++) {
    x[1][i % c][i][0] += 1;
  }
  for (int i = 1; i < 10; i++) {
    for (int j = 0; j < 10; j++) {
      if (i > j) {
        x[2][(i * 10 + j) % c][j][0] += 1;
      } else if (i < j) {
        x[2][(i * 10 + j) % c][j][1] += 1;
      }
    }
  }
  for (int i = 3; i < m.size(); i++) {
    for (int j = 0; j < c; j++) {
      for (int k = 0; k < 10; k++) {
        if (i % 2 == 0) {
          for (int l = 0; l < k; l++) {
            x[i][(j * 10 + l) % c][l][0] += x[i - 1][j][k][0];
            x[i][(j * 10 + l) % c][l][0] %= 10000;
          }
        } else {
          for (int l = k + 1; l < 10; l++) {
            x[i][(j * 10 + l) % c][l][0] += x[i - 1][j][k][0];
            x[i][(j * 10 + l) % c][l][0] %= 10000;
          }
        }
      }
    }
  }
  for (int i = 3; i < m.size(); i++) {
    for (int j = 0; j < c; j++) {
      for (int k = 0; k < 10; k++) {
        if (i % 2 == 1) {
          for (int l = 0; l < k; l++) {
            x[i][(j * 10 + l) % c][l][1] += x[i - 1][j][k][1];
            x[i][(j * 10 + l) % c][l][1] %= 10000;
          }
        } else {
          for (int l = k + 1; l < 10; l++) {
            x[i][(j * 10 + l) % c][l][1] += x[i - 1][j][k][1];
            x[i][(j * 10 + l) % c][l][1] %= 10000;
          }
        }
      }
    }
  }
  sum2 = 0;
  if (n.size() >= 3) {
    for (int i = 1; i < m.size(); i++) {
      for (int j = 0; j < 10; j++) {
        sum2 += x[i][0][j][1];
        sum2 += x[i][0][j][0];
      }
    }
  } else {
    for (int i = 1; i <= m.size(); i++) {
      for (int j = 0; j < 10; j++) {
        sum2 += x[i][0][j][1];
        sum2 += x[i][0][j][0];
      }
    }
  }
  memset(x, 0, sizeof(x));
  for (int i = 1; i < 10; i++) {
    if (giri[1][0][1] >= i) {
      x[1][i % c][i][0] += 1;
    }
  }
  for (int i = 1; i < 10; i++) {
    if (giri[1][0][1] >= i) {
      for (int j = 0; j < 10; j++) {
        if (giri[2][0][1] >= j || giri[1][0][1] != i) {
          if (i > j) {
            x[2][(i * 10 + j) % c][j][0] += 1;
          } else if (i < j) {
            x[2][(i * 10 + j) % c][j][1] += 1;
          }
        }
      }
    }
  }
  for (int i = 3; i <= n.size(); i++) {
    for (int j = 0; j < c; j++) {
      for (int k = 0; k < 10; k++) {
        if (i % 2 == 0) {
          for (int l = 0; l < k; l++) {
            x[i][(j * 10 + l) % c][l][0] += x[i - 1][j][k][0];
            if ((j == giri[i][0][0] && giri[i][0][1] < l) &&
                (giri[i - 1][0][1] == k && giri[i][0][2] != 2)) {
              x[i][(giri[i][0][0] * 10 + l) % c][l][0] -=
                  min(1, x[i - 1][j][k][0]);
              b++;
            }
            x[i][(j * 10 + l) % c][l][0] %= 10000;
          }
        } else {
          for (int l = k + 1; l < 10; l++) {
            x[i][(j * 10 + l) % c][l][0] += x[i - 1][j][k][0];
            if ((j == giri[i][0][0] && giri[i][0][1] < l) &&
                (giri[i - 1][0][1] == k && giri[i][0][2] != 1)) {
              x[i][(giri[i][0][0] * 10 + l) % c][l][0] -=
                  min(1, x[i - 1][j][k][0]);
              b++;
            }
            x[i][(j * 10 + l) % c][l][0] %= 10000;
          }
        }
      }
    }
  }
  for (int i = 3; i <= n.size(); i++) {
    for (int j = 0; j < c; j++) {
      for (int k = 0; k < 10; k++) {
        if (i % 2 == 1) {
          for (int l = 0; l < k; l++) {
            x[i][(j * 10 + l) % c][l][1] += x[i - 1][j][k][1];
            if ((j == giri[i][0][0] && giri[i][0][1] < l) &&
                (giri[i - 1][0][1] == k && giri[i][0][2] != 1)) {
              x[i][(giri[i][0][0] * 10 + l) % c][l][1] -=
                  min(1, x[i - 1][j][k][1]);
              b++;
            }
            x[i][(j * 10 + l) % c][l][1] %= 10000;
          }
        } else {
          for (int l = k + 1; l < 10; l++) {
            x[i][(j * 10 + l) % c][l][1] += x[i - 1][j][k][1];
            if ((j == giri[i][0][0] && giri[i][0][1] < l) &&
                (giri[i - 1][0][1] == k && giri[i][0][2] != 2)) {
              x[i][(giri[i][0][0] * 10 + l) % c][l][1] -=
                  min(1, x[i - 1][j][k][1]);
              b++;
            }
            x[i][(j * 10 + l) % c][l][1] %= 10000;
          }
        }
      }
    }
  }
  if (n.size() >= 3) {
    for (int i = n.size(); i <= n.size(); i++) {
      for (int j = 0; j < 10; j++) {
        sum += x[i][0][j][1];
        sum += x[i][0][j][0];
      }
    }
  }
  memset(x, 0, sizeof(x));
  for (int i = 1; i < 10; i++) {
    if (giri[1][0][1] >= i) {
      x[1][i % c][i][0] += 1;
    }
  }
  for (int i = 1; i < 10; i++) {
    if (giri[1][1][1] >= i) {
      for (int j = 0; j < 10; j++) {
        if (giri[2][1][1] >= j || giri[1][1][1] != i) {
          if (i > j) {
            x[2][(i * 10 + j) % c][j][0] += 1;
          } else if (i < j) {
            x[2][(i * 10 + j) % c][j][1] += 1;
          }
        }
      }
    }
  }
  for (int i = 3; i <= m.size(); i++) {
    for (int j = 0; j < c; j++) {
      for (int k = 0; k < 10; k++) {
        if (i % 2 == 0) {
          for (int l = 0; l < k; l++) {
            x[i][(j * 10 + l) % c][l][0] += x[i - 1][j][k][0] % 10000;
            if ((j == giri[i][1][0] && giri[i][1][1] < l) &&
                (giri[i - 1][1][1] == k && giri[i][1][2] != 2)) {
              x[i][(giri[i][1][0] * 10 + l) % c][l][0] -=
                  min(x[i - 1][j][k][0], 1);
              a++;
            }
            x[i][(j * 10 + l) % c][l][0] %= 10000;
          }
        } else {
          for (int l = k + 1; l < 10; l++) {
            x[i][(j * 10 + l) % c][l][0] += x[i - 1][j][k][0] % 10000;
            if ((j == giri[i][1][0] && giri[i][1][1] < l) &&
                (giri[i - 1][1][1] == k && giri[i][1][2] != 1)) {
              x[i][(giri[i][1][0] * 10 + l) % c][l][0] -=
                  min(x[i - 1][j][k][0], 1);
              a++;
            }
            x[i][(j * 10 + l) % c][l][0] %= 10000;
          }
        }
      }
    }
  }
  for (int i = 3; i <= m.size(); i++) {
    for (int j = 0; j < c; j++) {
      for (int k = 0; k < 10; k++) {
        if (i % 2 == 1) {
          for (int l = 0; l < k; l++) {
            x[i][(j * 10 + l) % c][l][1] += x[i - 1][j][k][1] % 10000;
            if ((j == giri[i][1][0] && giri[i][1][1] < l) &&
                (giri[i - 1][1][1] == k && giri[i][1][2] != 1)) {
              x[i][(giri[i][1][0] * 10 + l) % c][l][1] -=
                  min(x[i - 1][j][k][1], 1);
              a++;
            }
            x[i][(j * 10 + l) % c][l][1] %= 10000;
          }
        } else {
          for (int l = k + 1; l < 10; l++) {
            x[i][(j * 10 + l) % c][l][1] += x[i - 1][j][k][1] % 10000;
            if ((j == giri[i][1][0] && giri[i][1][1] < l) &&
                (giri[i - 1][1][1] == k && giri[i][1][2] != 2)) {
              x[i][(giri[i][1][0] * 10 + l) % c][l][1] -=
                  min(x[i - 1][j][k][1], 1);
              a++;
            }
            x[i][(j * 10 + l) % c][l][1] %= 10000;
          }
        }
      }
    }
  }
  if (m.size() >= 3) {
    for (int i = m.size(); i <= m.size(); i++) {
      for (int j = 0; j < 10; j++) {
        sum2 += x[i][0][j][1];
        sum2 += x[i][0][j][0];
        cout << x[i][0][j][0] << ' ' << x[i][0][j][1] << endl;
      }
    }
  }
  if (m.size() == 500) {
    sum2 += 1;
  }
  cout << (sum2 - sum + a - b) % 10000 << endl;
  return 0;
}
