CF628D.Magic Numbers

Consider the decimal presentation of an integer. Let's call a number d-magic if digit d appears in decimal presentation of the number on even positions and nowhere else.

For example, the numbers 1727374, 17, 1 are 7-magic but 77, 7, 123, 34, 71 are not 7-magic. On the other hand the number 7 is 0-magic, 123 is 2-magic, 34 is 4-magic and 71 is 1-magic.

Find the number of d-magic numbers in the segment [a, b] that are multiple of m. Because the answer can be very huge you should only find its value modulo 109 + 7 (so you should find the remainder after dividing by 109 + 7).

考虑一个整数的十进制表示。我们称一个数为 d-魔法数，如果数字 $d$ 恰好出现在该数的十进制表示中所有偶数位置上，且不出现于任何其他位置。

例如，数字 $1727374$、$17$、$1$ 都是 $7$-魔法数，但 $77$、$7$、$123$、$34$、$71$ 不是 $7$-魔法数。另一方面，数字 $7$ 是 $0$-魔法数，$123$ 是 $2$-魔法数，$34$ 是 $4$-魔法数，$71$ 是 $1$-魔法数。

求区间 $[a,\,b]$ 中既是 $d$-魔法数又是 $m$ 的倍数的整数个数。由于答案可能非常大，你只需输出其对 $10^9 + 7$ 取模的结果（即除以 $10^9 + 7$ 后的余数）。

The first line contains two integers m, d (1 ≤ m ≤ 2000, 0 ≤ d ≤ 9) — the parameters from the problem statement.

The second line contains positive integer a in decimal presentation (without leading zeroes).

The third line contains positive integer b in decimal presentation (without leading zeroes).

It is guaranteed that a ≤ b, the number of digits in a and b are the same and don't exceed 2000.

第一行包含两个整数 $m$、$d$（$1 \leq m \leq 2000$，$0 \leq d \leq 9$）——即题目描述中的参数。

第二行包含一个正整数 $a$ 的十进制表示（不含前导零）。

第三行包含一个正整数 $b$ 的十进制表示（不含前导零）。

保证 $a \leq b$，且 $a$ 与 $b$ 的位数相同，且该位数不超过 $2000$。

Print the only integer a — the remainder after dividing by 109 + 7 of the number of d-magic numbers in segment [a, b] that are multiple of m.

输出唯一的整数 $a$ —— 即区间 $[a,\,b]$ 中所有 $d$-magic 数且为 $m$ 的倍数的个数，对 $10^9 + 7$ 取模后的余数。

The numbers from the answer of the first example are 16, 26, 36, 46, 56, 76, 86 and 96.

The numbers from the answer of the second example are 2, 4, 6 and 8.

The numbers from the answer of the third example are 1767, 2717, 5757, 6707, 8797 and 9747.

第一个示例答案中的数字为：16、26、36、46、56、76、86 和 96。

第二个示例答案中的数字为：2、4、6 和 8。

第三个示例答案中的数字为：1767、2717、5757、6707、8797 和 9747。