rt 很奇怪的就寄在了第 29 个点

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10;
const int p=1e9+7;

int m,d;

int dp[2100][2100];
int a[2100],cnt;

int dfs(int len,int st,bool lim){
	if(!len) return st%m==0;
	if(!lim&&dp[len][st]!=-1) return dp[len][st];
	int limit=lim?a[len]:9; int ans=0;
	for(int i=0;i<=limit;i++){
		if((cnt-len)%2==0) {if(i==d) continue;} else if(i!=d) continue;
		ans=(ans+dfs(len-1,(st*10%m+i)%m,lim&&(i==a[len])))%p;
	}
	if(!lim) dp[len][st]=ans;
	return ans;
}

int work(string x){
	cnt=0; memset(a,0,sizeof a);
	for(int i=x.size()-1;i>=0;i--) a[++cnt]=x[i]-'0';
	return dfs(cnt,0,1);
}

int check(string x){
	cnt=0;
	for(int i=x.size()-1;i>=0;i--) a[++cnt]=x[i]-'0';
	int ans=0;
	for(int i=cnt;i>=1;i--){
		if((cnt-i)%2==1&&a[i]!=d) return 0;
		ans=(ans*10%m+a[i])%m;
	}
	if(ans%m!=0) return 0;
	return 1;
}


void fake_main(){
	string l,r; cin>>m>>d>>l>>r;
	cout<<((work(r)-work(l)+check(l))%p+p)%p<<"\n";
}

signed main(){
	memset(dp,-1,sizeof dp);
	ios::sync_with_stdio(false);
	int t; t=1;
	while(t--) fake_main();
}