考虑整数的十进制表示形式。如果数字 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。