CodeForces - 628D （数位dp）

CodeForces - 628D （数位dp）

Consider the decimal presentation of an integer. Let's call a number d-magic if digit d appears in decimal presentation of the number on even positions and nowhere else.

For example, the numbers 1727374, 17, 1 are 7-magic but 77, 7, 123, 34, 71 are not 7-magic. On the other hand the number 7 is 0-magic, 123 is 2-magic, 34 is 4-magicand 71 is 1-magic.

Find the number of d-magic numbers in the segment [a, b] that are multiple of m. Because the answer can be very huge you should only find its value modulo 109 + 7 (so you should find the remainder after dividing by 109 + 7).

Input

The first line contains two integers m, d (1 ≤ m ≤ 2000, 0 ≤ d ≤ 9) — the parameters from the problem statement.

The second line contains positive integer a in decimal presentation (without leading zeroes).

The third line contains positive integer b in decimal presentation (without leading zeroes).

It is guaranteed that a ≤ b, the number of digits in a and b are the same and don't exceed 2000.

Output

Print the only integer a — the remainder after dividing by 109 + 7 of the number of d-magic numbers in segment [a, b] that are multiple of m.

Examples

Input

2 6 10 99

Output

8

Input

2 0 1 9

Output

4

Input

19 7 1000 9999

Output

6

题目大意：

求一个区间内某种数的个数，需要是m的倍数，并且奇数位不能包含d，偶数为必须包含d。数的位数是2000位。

思路：

首先是数位dp。

关于m的限制，直接便计算边取模就行。d限制，需要分奇偶讨论一下。

数的位数很大，需要用字符串，这样的话，闭区间，左边的数减一不好计算，需要特判一下。

代码：

#include #include #include #include #include #include #include

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。