#include <bits/stdc++.h>

#define rep(i, n) for(int i = 0; i < n; i++)
using namespace std;

typedef long long ll;

const int INF = 1 << 30;
const ll LLINF = 1LL << 62;

int mod = 1000000007;

ll dp1[505][3][2][10][500]; //B以下でジグザグかつMの倍数
ll dp2[505][3][2][10][500]; //A-1以下でジグザグかつMの倍数

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    rep(i, 500) rep(j, 3) rep(k, 2) rep(l, 10) rep(m, 500) {dp1[i][j][k][l][m] = 0; dp2[i][j][k][l][m] = 0;}
    dp1[0][0][0][0][0] = 1;
    dp2[0][0][0][0][0] = 1;
    string A, B; cin >> A >> B;
    int M; cin >> M;
    
    for(int i = 0; i < B.length(); i++){
        for(int j = 0; j < 3; j++){
            for(int smaller = 0; smaller < 2; smaller++){
                for(int l = 0; l <= 9; l++){
                    for(int m = 0; m < M; m++){
                        for(int lprime = 0; lprime <= (smaller ? 9 : B[i]-'0'); lprime++){
                            if(j == 1 && lprime <= l) continue;
                            if(j == 2 && lprime >= l) continue;
                            if(j == 0){
                                if(l == 0){
                                    dp1[i+1][0][smaller | lprime < B[i]-'0'][lprime][(m*10 + lprime) % M]
                                        = (dp1[i+1][0][smaller | lprime < B[i]-'0'][lprime][(m*10 + lprime) % M] + dp1[i][j][smaller][l][m]) % 10000;
                                }
                                else{
                                    if(lprime < l){
                                        dp1[i+1][1][smaller | lprime < B[i]-'0'][lprime][(m*10 + lprime) % M]
                                            = (dp1[i+1][1][smaller | lprime < B[i]-'0'][lprime][(m*10 + lprime) % M] + dp1[i][j][smaller][l][m]) % 10000;
                                    }
                                    else if(lprime > l){
                                        dp1[i+1][2][smaller | lprime < B[i]-'0'][lprime][(m*10 + lprime) % M]
                                            = (dp1[i+1][2][smaller | lprime < B[i]-'0'][lprime][(m*10 + lprime) % M] + dp1[i][j][smaller][l][m]) % 10000;
                                    }
                                }
                            }
                            else{
                                dp1[i+1][j^3][smaller | lprime < B[i]-'0'][lprime][(m*10 + lprime) % M]
                                    = (dp1[i+1][j^3][smaller | lprime < B[i]-'0'][lprime][(m*10 + lprime) % M] + dp1[i][j][smaller][l][m]) % 10000;
                            }
                        }
                    }
                }
            }
        }
    }

    for(int i = 0; i < A.length(); i++){
        for(int j = 0; j < 3; j++){
            for(int smaller = 0; smaller < 2; smaller++){
                for(int l = 0; l <= 9; l++){
                    for(int m = 0; m < M; m++){
                        for(int lprime = 0; lprime <= (smaller ? 9 : A[i]-'0'); lprime++){
                            if(j == 1 && lprime <= l) continue;
                            if(j == 2 && lprime >= l) continue;
                            if(j == 0){
                                if(l == 0){
                                    dp2[i+1][0][smaller | lprime < A[i]-'0'][lprime][(m*10 + lprime) % M]
                                        = (dp2[i+1][0][smaller | lprime < A[i]-'0'][lprime][(m*10 + lprime) % M] + dp2[i][j][smaller][l][m]) % 10000;
                                }
                                else{
                                    if(lprime < l){
                                        dp2[i+1][1][smaller | lprime < A[i]-'0'][lprime][(m*10 + lprime) % M]
                                            = (dp2[i+1][1][smaller | lprime < A[i]-'0'][lprime][(m*10 + lprime) % M] + dp2[i][j][smaller][l][m]) % 10000;
                                    }
                                    else if(lprime > l){
                                        dp2[i+1][2][smaller | lprime < A[i]-'0'][lprime][(m*10 + lprime) % M]
                                            = (dp2[i+1][2][smaller | lprime < A[i]-'0'][lprime][(m*10 + lprime) % M] + dp2[i][j][smaller][l][m]) % 10000;
                                    }
                                }
                            }
                            else{
                                dp2[i+1][j^3][smaller | lprime < A[i]-'0'][lprime][(m*10 + lprime) % M]
                                    = (dp2[i+1][j^3][smaller | lprime < A[i]-'0'][lprime][(m*10 + lprime) % M] + dp2[i][j][smaller][l][m]) % 10000;
                            }
                        }
                    }
                }
            }
        }
    }

    ll ans = 0;
    rep(j, 3) rep(k, 2) rep(l, 10) ans = (ans + dp1[B.length()][j][k][l][0] - dp2[A.length()][j][k][l][0]) % 10000;
    if(ans < 0) ans += 10000;

    //Aがジグザク数なら1足す
    bool flg = true;
    int md = 0;
    rep(i, A.length()){
        md = ((md*10) + A[i]) % M;
        if(i > 0){
            if(i == 1){
                if(A[i] == A[i-1]) flg = false;
            }
            else{
                if(!( (A[i-2] < A[i-1] && A[i-1] > A[i]) || (A[i-2] > A[i-1] && A[i-1] < A[i]) )) flg = false;
            }
        } 
    }
    if(md != 0) flg = false;
    if(flg) ans++;
    cout << ans << endl;
    return 0;
    
}


Measured memory_bytes: 237812