#include "stdio.h"
#include "string.h"
#include <iostream>

using namespace std;

int dp[500][500][10][3][3];

char a[555];
char b[555];

char aw[500];
char bw[500];

int main()
{
	int m;
	scanf("%s",a);
	scanf("%s",b);
	scanf("%d",&m);
	int l = strlen(b);
	for(int i = 0; i < l; i++)
	{
		if(i >= l - strlen(b))
		{
			aw[i] = a[i - (l - strlen(b))] - '0';
		}
		else
		{
			aw[i] = 0;
		}
		bw[i] = b[i] - '0';
	}
	for(int j = 0; j < 500; j++)
	{
		for(int i = 0; i < 500; i++)
		{
			for(int ii = 0; ii < 10; ii++)
			{
				for(int iii = 0; iii < 2; iii++)
				{
					for(int iiii = 0; iiii < 3; iiii++)
					{
						dp[j][i][ii][iii][iiii] = 0;
					}
				}
			}
		}
	}
	for(int i = 0; i < 10; i++)
	{
		for(int ii = 0; ii < 2; ii++)
		{
			if(i == aw[0])
			{
				if(i == 0)
				{
					dp[0][i % m][i][3][1] = 1;
				}
				else
				{
					dp[0][i % m][i][ii][1] = 1;
				}
			}
			else if(i == bw[0])
			{
				dp[0][i % m][i][ii][2] = 1;
			}
			else if(aw[0] < i && i < bw[0])
			{
				dp[0][i % m][i][ii][0] = 1;
			}
		}
	}
	for(int i = 1; i < l; i++)
	{
		for(int ii = 0; ii < 10; ii++)
		{
			for(int j = 0; j < 10; j++)
			{
				if(ii < aw[i])
				{
					if(ii < j)
					{
						for(int jj = 0; jj < m; jj++)
						{
							dp[i][(jj + ii) % m][ii][i % 2][0] += dp[i - 1][jj][j][i % 2][0];
							dp[i][(jj + ii) % m][ii][i % 2][0] += dp[i - 1][jj][j][i % 2][2];
						}
					}
					else if(ii > j)
					{
						for(int jj = 0; jj < m; jj++)
						{
							dp[i][(jj + ii) % m][ii][i % 2][0] += dp[i - 1][jj][j][(i + 1) % 2][0];
							dp[i][(jj + ii) % m][ii][i % 2][0] += dp[i - 1][jj][j][(i + 1) % 2][2];
						}
					}
				}
				else if(ii == aw[i])
				{
					if(ii == 0)
					{
						dp[i][0][ii][3][1] = 1;
					}
					else if(ii < j)
					{
						for(int jj = 0; jj < m; jj++)
						{
							dp[i][(jj + ii) % m][ii][i % 2][0] += dp[i - 1][jj][j][i % 2][0];
							dp[i][(jj + ii) % m][ii][i % 2][1] += dp[i - 1][jj][j][i % 2][1];
							dp[i][(jj + ii) % m][ii][i % 2][1] += dp[i - 1][jj][j][3][1];
							dp[i][(jj + ii) % m][ii][i % 2][0] += dp[i - 1][jj][j][i % 2][2];
						}
					}
					else if(ii > j)
					{
						for(int jj = 0; jj < m; jj++)
						{
							dp[i][(jj + ii) % m][ii][i % 2][0] += dp[i - 1][jj][j][(i + 1) % 2][0];
							dp[i][(jj + ii) % m][ii][i % 2][1] += dp[i - 1][jj][j][(i + 1) % 2][1];
							dp[i][(jj + ii) % m][ii][i % 2][1] += dp[i - 1][jj][j][3][1];
							dp[i][(jj + ii) % m][ii][i % 2][0] += dp[i - 1][jj][j][(i + 1) % 2][2];
						}
					}
				}
				else if(ii == bw[i])
				{
					if(ii < j)
					{
						for(int jj = 0; jj < m; jj++)
						{
							dp[i][(jj + ii) % m][ii][i % 2][0] += dp[i - 1][jj][j][i % 2][0];
							dp[i][(jj + ii) % m][ii][i % 2][0] += dp[i - 1][jj][j][i % 2][1];
							dp[i][(jj + ii) % m][ii][i % 2][0] += dp[i - 1][jj][j][3][1];
							dp[i][(jj + ii) % m][ii][i % 2][2] += dp[i - 1][jj][j][i % 2][2];
						}
					}
					else if(ii > j)
					{
						for(int jj = 0; jj < m; jj++)
						{
							dp[i][(jj + ii) % m][ii][i % 2][0] += dp[i - 1][jj][j][(i + 1) % 2][0];
							dp[i][(jj + ii) % m][ii][i % 2][0] += dp[i - 1][jj][j][(i + 1) % 2][1];
							dp[i][(jj + ii) % m][ii][i % 2][0] += dp[i - 1][jj][j][3][1];
							dp[i][(jj + ii) % m][ii][i % 2][2] += dp[i - 1][jj][j][(i + 1) % 2][2];
						}
					}
				}
				else if(bw[i] < ii)
				{
					if(ii < j)
					{
						for(int jj = 0; jj < m; jj++)
						{
							dp[i][(jj + ii) % m][ii][i % 2][0] += dp[i - 1][jj][j][i % 2][0];
							dp[i][(jj + ii) % m][ii][i % 2][0] += dp[i - 1][jj][j][i % 2][1];
							dp[i][(jj + ii) % m][ii][i % 2][0] += dp[i - 1][jj][j][3][1];
						}
					}
					else if(ii > j)
					{
						for(int jj = 0; jj < m; jj++)
						{
							dp[i][(jj + ii) % m][ii][i % 2][0] += dp[i - 1][jj][j][(i + 1) % 2][0];
							dp[i][(jj + ii) % m][ii][i % 2][0] += dp[i - 1][jj][j][(i + 1) % 2][1];
							dp[i][(jj + ii) % m][ii][i % 2][0] += dp[i - 1][jj][j][3][1];
						}
					}
				}
				else
				{
					if(ii < j)
					{
						for(int jj = 0; jj < m; jj++)
						{
							dp[i][(jj + ii) % m][ii][i % 2][0] += dp[i - 1][jj][j][i % 2][0];
							dp[i][(jj + ii) % m][ii][i % 2][0] += dp[i - 1][jj][j][i % 2][1];
							dp[i][(jj + ii) % m][ii][i % 2][0] += dp[i - 1][jj][j][3][1];
							dp[i][(jj + ii) % m][ii][i % 2][0] += dp[i - 1][jj][j][i % 2][2];
						}
					}
					else if(ii > j)
					{
						for(int jj = 0; jj < m; jj++)
						{
							dp[i][(jj + ii) % m][ii][i % 2][0] += dp[i - 1][jj][j][(i + 1) % 2][0];
							dp[i][(jj + ii) % m][ii][i % 2][0] += dp[i - 1][jj][j][(i + 1) % 2][1];
							dp[i][(jj + ii) % m][ii][i % 2][0] += dp[i - 1][jj][j][3][1];
							dp[i][(jj + ii) % m][ii][i % 2][0] += dp[i - 1][jj][j][(i + 1) % 2][2];
						}
					}
				}
			}
		}
		for(int j = 0; j < 500; j++)
		{
			for(int jj = 0; jj < 10; jj++)
			{
				for(int jjj = 0; jjj < 3; jjj++)
				{
					for(int jjjj = 0; jjjj < 3; jjjj++)
					{
						dp[i][j][jj][jjj][jjjj] %= 10000;
					}
				}
			}
		}
	}
	int max = 0;
	for(int i = 0; i < 10; i++)
	{
		for(int ii = 0; ii < 3; ii++)
		{
			for(int iii = 0; iii < 3; iii++)
			{
				max = (max + dp[l - 1][0][i][ii][iii]) % 10000;
			}
		}
	}
	printf("%d\n",max);
	return 0;
}