rt，能过样例 #1 但是不过样例 #2

#include<bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define int long long
#define F(i,x,y) for(int i=x;i<=y;++i)
#define G(i,x,y) for(int i=x;i>=y;--i)
#define FD(x,y) for(int i=x;i*i<=y;++i)
#define GD(x,y) for(int i=x;i*i>=y;--i)
#define adde(x,y) z[x].eb(y);
#define Adde(x,y) z[x].eb(y),z[y].eb(x);
#define addew(x,y,w) z[x].eb(y,w)
#define Addew(x,y,w) z[x].eb(y,w),z[y].eb(x,w)
#define FIMX(X) memset(X,0x3f,sizeof X)
#define FIMI(X) memset(X,-0x3f,sizeof X)
#define FI0(X) memset(X,0,sizeof X)
#define FIN(X) memset(X,-1,sizeof X)
#define rng(X) X.begin(),X.end()
#define PII pair<int,int>
#define PDD pair<double,double>
#define PIII tuple<int,int,int>
#define VI vector<int>
#define VII vector<PII>
#define VID vector<pair<int,double>>
#define VDD vector<PDD>
using namespace std;
int f[20][500010],now,s[233],idx;
//设当前枚举到了第i位 当前这个数 mod x=j 的方案数
void todo(int x){
    idx=0;
    while(x){
        s[++idx]=x%10;
        x/=10;
    }
}
int canuse[10];
int X,l,r;
int dfs(int len,int yu,int lim){
    if(!lim&&~f[len][yu])return f[len][yu];
    if(!len){
        if(!yu)return 1;
        return 0;
    }
    int limit=lim?s[len]:9,res=0;
    F(i,0,limit)if(canuse[i])
        res+=dfs(len-1,(yu*10+i)%X,lim&&(i==s[len]));
    if(!lim)f[len][yu]=res;
    return res;
}
int fun(int x){
    if(x<=5e5){
        todo(x);
        FIN(f);
        return dfs(idx,0,1);
    }else{
        int cnt=0;
        for(int i=X;i<=x/X*X;i+=X){
            string s=to_string(i);
            int ok=1;
            for(auto &j:s)
                if(!canuse[j-'0']){ok=0;break;}
            if(ok)++cnt;
        }
        return cnt;
    }
}
signed main(){
//  freopen("count_in","r",stdin);freopen("count.out","w",stdout);
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>X>>l>>r;
    string s;cin>>s;
    for(auto&x:s)canuse[x-'0']=1;
    cout<<fun(r)-fun(l-1)<<'\n';
    return 0;
}