
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define FOR(i,a,b) for(int i=a;i<=b;++i)
#define LL long long
using namespace std;
static const LL INF = 1LL<<61LL;
static const int MOD = 10000;
char c[]={'0','1','2','3','4','5','6','7','8','9'};
typedef pair<LL,LL> PLL;

string str1,str2;
int M;
int sum;
string str;
int mem1[500][10][2][500];
int mem2[500][10][2][500][3];
int t;


int cal1(int n,int p,int pp,int mod,string s){
    int res=0;
    //cout<<s<<endl;
    if(mem1[n][p][pp][mod]!=0){
        //cout<<"hoge"<<endl;
        return mem1[n][p][pp][mod];
    }
    if(n==str.size()-2){
        return 0;
    }
    else if(n==0){
        rep(i,10){
            int temp=mod*10;
            temp+=i;
            if(i>p||i<p){
                int a;
                if(i<p)a=1;
                else if(i>p)a=0;
                if(!(temp%M)){
                    sum++;
                    //cout<<s+c[i]<<endl;
                    res+=cal1(n+1,i,a,0,s+c[i])+1;
                }
                else res+=cal1(n+1,i,a,temp%M,s+c[i]);
            }
        }
    }
    else {
        rep(i,10){
            int temp=mod*10;
            temp+=i;
            if(pp&&p<i){
                if(!(temp%M)){
                    sum++;
                    //cout<<s+c[i]<<endl;
                    res+=cal1(n+1,i,0,0,s+c[i])+1;
                }
                else res+=cal1(n+1,i,0,temp%M,s+c[i]);
            }
            else if(!(pp)&&p>i){
                if(!(temp%M)){
                    sum++;
                    //cout<<s+c[i]<<endl;
                    res+=cal1(n+1,i,1,0,s+c[i])+1;
                }
                else res+=cal1(n+1,i,1,temp%M,s+c[i]);
            }
        }
    }
    return mem1[n][p][pp][mod]=res%MOD;
}

int cal(int n,int p,int pp,int mod,int f,string s){
    int res=0;
    if(mem2[n][p][pp][mod][f]!=0){
        return mem2[n][p][pp][mod][f];
    }
    if(n==str.size()-1&&mod==0){
        return 1;
    }
    else if(n==str.size()-1) return 0;
    rep(i,10){
        int b=f;
        if(b==1){
            if(str[n+1]-'0'>i){
                b=0;
            }
            if(str[n+1]-'0'==i){
                b=1;
            }
            if(str[n+1]-'0'<i){
                continue;
            }
        }
        int temp=mod*10;
        temp+=i;
        if(n==0){
            if(i>p||i<p){
                int a=(i<p);
                if(!(temp%M)){
                    res+=cal(n+1,i,a,0,b,s+c[i]);
                }
                else res+=cal(n+1,i,a,temp%M,b,s+c[i]);
            }
        }
        else{
            if((pp&&p<i)||(n==0&&p<i)){
                if(!(temp%M)){
                        res+=cal(n+1,i,0,temp%M,b,s+c[i]);
                }
                else res+=cal(n+1,i,0,temp%M,b,s+c[i]);
            }
            else if((!(pp)&&p>i)||(n==0&&p>i)){
                if(!(temp%M)){
                        res+=cal(n+1,i,1,temp%M,b,s+c[i]);
                }
                else res+=cal(n+1,i,1,temp%M,b,s+c[i]);
            }
        }
    }
    return mem2[n][p][pp][mod][f]=res%MOD;
}

int main(){
    LL ans=0;
    cin>>str1>>str2;
    cin>>M;
    int vl=0;
    int vr=0;
    rep(i,2){
        FOR(j,1,9){
            string s;
            if(i==0){
                str=str1;
                if(j%M==0&&str.size()!=1&&str[0]>j)vl++;
                if(str.size()!=1)vl+=cal1(0,j,0,j%M,s+c[j]);
                if(str[0]-'0'>j)vl+=cal(0,j,0,j%M,0,s+c[j]);
                if(str[0]-'0'==j) vl+=cal(0,j,0,j%M,1,s+c[j]);
                if(j==str[0]-'0'&&str.size()==1)vl--;
            }
            else {
                str=str2;
                if(j%M==0&&(str.size()>1||str[0]>=j))vr++;
                vr+=cal1(0,j,0,j%M,s+c[j]);
                if(str[0]-'0'>j)vr+=cal(0,j,0,j%M,0,s+c[j]);
                else if(str[0]-'0'==j)vr+=cal(0,j,0,j%M,1,s+c[j]);
            }
            /*if(str1.size()==str2.size()){
                if(str1[0]-'0'<i&&str2[0]-'0'>i)ans+=cal4(0,i,0,i%M,0,s+c[i]);
                else if(str1[0]-'0'==i)ans+=cal4(0,i,0,i%M,1,s+c[i]);
                else if(str2[0]-'0'==i)ans+=cal4(0,i,0,i%M,2,s+c[i]);
                continue;
            }
            ans+=cal1(0,i,0,i%M,s+c[i]);
            if(str1[0]-'0'<=i&&i!=0){
                    if(str1[0]-'0'<i)ans+=cal2(0,i,0,i%M,0,s+c[i]);
                    else ans+=cal2(0,i,0,i%M,1,s+c[i]);
            }
            if(str2[0]-'0'>=i&&i!=0){
                if(str2[0]-'0'>i)ans+=cal3(0,i,0,i%M,0,s+c[i]);
                else ans+=cal3(0,i,0,i%M,1,s+c[i]);
            }*/
        }
    }
    cout<<(vr-vl)&M<<endl;
}