# include <iostream>
# include <algorithm>
# include <vector>
# include <string>
# include <set>
# include <map>
# include <cmath>
# include <iomanip>
# include <functional>
# include <utility>
# include <stack>
# include <queue>
# include <list>
# include <bitset>
# include <complex>
# include <numeric>
# include <tuple>
using namespace std;
using LL = long long;
using ULL = unsigned long long;
constexpr int INF = 2000000000;
constexpr int HINF = INF / 2;
constexpr double DINF = 100000000000000000.0;
constexpr long long LINF = 9223372036854775807;
constexpr long long HLINF = 4500000000000000000;
const double PI = acos(-1);
int dx[4] = { 0,1,0,-1 }, dy[4] = { 1,0,-1,0 };
#define ALL(x) (x).begin(),(x).end()
#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))
#define mp make_pair
#define eb emplace_back
typedef pair<LL, LL> P;
typedef pair<P, P> PP;
template<typename A, typename B>inline void chmin(A &a, B b) { if (a>b)a = b; }
template<typename A, typename B>inline void chmax(A &a, B b) { if (a<b)a = b; }
const int MOD = 10000;
string s, s1;
int dp[2][3][10][500][501];
int m;
int calc(bool fr, int updw, int pre, int mod, int index) {
if (index == s.size())return !mod;
if (dp[fr][updw][pre][mod][index] != -1)return dp[fr][updw][pre][mod][index];
int ret = 0, end = fr ? 9 : s[index];
for (int i = 0,u; i <= end; i++) {
switch (updw) {
case 0:
if (pre&&pre == i)continue;
else if (pre == 0)u = 0;
else if (pre > i)u = 1;
else u = 2;
break;
case 1:
if (pre >= i)continue;
else u = 2;
break;
case 2:
if (pre <= i)continue;
else u = 1;
break;
}
ret += calc(fr | (i != s[index]), u, i, (mod * 10 + i) % m, index + 1);
}
return dp[fr][updw][pre][mod][index] = ret%MOD;
}
int main() {
cin >> s >> s1 >> m;
for (int i = 0; i < s.size(); i++)s[i] -= '0';
for (int i = s.size() - 1; i >= 0; i--) {
if (s[i] == 0)s[i] = 9;
else {
s[i]--;
break;
}
}
for (int i = 0; i < 2; i++)for (int j = 0; j < 3; j++)for (int k = 0; k < 10; k++)for (int l = 0; l < 500; l++)for (int p = 0; p < 501; p++)dp[i][j][k][l][p] = -1;
int aans = calc(0, 0, 0, 0, 0);
s = s1;
for (int i = 0; i < s.size(); i++)s[i] -= '0';
for (int i = 0; i < 2; i++)for (int j = 0; j < 3; j++)for (int k = 0; k < 10; k++)for (int l = 0; l < 500; l++)for (int p = 0; p < 501; p++)dp[i][j][k][l][p] = -1;
int bans = calc(0, 0, 0, 0, 0);
cout << (bans - aans + MOD) % MOD << endl;
}