지그재그 숫자

양의 정수에서 이웃한 두 자리 숫자의 대소 관계가 증가와 감소를 번갈아 나타날 때, 이 수를 지그재그 수라고 한다.

예를 들어 $2947$은 각 자리가 $2 \to 9 \to 4 \to 7$로 증가 → 감소 → 증가 순서이므로 지그재그 수이다. 또한 $71946$은 감소 → 증가 → 감소 → 증가 순서이므로 지그재그 수이다. 반면 $123$, $71446$, $71442$, $88$은 지그재그 수가 아니다. 한 자리 정수는 모두 지그재그 수로 본다.

$A$ 이상 $B$ 이하의 정수 중에서 $M$의 배수이면서 지그재그 수인 것의 개수를 구하는 프로그램을 작성하시오.

첫째 줄에 $A$, 둘째 줄에 $B$, 셋째 줄에 $M$이 주어진다. ($1 \le A \le B \le 10^{500}$, $1 \le M \le 500$)

$A$ 이상 $B$ 이하의 정수 중 $M$의 배수이면서 지그재그 수인 것의 개수를 $10000$으로 나눈 나머지를 출력한다.