#include<bits/stdc++.h>
using namespace std;

#define int long long 
#define F first 
#define S second 
#define pb push_back
#define ld double

int dp[61][41][21][21][21][2][2], tot[61][41][21][21][21][2][2]; // 2, 3, 5, 7, 0, small, hav
int p2=0, p3=0, p5=0, p7=0;
int g2=0, g3=0, g5=0, g7=0;
const int mol=1e9+7;
void add(int &t1, int t2){
    t1+=t2;
    t1%=mol;
}

void add1(int j, int t1, int t2, int t3, int t4, int t5){
    int op=0;
    for(int i=0;i<2;i++) for(int j=0;j<2;j++) op+=dp[t1][t2][t3][t4][t5][i][j];

    if(j==0) add(tot[t1][t2][t3][t4][t5+1][1][1], dp[t1][t2][t3][t4][t5][0][1] + dp[t1][t2][t3][t4][t5][1][1])
    , add(tot[t1][t2][t3][t4][t5][1][0], dp[t1][t2][t3][t4][t5][1][0] + dp[t1][t2][t3][t4][t5][0][0]);
    if(j==1) add(tot[t1][t2][t3][t4][t5][1][1], op);
    if(j==2) add(tot[min(t1+1,p2)][t2][t3][t4][t5][1][1],op);
    if(j==3) add(tot[t1][min(t2+1, p3)][t3][t4][t5][1][1],op);
    if(j==4) add(tot[min(t1+2, p2)][t2][t3][t4][t5][1][1],op);
    if(j==5) add(tot[t1][t2][min(t3+1, p5)][t4][t5][1][1],op);
    if(j==6) add(tot[min(t1+1, p2)][min(t2+1, p3)][t3][t4][t5][1][1],op);
    if(j==7) add(tot[t1][t2][t3][min(t4+1, p7)][t5][1][1],op);
    if(j==8) add(tot[min(t1+3, p2)][t2][t3][t4][t5][1][1],op);
    if(j==9) add(tot[t1][min(t2+2, p3)][t3][t4][t5][1][1],op);
}
void add2(int j, int t1, int t2, int t3, int t4, int t5){
    int op1=0, op2=0;
    for(int i=0;i<2;i++) op1+=dp[t1][t2][t3][t4][t5][0][i], op2+=dp[t1][t2][t3][t4][t5][1][i];

    // if(t1==0&&t2==0&&t3==0&&t4==0&&t5==0) cerr<<dp[t1][t2][t3][t4][t5][1][1]<<"kk\n";
    
    if(j==0) add(tot[t1][t2][t3][t4][t5+1][1][1], dp[t1][t2][t3][t4][t5][1][1]), add(tot[t1][t2][t3][t4][t5][1][0], dp[t1][t2][t3][t4][t5][1][0]); 
    if(j==1) add(tot[t1][t2][t3][t4][t5][1][1], op2);
    if(j==2) add(tot[min(t1+1, p2)][t2][t3][t4][t5][1][1], op2);
    if(j==3) add(tot[t1][min(t2+1, p3)][t3][t4][t5][1][1], op2);
    if(j==4) add(tot[min(t1+2, p2)][t2][t3][t4][t5][1][1], op2);
    if(j==5) add(tot[t1][t2][min(t3+1, p5)][t4][t5][1][1], op2);
    if(j==6) add(tot[min(t1+1, p2)][min(t2+1, p3)][t3][t4][t5][1][1], op2);
    if(j==7) add(tot[t1][t2][t3][min(t4+1, p7)][t5][1][1], op2);
    if(j==8) add(tot[min(t1+3, p2)][t2][t3][t4][t5][1][1], op2);
    if(j==9) add(tot[t1][min(t2+2, p3)][t3][t4][t5][1][1], op2);

    if(j==0) add(tot[t1][t2][t3][t4][t5+1][0][1], dp[t1][t2][t3][t4][t5][0][1]), add(tot[t1][t2][t3][t4][t5][0][0], dp[t1][t2][t3][t4][t5][0][0]); 
    if(j==1) add(tot[t1][t2][t3][t4][t5][0][1], op1);
    if(j==2) add(tot[min(t1+1, p2)][t2][t3][t4][t5][0][1], op1);
    if(j==3) add(tot[t1][min(t2+1, p3)][t3][t4][t5][0][1], op1);
    if(j==4) add(tot[min(t1+2, p2)][t2][t3][t4][t5][0][1], op1);
    if(j==5) add(tot[t1][t2][min(t3+1, p5)][t4][t5][0][1], op1);
    if(j==6) add(tot[min(t1+1, p2)][min(t2+1, p3)][t3][t4][t5][0][1], op1);
    if(j==7) add(tot[t1][t2][t3][min(t4+1, p7)][t5][0][1], op1);
    if(j==8) add(tot[min(t1+3, p2)][t2][t3][t4][t5][0][1], op1);
    if(j==9) add(tot[t1][min(t2+2, p3)][t3][t4][t5][0][1], op1);
}
void add3(int j, int t1, int t2, int t3, int t4, int t5){
    int op2=0;
    for(int i=0;i<2;i++) op2+=dp[t1][t2][t3][t4][t5][1][i];
    // if(t1+t2+t3+t4+t5==0&&j==5)
    // cerr<<op2<<"op\n"<<min(t3+1, p5)<<"\n"<<t3<<" "<<p3<<"\n";
    
    if(j==0) add(tot[t1][t2][t3][t4][t5+1][1][1], dp[t1][t2][t3][t4][t5][1][1]), add(tot[t1][t2][t3][t4][t5][1][0], dp[t1][t2][t3][t4][t5][1][0]); 
    if(j==1) add(tot[t1][t2][t3][t4][t5][1][1], op2);
    if(j==2) add(tot[min(t1+1, p2)][t2][t3][t4][t5][1][1], op2);
    if(j==3) add(tot[t1][min(t2+1, p3)][t3][t4][t5][1][1], op2);
    if(j==4) add(tot[min(t1+2, p2)][t2][t3][t4][t5][1][1], op2);
    if(j==5) add(tot[t1][t2][min(t3+1, p5)][t4][t5][1][1], op2);
    if(j==6) add(tot[min(t1+1, p2)][min(t2+1, p3)][t3][t4][t5][1][1], op2);
    if(j==7) add(tot[t1][t2][t3][min(t4+1, p7)][t5][1][1], op2);
    if(j==8) add(tot[min(t1+3, p2)][t2][t3][t4][t5][1][1], op2);
    if(j==9) add(tot[t1][min(t2+2, p3)][t3][t4][t5][1][1], op2);
}


