#include<bits/stdc++.h> using namespace std; #define int long long #define mod 1000000007 #define L str[1] #define R str[2] int n,str[10][300100],a,fac[300100],invfac[300100],dp[300100][20]; int Begin; bool who_choose_str[10][20]; int qp(int a,int x){ int res=1; while(x){ if(x&1){ res=(res*a)%mod; }a=(a*a)%mod; x>>=1; }return res; }void init(); int C(int n,int m){//m>n; if(m<n||m<0||n<0) return 0; return (fac[m]*invfac[n]%mod)*invfac[m-n]%mod; }int A(int n,int m){//m>n; if(m<n||m<0||n<0) return 0; return (fac[m]*invfac[m-n]%mod); }int To_run(int id){ int ans=0; memset(who_choose_str,0,sizeof(who_choose_str)); int top=1;if(id==1) top=Begin; for(int i=1;i<=n;i++){ for(int j=0;j<=9;j++){ int sum=0; int front_thisone=0; for(int k=0;k<=9;k++){ if(who_choose_str[id][k]){ front_thisone++; } }if(who_choose_str[id][j]==0){ front_thisone++; } if(i==n&&j<=str[id][i]){ if(front_thisone==a){ ans++; }continue; } if(j<str[id][i]){ if(j!=0||i!=1){ int Igotchoose=C(a-front_thisone,10-front_thisone); for(int nowchoose_in_last=a-front_thisone; nowchoose_in_last<=a; nowchoose_in_last++){ int nums=C(nowchoose_in_last-a+front_thisone,front_thisone)*fac[nowchoose_in_last]%mod*Igotchoose%mod; sum=(sum+nums*dp[n-i][nowchoose_in_last])%mod; } } }if(j!=0&&i!=top){ front_thisone=1; int Igotchoose=C(a-front_thisone,10-front_thisone); for(int nowchoose_in_last=a-front_thisone;nowchoose_in_last<=a;nowchoose_in_last++){ int nums=C(nowchoose_in_last-a+front_thisone,front_thisone)*fac[nowchoose_in_last]%mod*Igotchoose%mod; sum=(sum+nums*dp[n-i][nowchoose_in_last])%mod; } }cout<<i<<' '<<j<<' '<<sum<<'\n'; ans=(ans+sum)%mod; }who_choose_str[id][str[id][i]]=1; }return ans; }signed main(){ //freopen("math.in","r",stdin); //freopen("math.out","w",stdout); cin>>n; init(); if(a==1){ int limitl=L[1],limitr=R[1]; for(int i=1;i<=n;i++){ if(L[i]<L[1]){ limitl--; break; }if(L[i]>L[1]){ break; } }for(int i=1;i<=n;i++){ if(R[i]<R[1]){ limitr--; break; }if(R[i]>R[1]){ break; } } cout<<limitr-limitl<<'\n'; return 0; }//cout<<To_run(1)<<' '<<To_run(2)<<'\n'; //cout<<To_run(1)<<' '<<To_run(2)<<'\n'; cout<<(To_run(2)-To_run(1)+mod)%mod; } // void init(){ fac[0]=1;invfac[0]=1; for(int i=1;i<=300000;i++){ fac[i]=(fac[i-1]*i)%mod; invfac[i]=qp(fac[i],mod-2)%mod; }for(int i=1;i<=n;i++){ char ch=getchar(); while(ch<'0'||ch>'9') ch=getchar(); L[i]=ch-'0'; //cout<<L[i]; }//cout<<'\n'; for(int i=1;i<=n;i++){ char ch=getchar(); while(ch<'0'||ch>'9') ch=getchar(); R[i]=ch-'0'; //cout<<R[i]; }//cout<<'\n'; dp[0][0]=1; for(int i=1;i<=n;i++){ for(int j=1;j<=min((long long)10,i);j++){ dp[i][j]=(dp[i-1][j-1]+dp[i-1][j]*j)%mod; //cout<<dp[i][j]<<' '; }//cout<<'\n'; }cin>>a; int nowpos=n; while(1){ if(L[nowpos]!=0){ break; }nowpos--; }L[nowpos]-=1; for(int i=nowpos+1;i<=n;i++){ L[i]=9; }bool flag=0; for(int i=1;i<=n;i++){ if(L[i]!=0&&flag==0){flag=1;Begin=i;} } } /*//cout<<Begin<<'\n'; for(int i=1;i<=n;i++){ //if(L[i]!=0) flag=1; for(int j=0;j<=9;j++){ if(j==0){ if(i!=1){ int front_thisone=0; for(int k=0;k<=9;k++){ if(who_choose_R[k]){ front_thisone++; } }if(who_choose_R[j]==0){ front_thisone++; } if(i==n&&j<R[i]){ if(front_thisone==a){ ansr++; }//continue; } int empty=front_thisone+n-i-1,sum=0; int Igotchoose=C(a-front_thisone,10-front_thisone); for(int nowchoose_in_last=a-front_thisone;nowchoose_in_last<=a&&i!=n;nowchoose_in_last++){ //cout<<front_thisone<<'\n'; int nums=C(nowchoose_in_last-a+front_thisone,front_thisone)*fac[nowchoose_in_last]%mod*Igotchoose%mod; //cout<<i<<' '<<j<<' '<<nowchoose_in_last<<' '<<nums*dp[n-i][nowchoose_in_last]<<'\n'; sum=(sum+nums*dp[n-i][nowchoose_in_last])%mod; //ansl=(ansl+nums*dp[n-i][nowchoose_in_last])%mod; }//cout<<i<<' '<<j<<' '<<sum<<'\n'; ansr=(ansr+sum)%mod; } }else{ int front_thisone=0; for(int k=0;k<=9;k++){ if(who_choose_R[k]){ front_thisone++; } }if(who_choose_R[j]==0){ front_thisone++; } if(i==n&&j<R[i]){ if(front_thisone==a){ ansr++; } } int empty=front_thisone+n-i-1,sum=0; int Igotchoose=C(a-front_thisone,10-front_thisone); if(j<R[i]){ for(int nowchoose_in_last=a-front_thisone;nowchoose_in_last<=a&&i!=n;nowchoose_in_last++){ //cout<<front_thisone<<'\n'; int nums=C(nowchoose_in_last-a+front_thisone,front_thisone)*fac[nowchoose_in_last]%mod*Igotchoose%mod; //cout<<i<<' '<<j<<' '<<nowchoose_in_last<<' '<<nums*dp[n-i][nowchoose_in_last]<<'\n'; sum=(sum+nums*dp[n-i][nowchoose_in_last])%mod; //ansl=(ansl+nums*dp[n-i][nowchoose_in_last])%mod; }//cout<<i<<' '<<j<<' '<<sum<<'\n'; } ansr=(ansr+sum)%mod; if(i!=1){ sum=0; front_thisone=1; int Igotchoose=C(a-front_thisone,10-front_thisone); for(int nowchoose_in_last=a-front_thisone;nowchoose_in_last<=a;nowchoose_in_last++){ //cout<<front_thisone<<'\n'; int nums=C(nowchoose_in_last-a+front_thisone,front_thisone)*fac[nowchoose_in_last]%mod*Igotchoose%mod; //cout<<i<<' '<<j<<' '<<nowchoose_in_last<<' '<<nums*dp[n-i][nowchoose_in_last]<<'\n'; sum=(sum+nums*dp[n-i][nowchoose_in_last])%mod; //ansl=(ansl+nums*dp[n-i][nowchoose_in_last])%mod; }//cout<<i<<' '<<j<<' '<<sum<<'\n'; ansr=(ansr+sum)%mod; } } }who_choose_R[R[i]]=1; } int lcnt=0,rcnt=0; for(int i=0;i<=9;i++){ lcnt+=who_choose_L[i]; rcnt+=who_choose_R[i]; }if(lcnt==a) ansl++; if(rcnt==a) ansr++; //cout<<lcnt<<'\n'; //cout<<ansl<<' '<<ansr<<'\n'; cout<<(ansr-ansl+mod)%mod<<'\n'; */