#include <bits/stdc++.h>
using namespace std;
int m;
int zzn(string s) {
  if (s.size() == 1) {
    return (s[0] - '0') / m;
  }
  static int dp[500][500][10][2];
  fill(dp[0][0][0], dp[500][0][0], 0);
  for (int i = 0; i < s[0] - '0'; i++) {
    dp[0][i % m][i][0] = dp[0][i % m][i][1] = 1;
  }
  int sr = s[0] - '0';
  bool zz[500][2] = {true, true};
  for (int i = 1; i < s.size(); i++) {
    for (int j = 0; j < m; j++) {
      for (int k = 0; k < 10; k++) {
        for (int l = 0; l < 10; l++) {
          if (k == l) continue;
          int &t = dp[i][(j * 10 + l) % m][l][k < l];
          t = (t + dp[i - 1][j][k][k > l]) % 10000;
        }
      }
    }
    if (zz[i - 1][0]) {
      if (s[i - 1] < s[i]) {
        for (int j = s[i - 1] - '0' + 1; j < s[i] - '0'; j++) {
          dp[i][(sr * 10 + j) % m][j][1]++;
        }
        zz[i][1] = true;
      }
    }
    if (zz[i - 1][1]) {
      if (s[i - 1] > s[i]) {
        for (int j = 0; j < s[i] - '0'; j++) {
          dp[i][(sr * 10 + j) % m][j][0]++;
        }
        zz[i][0] = true;
      }
    }
    sr = (sr * 10 + s[i] - '0') % m;
  }
  return (accumulate(dp[s.size() - 1][0][0], dp[s.size() - 1][1][0], 0) +
          (zz[s.size() - 1][0] | zz[s.size() - 1][1]));
}
int main() {
  string a, b;
  cin >> a >> b >> m;
  cout << zzn(b) << endl;
  cout << (zzn(b) - zzn(a) + 10000) % 10000 << endl;
  return 0;
}
