Magic Numbers

给你 $4$ 个数 $m,d,l,r$ ,保证 $l,r$ 位数相同。 问满足以下条件的数 $x$ 的个数： 1. $l \leq x\leq r$ 2. $x$ 的偶数位是 $d$，奇数位不是 $d$。 （这里定义偶数位为从高位往低位的数的偶数位） 3. $m|x$ 答案对 $1000000007$ 取模。 $1\le m \le 2000,0\le d \le 9,1\le l \le r \le 10^{2000}$

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-magic and $ 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 $ 10^{9}+7 $ (so you should find the remainder after dividing by $ 10^{9}+7 $ ).

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 $ .

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

2 6
10
99

8

2 0
1
9

4

19 7
1000
9999

6

The numbers from the answer of the first example are $ 16 $ , $ 26 $ , $ 36 $ , $ 46 $ , $ 56 $ , $ 76 $ , $ 86 $ and $ 96 $ . The numbers from the answer of the second example are $ 2 $ , $ 4 $ , $ 6 $ and $ 8 $ . The numbers from the answer of the third example are $ 1767 $ , $ 2717 $ , $ 5757 $ , $ 6707 $ , $ 8797 $ and $ 9747 $ .