D. Magic Numbers

题目连接：

Description

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

Sample Input

2 6

10

99

Sample Output

8

Hint

题意

现在定义d-magic数字，就是一个没有前导0的数，d恰好仅出现在这个数的偶数位置。

然后现在给你m,d,a,b。问你在[a,b]内，是m的倍数，且是d-magic的数字有多少个

答案需要 mod 1e9+7

题解：

比较显然的数位dp

dp[len][mod][flag]表示现在长度是多少，现在的余数是多少，现在是否达到上界的方案数是多少

然后直接转移就好了

这个让L--很麻烦，所以我直接就判断L这个位置合不合法就好了，如果合法，我就直接让答案++就好了

代码

#include
    
     using namespace std;const int maxn = 2e3+5;const int mod = 1e9+7;int dp[maxn][maxn][2];int vis[maxn][maxn][2];char s[maxn];int m,d,len;int check(){    int mm = 0;    for(int i=1;i<=len;i++)    {        mm = (mm+s[i]-'0')%m;        if(i%2==1&&(s[i]-'0')==d)            return 0;        if(i%2==0&&(s[i]-'0')!=d)            return 0;    }    if(mm!=0)return 0;    return 1;}void update(int &a,int b){    a = (a+b)%mod;}int solve(int Len,int Mod,int Flag){    if(Len==len+1)return Mod==0?1:0;    if(vis[Len][Mod][Flag])return dp[Len][Mod][Flag];    vis[Len][Mod][Flag]=1;    int st=0,ed=0;    if(Flag!=0)ed=9;else ed=s[Len]-'0';    if(Len==1)st=1;else st=0;    if(Len%2==0)    {        if(ed>=d)        {            int Flag2 = Flag|(d<(s[Len]-'0'));            update(dp[Len][Mod][Flag],solve(Len+1,(Mod*10+d)%m,Flag2));        }    }    else    {        for(int i=st;i<=ed;i++)        {            if(i==d)continue;            int Flag2 = Flag|(i<(s[Len]-'0'));            update(dp[Len][Mod][Flag],solve(Len+1,(Mod*10+i)%m,Flag2));        }    }    return dp[Len][Mod][Flag];}int main(){    scanf("%d%d",&m,&d);    scanf("%s",s+1);    len = strlen(s+1);    memset(vis,0,sizeof(vis));    memset(dp,0,sizeof(dp));    int ans1 = solve(1,0,0),ans2=0;    if(check())ans2++;    scanf("%s",s+1);    len = strlen(s+1);    memset(vis,0,sizeof(vis));    memset(dp,0,sizeof(dp));    ans2 += solve(1,0,0);    int ans=(ans2-ans1)%mod;    if(ans<0)ans+=mod;    cout<
     
      <