问题

問題

正整数的十进制表示是逐个查看数字的位数时交替增加和减少的时候，这个数被称为"锯齿数"。例如，$2947$ 是一个锯齿数，因为数字的位数依次增加、减少、增加，即$2$ → $9$ → $4$ → $7$。同样，$71,946$ 是一个锯齿数，因为数字的位数依次减少、增加、减少、增加。然而，$123$、$71,446$、$71,442$ 和 $88$ 都不是锯齿数。需要注意的是，一个位数的正整数被视为锯齿数。

编写一个程序，求出 $A$ 到 $B$ 之间的倍数中，锯齿数的个数除以 $10,000$ 的余数。

输入

输入包含 $3$ 行，每行包含一个正整数。

第一行为 $A$，第二行为 $B$，第三行为 $M$。它们满足 $1 \\leqq A \\leqq B \\leqq 10^{500}$，$1 \\leqq M \\leqq 500$。

※ 注意，$A$ 和 $B$ 的值可能超出常规整数数据类型的范围。

输出

输出为一行，为 $A$ 到 $B$ 之间的 $M$ 的倍数中，锯齿数的个数除以 $10,000$ 的余数。

输入示例 1

100
200
5

输出示例 1

13

在输入示例 $1$ 中，$100$ 到 $200$ 之间的 $5$ 的倍数中，有 $13$ 个锯齿数: $105, 120, 130, 140, 150, 160, 165, 170, 175, 180, 185, 190, 195$。

输入示例 2

6
1234567
3

输出示例 2

246

在输入示例 $2$ 中，$6$ 到 $1,234,567$ 之间的 $3$ 的倍数中，有 $50,246$ 个锯齿数。求出它除以 $10,000$ 的余数，结果为 $246$。