#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<functional>
#include<string>
#include<cstring>
using namespace std;
#define LATTE 10000

int dp[2][502][10][500][2][2];


int main(){
	char str[2][502];
	int M;
	cin>>str[0]>>str[1]>>M;
	int len[2] = {strlen(str[0]),strlen(str[1])};
	for(int i=0;i<2;i++)for(int j=0;j<len[i];j++) str[i][j]-='0';

	int ans[2]={};
	for(int m=0;m<2;m++){
		//printf(" %d,%d\n",str[m][0],len[m]);
		for(int i=1;i<str[m][0];i++){
			dp[m][0][i][i%M][0][0] = 1;
			if(0!=len[m]-1) dp[m][0][i][i%M][1][0] = 1;
			//printf("  %d,%d\n",i,i%M);
		}
		dp[m][0][str[m][0]][str[m][0]%M][0][1] = 1;
		if(0!=len[m]-1) dp[m][0][str[m][0]][str[m][0]%M][1][1] = 1;

		/*for(int i=0;i<10;i++){
			printf("%d ",dp[m][0][i][0][0][0]+dp[m][0][i][0][1][0]+dp[m][0][i][0][0][1]+dp[m][0][i][0][1][1]);
		}puts("");*/

		for(int i=0;i+1<len[m];i++){
			for(int j=1;j<10;j++){
				dp[m][i+1][j][j%M][0][0] = 1;
				if(i+1!=len[m]-1) dp[m][i+1][j][j%M][1][0] = 1;
			}
			for(int j=0;j<10;j++){
				for(int k=0;k<M;k++){
					for(int l=j+1;l<10;l++){
						dp[m][i+1][l][(k*10+l)%M][1][0] += dp[m][i][j][k][0][0]%LATTE;
						if(l<str[m][i+1])
							dp[m][i+1][l][(k*10+l)%M][1][0] += dp[m][i][j][k][0][1]%LATTE;
						if(l==str[m][i+1])
							dp[m][i+1][l][(k*10+l)%M][1][1] += dp[m][i][j][k][0][1]%LATTE;
					}
					for(int l=j-1;l>=0;l--){
						dp[m][i+1][l][(k*10+l)%M][0][0] += dp[m][i][j][k][1][0]%LATTE;
						if(l<str[m][i+1])
							dp[m][i+1][l][(k*10+l)%M][0][0] += dp[m][i][j][k][1][1]%LATTE;
						if(l==str[m][i+1])
							dp[m][i+1][l][(k*10+l)%M][0][1] += dp[m][i][j][k][1][1]%LATTE;
					}
				}
			}
		}
		for(int i=0;i<10;i++){
			ans[m] += (dp[m][len[m]-1][i][0][0][0]+dp[m][len[m]-1][i][0][1][0])%LATTE;
			if(m==1)
				ans[m] += (dp[m][len[m]-1][i][0][0][1]+dp[m][len[m]-1][i][0][1][1])%LATTE;
		}
	}
	printf("%d\n",(ans[1]%LATTE+LATTE-ans[0]%LATTE)%LATTE);
    return 0;
}