Zigzag Numbers

A positive integer is called a zigzag number when, reading its digits from left to right, the comparison between each pair of adjacent digits alternates between increasing and decreasing.

For example, $2947$ is a zigzag number because its digits go $2 \to 9 \to 4 \to 7$, that is increase → decrease → increase. Likewise, $71946$ is a zigzag number because it goes decrease → increase → decrease → increase. On the other hand, $123$, $71446$, $71442$, and $88$ are not zigzag numbers. Every single-digit integer is considered a zigzag number.

Write a program that counts how many integers between $A$ and $B$ (inclusive) are multiples of $M$ and are also zigzag numbers.

The first line contains $A$, the second line contains $B$, and the third line contains $M$. ($1 \le A \le B \le 10^{500}$, $1 \le M \le 500$)

Print, modulo $10000$, the number of integers between $A$ and $B$ (inclusive) that are multiples of $M$ and are zigzag numbers.