303230: CF628D. Magic Numbers
Memory Limit：256 MB
Time Limit：2 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
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 $ .
输入输出样例
输入样例 #1
2 6
10
99
输出样例 #1
8
输入样例 #2
2 0
1
9
输出样例 #2
4
输入样例 #3
19 7
1000
9999
输出样例 #3
6