#1917 · Zig-Zag Numbers

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.