题目描述

给定四个整数 $m(1 \le m \le 2000)$，$d(0 \le d \le 9)$，$l$ 和 $r$（$1 \le l \le r \lt 10^{2000}$），且 $l$ 和 $r$ 对应的十进制数的位数相同。

你需要找到 $[l, r]$ 范围内存在多少个同时满足如下两个条件的整数 $a(l \le a \le r)$：

1. $a$ 从高到低偶数位上的数字都是 $d$，同时 $a$ 从高到低奇数位上的数字都不是 $d$；
2. $a$ 能被 $m$ 整除。

由于满足条件的数可能很多，所以你只需要输出满足条件的数的个数模 $10^9 + 7$ 的结果即可。

输入格式

第一行，两个整数 $m$ 和 $d$（$1 \le m \le 2000, 0 \le d \le 9$）。

第二行，一个整数 $l$。

第三行，一个整数 $r$。

数据保证 $l$ 和 $r$ 位数相同，且不超过 $2000$ 位。

输出格式

输出一个整数，表示满足条件（区间 $[l, r]$ 范围内所有偶数位为 $d$ 奇数为不为 $d$ 且能被 $m$ 整除）的数的个数模 $10^9 + 7$ 的结果。

样例

2 6
10
99

8

2 0
1
9

4

19 7
1000
9999

6

说明/提示

样例解释

• 样例1：满足条件的数有 $16, 26, 36, 46, 56, 76, 86, 96$
• 样例2：满足条件的数有 $2, 4, 6, 8$
• 样例3：满足条件的数有 $1767, 2717, 5757, 6707, 8797, 9747$

数据规模与约定

• 对于 $20\%$ 的数据，$m \le 20$，$l$ 和 $r$ 不超过 $10$ 位；
• 对于 $50\%$ 的数据，$m \le 200$，$l$ 和 $r$ 不超过 $200$ 位；
• 对于 $100\%$ 的数据，$1 \le m \le 2000, 0 \le d \le 9$，$l$ 和 $r$ 不超过 $2000$ 位。