int k;string l, r;

int ff(int g, int h){
    if(h==0) return 1;
    if(h==1) return g;
    if(h%2) return g*ff(g,h-1)%k;
    else {
        int t=ff(g, h/2);
        return t*t%k;
    }
}

int calc(__int128 x,int k){
    string now;
    if(x==0) return 0; 
    while(x) now+=(char)('0'+x%10), x/=10;

    for(int i2=0;i2<=p2;i2++){
        for(int i3=0;i3<=p3;i3++){
            for(int i5=0;i5<=p5;i5++){
                for(int i7=0;i7<=p7;i7++){
                    for(int i0=0;i0<=20;i0++){
                        for(int u1=0;u1<2;u1++){
                            for(int u2=0;u2<2;u2++)
                                dp[i2][i3][i5][i7][i0][u1][u2]=0;
                        }
                    }
                }
            }
        }
    }

    dp[0][0][0][0][0][0][0]=1;
    for(int i=now.size()-1;i>=0;i--){
        for(int i2=0;i2<=p2;i2++){
            for(int i3=0;i3<=p3;i3++){
                for(int i5=0;i5<=p5;i5++){
                    for(int i7=0;i7<=p7;i7++){
                        for(int i0=0;i0<=20;i0++){
                            for(int j=0;j<=9;j++){
                                if(j<now[i]-'0'){
                                    add1(j, i2, i3, i5, i7, i0);
                                }
                                else if(j==now[i]-'0'){
                                    add2(j, i2, i3, i5, i7, i0);
                                }
                                else{
                                    add3(j, i2, i3, i5, i7, i0);
                                }
                            }
                        }
                    }
                }
            }
        }

        for(int i2=0;i2<=p2;i2++){
            for(int i3=0;i3<=p3;i3++){
                for(int i5=0;i5<=p5;i5++){
                    for(int i7=0;i7<=p7;i7++){
                        for(int i0=0;i0<=20;i0++){
                            for(int u1=0;u1<2;u1++){
                                for(int u2=0;u2<2;u2++)
                                    dp[i2][i3][i5][i7][i0][u1][u2]=tot[i2][i3][i5][i7][i0][u1][u2], tot[i2][i3][i5][i7][i0][u1][u2]=0;
                            }
                        }
                    }
                }
            }
        }
    }
        // cerr<<dp[0][0][0][0][0][1][0]<<"ff\n";

    int now1=0;
    for(int i2=0;i2<=p2;i2++){
        for(int i3=0;i3<=p3;i3++){
            for(int i5=0;i5<=p5;i5++){
                for(int i7=0;i7<=p7;i7++){
                    for(int i0=0;i0<=now.size();i0++){
                        for(int u1=0;u1<2;u1++){
                            if(i0) add(now1, dp[i2][i3][i5][i7][i0][u1][1]);
                            else if(i2>=g2&&i3>=g3&&i5>=g5&&i7>=g7) add(now1, dp[i2][i3][i5][i7][i0][u1][1]);
                            else break;
                            // cerr<<dp[i2][i3][i5][i7][i0][u1][1]<<" "<<i2<<" "<<i3<<" "<<i5<<" "<<i7<<" "<<i0<<"\n";
                        }
                    }
                }
            }
        }
    }
    // now1--;
    // cerr<<now1<<" "<<now<<"\n";
    return now1;
}

void solve(){
    cin>>k>>l>>r;
    __int128 t1=0, t2=0;
    for(auto g:l) t1*=10, t1+=g-'0';
    for(auto g:r) t2*=10, t2+=g-'0';
    
    int u1=t2, u2=t1;
    // cout<<u1<<" "<<u2<<"\n";
    while(u1%2==0) u1/=2, p2++;
    while(u1%3==0) u1/=3, p3++;
    while(u1%5==0) u1/=5, p5++;
    while(u1%7==0) u1/=7, p7++;
    int gg=k;
    while(gg%2==0) gg/=2, g2++;
    while(gg%3==0) gg/=3, g3++;
    while(gg%5==0) gg/=5, g5++;
    while(gg%7==0) gg/=7, g7++;
    p2=g2, p3=g3, p5=g5, p7=g7;
    // cerr<<p2<<" "<<p3<<" "<<p5<<" "<<p7<<"\n";
    int ans=calc(t2, k);
    // p2=0, p3=0, p5=0, p7=0;
    // while(u2%2==0) u2/=2, p2++;
    // while(u2%3==0) u2/=3, p3++;
    // while(u2%5==0) u2/=5, p5++;
    // while(u2%7==0) u2/=7, p7++;
    ans+=mol-calc(t1-1, k);
    ans+=mol;
    ans%=mol;

    cout<<ans;
}

signed main(){
    ios::sync_with_stdio(0);cin.tie(0);
    // int t;
    // cin>>t;
    // while(t--)
    solve();
    return 0;
}