← 返回题目列表

Codeforces · 628/D

D. 魔法数字

中文机器翻译题面 查看原题

考虑整数的十进制表示形式。如果数字 d 出现在该数字的十进制表示中的偶数位置而不是其他地方,我们称该数字为 d-magic。

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

求段 [a, b] 中 d-magic 数是 m 的倍数。因为答案可能非常大,所以您应该只找到它对 109 + 7 求模的值(因此您应该找到除以 109 + 7 后的余数)。

输入

第一行包含两个整数 m、d (1 ≤ m ≤ 2000, 0 ≤ d ≤ 9) — 问题陈述中的参数。

第二行包含十进制表示的正整数 a(不带前导零)。

第三行包含十进制表示的正整数 b(不带前导零)。

保证a ≤ b,a和b的位数相同且不超过2000。

输出

打印唯一的整数 a — 段 [a, b] 中 m 倍数的 d-magic 数除以 109 + 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。