import std.stdio;
import core.stdc.stdio;
import std.algorithm;
import std.math;
import core.stdc.string;

char[] A;
char[] B;

class Arr{
	int as,bs,cs,ds;
	void Set(int a,int b,int c,int d){
		as = a;
		bs = b;
		cs = c;
		ds = d;
		data = new int[a*b*c*d];
	}
	this(){
		Set(500,10,2,3);
	}
	int[] data;
	ref int opIndex(int a,int b,int c,int d){
		return data[(((a)*bs+b)*cs+c)*ds+d];
	}
	void Clear(){
		data[] = 0;
	}
}

Arr now;
Arr next;

static immutable modBase = 10000;

void Minus(char[] d,int idx){
	if(d[idx] == 0){
		d[idx] = 9;
		d.Minus(idx-1);
	}else{
		d[idx]--;
	}
}

int Count(char[] d,int m,bool minus){
	int len = strlen(d.ptr);
	for(int i=0;i<len;i++){
		d[i] -= '0';
	}
	if(minus)
		d[0..len].Minus(len-1);
	now.Clear;
	
	int md=1;
	int res=0;
	foreach_reverse(_,c;d[0..len]){
		next.Clear;
		for(int i=0;i<m;i++){
			for(int j=0;j<10;j++){
				if(_ == len-1){
					if(i==0){
						next[j%m,j,j<=c?0:1,2] = 1;
					}
				}else{
					for(int k=0;k<10;k++){
						if(j==k) continue;
						int t = 0;
						int s = 1;
						if(j > k) swap(s,t);
						if(j<c){
							next[(i+md*j)%m,j,0,t] += now[i,k,0,s] + now[i,k,1,s] + now[i,k,0,2] + now[i,k,1,2];
							next[(i+md*j)%m,j,0,t] %= modBase;
						}else if(j==c){
							next[(i+md*j)%m,j,0,t] += now[i,k,0,s] + now[i,k,0,2];
							next[(i+md*j)%m,j,1,t] += now[i,k,1,s] + now[i,k,1,2];
							next[(i+md*j)%m,j,0,t] %= modBase;
							next[(i+md*j)%m,j,1,t] %= modBase;
						}else{
							next[(i+md*j)%m,j,1,t] += now[i,k,0,s] + now[i,k,1,s] + now[i,k,0,2] + now[i,k,1,2];
							next[(i+md*j)%m,j,1,t] %= modBase;
						}
					}
				}
			}
		}
		swap(now,next);
		for(int i=1;i<10;i++){
			res += now[0,i,0,0] + now[0,i,0,1] + now[0,i,0,2];
			if(_>0)
				res += now[0,i,1,0] + now[0,i,1,1] + now[0,i,1,2];
			res %= modBase;
		}
		md *= 10;
		md %= m;
	}
	
	return res;
}

void main(){
	A = new char[514];
	B = new char[514];
	scanf("%s",A.ptr);
	scanf("%s",B.ptr);

	int m;
	scanf("%d",&m);
	
	now = new Arr;
	next = new Arr;
	
	int ac = A.Count(m,true);
	int bc = B.Count(m,false);
	
	printf("%d\n",(bc+modBase-ac)%modBase);
}