CF628D Magic Numbers

考虑一个整数 $n$ 的十进制表示。如果某个数字 $d$ 出现且仅出现在该整数 $n$ 的所有偶数位（从左至右编号，从 1 开始）上，则称这个数字为 $d$-魔法数。特别的，若整数 $n$ 的十进制表示中不包含偶数位，则所有未在奇数位出现的数字 $d$ 都可以使得该整数 $n$ 被称为 $d$-魔法数。 例如，$1727374$、$17$、$1$ 都是 7-魔法数，但 $77$、$7$、$123$、$34$、$71$ 不是 7-魔法数。另一方面，$7$ 是 0-魔法数，$123$ 是 2-魔法数，$34$ 是 4-魔法数，$71$ 是 1-魔法数。 对于给定的整数 $m$，求区间 $[a,b]$ 内所有是 $m$ 的倍数的 $d$-魔法数的个数。由于答案可能非常大，只需输出其对 $10^{9}+7$ 取余的结果。

第一行包含两个整数 $m,d$（$1 \le m \le 2000$，$0 \le d \le 9$）——题目中的参数。 第二行包含一个正整数 $a$ 的十进制表示（无前导零）。 第三行包含一个正整数 $b$ 的十进制表示（无前导零）。 保证 $a \le b$，且 $a$ 和 $b$ 的位数相同，且不超过 $2000$。

输出一个整数 $a$，即区间 $[a,b]$ 内所有同时满足 $d$-魔法性质且是 $m$ 的倍数的数字的个数对 $10^{9}+7$ 取余的值。

第一个样例的答案中的数字为 $16$、$26$、$36$、$46$、$56$、$76$、$86$ 和 $96$。 第二个样例的答案中的数字为 $2$、$4$、$6$ 和 $8$。 第三个样例的答案中的数字为 $1767$、$2717$、$5757$、$6707$、$8797$ 和 $9747$。 由 ChatGPT 5 翻译