描述

考虑一个整数的十进制表示。我们称一个数字为 $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$ 后的余数）。

输入

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

第二行包含十进制表示中的正整数 $a$（没有前导零）。

第三行包含十进制表示中的正整数 $b$（没有前导零）。

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

输出

输出一个整数 $a$，即区间 $[a, b]$ 中为 $d$-幻数且是 $m$ 的倍数的数字个数对 $10^9+7$ 取模后的余数。

2 6
10
99

2 0
1
9

19 7
1000
9999

8

4

6

注意

第一个示例的答案中的数字是 $16$, $26$, $36$, $46$, $56$, $76$, $86$ 和 $96$。

第二个示例的答案中的数字是 $2$, $4$, $6$ 和 $8$。

第三个示例的答案中的数字是 $1767$, $2717$, $5757$, $6707$, $8797$ 和 $9747$。