A positive integer is called a zig-zag number if the digits, when read from left to right, alternate between increasing and decreasing.

For example, 2947 is a zig-zag number because the sequence of its digits alternates between increasing (2 → 9) and decreasing (9 → 4) and then increasing again (4 → 7). Similarly, 71946 is a zig-zag number because its digits alternate between decreasing (7 → 1) and increasing (1 → 9) and so on. Conversely, numbers like 123, 71446, 71442, or 88 are not zig-zag numbers. Note that single-digit positive integers are considered zig-zag numbers.

Given integers A, B, and M, find the number of zig-zag numbers between A and B that are multiples of M, and output the count modulo 10000.

The input consists of 3 lines:

• The first line contains the integer A.
• The second line contains the integer B. The third line contains the integer M.

The values satisfy the constraints: 1≤A≤B≤10500 and 1≤M≤500. Note that A and B may be larger than standard integer types.

Print a single integer which is the count of zig-zag numbers between A and B that are multiples of M, modulo 10000.

• Explanation Example 1: There are 13 zig-zag numbers between 100 and 200 that are multiples of 5: 105, 120, 130, 140, 150, 160, 165, 170, 175, 180, 185, 190, and 195.
• Explanation Example 2: There are 50246 zig-zag numbers between 6 and 1234567 that are multiples of 3. The result modulo 10000 is 246.