Problem Description

Let's call a positive integer a "zig-zag number" if, when written in base 10 without leading zeros, the digits alternate between increasing and decreasing. For example, $2947$ is a zig-zag number because its digits $2 \rightarrow 9 \rightarrow 4 \rightarrow 7$ alternate in the order increase → decrease → increase. Also, $71,946$ is a zig-zag number because its digits alternate in the order decrease → increase → decrease → increase. On the other hand, $123$, $71,446$, $71,442$, and $88$ are not zig-zag numbers. Note that a single-digit positive integer is considered a zig-zag number.

Write a program to find the number of zig-zag numbers that are multiples of $M$ and lie between $A$ and $B$, inclusive, modulo $10,000$.

Input Format

The input consists of 3 lines, each containing a positive integer.

The first line contains the integer $A$, the second line contains the integer $B$, and the third line contains the integer $M$. These satisfy $1 \leq A \leq B \leq 10^{500}$ and $1 \leq M \leq 500$.

Note that the values of $A$ and $B$ may not fit into standard integer data types.

Output Format

Output a single line containing the number of zig-zag numbers that are multiples of $M$ and lie between $A$ and $B$, inclusive, modulo $10,000$.

Sample Input and Output

Sample Input #1

100
200
5

Sample Output #1

13

Sample Input #2

6
1234567
3

Sample Output #2

246

Notes/Hints

Sample Explanation 1

In sample input #1, the zig-zag numbers that are multiples of $5$ and lie between $100$ and $200$ are $105, 120, 130, 140, 150, 160, 165, 170, 175, 180, 185, 190, 195$, totaling $13$ numbers.

Sample Explanation 2

In sample input #2, there are $50,246$ zig-zag numbers that are multiples of $3$ and lie between $6$ and $1,234,567$. Therefore, output the remainder when $50,246$ is divided by $10,000$, which is $246$.

见题面 Input 部分

见题面 Output 部分