#include<bits/stdc++.h> using namespace std; #define int long long const int N=2e5+10,M=1e9+7; int n,a[N][2],I,c[20][20],jc[20],ny[20],g[N][20],cny[20][20]; bool vis[20]; string s; int ksm(int a,int b){ int ans=1,base=a; while(b>0){ if(b&1)ans=ans*base%M; base=base*base%M;b>>=1; } return ans; } int fll(int p,int x,int y){//p个空格，有x种颜色必须使用，有y种颜色可选用的填色方案数 int ans=0; if(p<x)return 0; if(p==0)return 1; for(int i=x;i<=min(x+y,p);i++){ // cout<<i<<" "<<c[y][i-x]<<" "<<b[i][p]<<" "<<b[i-1][p]<<endl; if(i==0)continue; ans=(ans+g[p][i]*c[y][i-x])%M; } return ans; } int slv(int op){ // cout<<"--------------------"<<endl; int ANS=0; for(int i=I;i<=n-1;i++){ // cout<<I<<endl; // cout<<c[10][I]<<" "<<g[i][I]<<" "<<c[9][I-1]<<" "<<g[i-1][I]<<" "<<c[9][I-1]<<" "<<g[i-1][I-1]<<endl; ANS+=(c[10][I]*g[i][I]%M-c[9][I-1]*g[i-1][I]%M-c[9][I-1]*g[i-1][I-1]%M+2*M)%M;ANS%=M; } // cout<<ANS<<endl; // for(int i=0;i<=10;i++)vis[i]=0; int cnt=0; for(int j=0;j<=n&&cnt<=I;j++){ // cout<<"!"<<j<<endl; if(j>=1){ if(!vis[a[j][op]]){vis[a[j][op]]=1;cnt++;} } if(cnt>I)break; if(j==n){if(cnt==I)ANS++;continue;} if((a[j+1][op]<=1&&j==0)||a[j+1][op]==0)continue; bool flag=0;int ct=0; for(int i=0;i<a[j+1][op];i++){ if(vis[i]){ // cout<<"!!"<<endl; flag=1; // cout<<c[10-cnt][I-cnt]<<" "<<fll(n-j-1,I-cnt,cnt)<<endl; ANS+=c[10-cnt][I-cnt]*fll(n-j-1,I-cnt,cnt);ANS%=M; ct++; // cout<<i<<" "<<ANS<<endl; } } if(cnt==I)continue; // cout<<a[j+1][op]-1<<" "<<10-cnt-1<<" "<<I-cnt-1<<" "<<c[10-cnt-1][I-cnt-1]<<" "<<fll(n-j-1,I-cnt-1,cnt+1)<<endl; if(j==0){ANS+=(a[j+1][op]-1-ct)*c[10-cnt-1][I-cnt-1]*fll(n-j-1,I-cnt-1,cnt+1);ANS%=M;} else {ANS+=(a[j+1][op]-ct)*c[10-cnt-1][I-cnt-1]*fll(n-j-1,I-cnt-1,cnt+1);ANS%=M;} // cout<<ANS<<endl; } return ANS; } signed main(){ jc[0]=1;ny[0]=1; for(int i=1;i<=10;i++){jc[i]=jc[i-1]*i%M;ny[i]=ksm(jc[i],M-2);} for(int i=0;i<=10;i++){ for(int j=0;j<=i;j++){ c[i][j]=((jc[i]*ny[i-j])%M)*ny[j]%M; cny[i][j]=ksm(c[i][j],M-2); // cout<<cny[i][j]<<" "; }//cout<<endl; } g[0][0]=1; for(int i=1;i<=N-5;i++){ for(int j=1;j<=10;j++){ g[i][j]=(g[i-1][j]*j%M+g[i-1][j-1]*j)%M; // cout<<g[i][j]<<" "; }//cout<<endl; } scanf("%lld",&n); // for(int i=1;i<=n;i++){ // for(int j=1;j<=10;j++)cout<<g[i][j]<<" "; // cout<<endl; // } cin>>s; for(int i=0;i<s.length();i++)a[i+1][0]=s[i]-'0'; cin>>s; for(int i=0;i<s.length();i++)a[i+1][1]=s[i]-'0'; scanf("%lld",&I); // cout<<slv(1)<<" "<<slv(0)<<endl; int ans=(slv(1)-slv(0)+M)%M;//cout<<ans<<endl; for(int i=0;i<=9;i++)vis[i]=0; for(int i=1;i<=n;i++){vis[a[i][0]]=1;} int cnt=0; for(int i=0;i<=9;i++){if(vis[i])cnt++;} // cout<<cnt<<endl; if(cnt==I)ans++; printf("%lld\n",ans); return 0; }