tle，还不稳定，有的时候是tle on 16,有的时候是tle on 35

#include<iostream>
#include<cstring>
using namespace std;
#define maxlen 2000
#define maxm 2000
#define mod (long long)(1e9+7)
long long m,d;
char l[maxlen+5],r[maxlen+5];
long long f[maxlen+5][2][maxm+5][2][2];
long long calc(char* s,long long x,bool iso,long long rst,bool lim,bool l0)
{
	if(x>=strlen(s))return !rst;
	if(f[x][iso][rst][lim][l0]>=0)return f[x][iso][rst][lim][l0];
	long long up=lim?s[x]-'0':9,res=0;
	for(int i=0;i<=up;i++)
	{
		if(l0&&!i)res=(res+calc(s,x+1,iso,rst,false,true))%mod;
		else if((iso&&i!=d)||(!iso&&i==d))
			res=(res+calc(s,x+1,!iso,(rst*10+i)%m,lim&&(i==up),false))%mod;
	}
	return f[x][iso][rst][lim][l0]=res;
}
int main()
{
	scanf("%lld%lld%s%s",&m,&d,l,r);
	l[strlen(l)-1]--;
    for(int i=strlen(l)-1;i>=1;i--)
        if(l[i]<'0')
        {
            l[i]+=10;
            l[i-1]--;
        }
    memset(f,-1,sizeof f);
    long long ans1=calc(r,0,true,0,true,true);
    memset(f,-1,sizeof f);
    long long ans2=calc(l,0,true,0,true,true);
	printf("%lld\n",(ans1-ans2+mod)%mod);
	return 0;
}