当前没有测试数据。

题目描述

考虑一个整数的十进制表示。若数字 $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 \le m \le 2000$，$0 \le d \le 9$），表示题目给定的参数。
第二行输入一个无前置零的正整数 $a$（十进制表示）。
第三行输入一个无前置零的正整数 $b$（十进制表示）。

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

输出格式

输出一个整数，表示区间 $[a, b]$ 内满足条件的数的个数对 $10^9 + 7$ 取模的结果。

样例输入 1

2 6
10
99

样例输出 1

8

样例输入 2

2 0
1
9

样例输出 2

4

样例输入 3

19 7
1000
9999

样例输出 3

6

备注

• 第一个样例的答案对应的数为：16、26、36、46、56、76、86、96。
• 第二个样例的答案对应的数为：2、4、6、8。
• 第三个样例的答案对应的数为：1767、2717、5757、6707、8797、9747。