AT_joi2012yo_f ジグザグ数 (Zig-Zag Numbers)

我们称一个正整数为「锯齿数」，如果它的十进制表示形式中各个数字的位置趋势交替上升或下降。例如，数字 $2947$ 的数字顺序为 $2 \to 9 \to 4 \to 7$，形成了 增 → 减 → 增 的模式，因此它是一个锯齿数。同样地，数字 $71\,946$ 的排列为减 → 增 → 减 → 增，因此也是锯齿数。但像 $123$、$71\,446$、$71\,442$ 和 $88$ 则不符合。规定一位数的数字也是锯齿数。 你的任务是编写一个程序，统计在 $A$ 到 $B$ 之间，所有能被 $M$ 整除的锯齿数的个数，并输出该数量对 $10\,000$ 取模后的结果。

输入共三行，每行一个正整数： 第一行为整数 $A$，第二行为整数 $B$，第三行为整数 $M$。这些数满足 $1 \leq A \leq B \leq 10^{500}$，$1 \leq M \leq 500$。 需要注意的是，$A$ 和 $B$ 的值可能大于普通整数类型所能表示的范围。

输出一行，表示在 $A$ 到 $B$ 之间，所有能够被 $M$ 整除的锯齿数的数量，对 $10\,000$ 取模后的结果。

### 样例解释 1 在样例 1 中，位于 $100$ 到 $200$ 之间的、能够被 $5$ 整除且是锯齿数的数包括：$105,\ 120,\ 130,\ 140,\ 150,\ 160,\ 165,\ 170,\ 175,\ 180,\ 185,\ 190,\ 195$。共 $13$ 个。 ### 样例解释 2 在样例 2 中，位于 $6$ 到 $1\,234\,567$ 之间的、可以被 $3$ 整除的锯齿数总共有 $50\,246$ 个。因而输出为这些数的数量对 $10\,000$ 取模后的值 $246$。 **本翻译由 AI 自动生成**