#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,b[15][N],c[20][20],jc[20],ny[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 fil(int p,int i,bool flg){//p spaces;i numbers if(p==0)return 1; if(flg){int ans=(b[i][p]-b[i-1][p]+M)%M;return ans;} else {int ans=((i-1)*b[i][p-1]-(i-2)*b[i][p-1])%M;ans=(ans+M)%M;return ans;} } int fll(int p,int x,int y){//p spaces;x of the colors must be used,while y of the colors can be used // cout<<"----------------"<<p<<" "<<x<<" "<<y<<endl; if(p==0)return 1; if(p<x)return 0; int ans=0; for(int i=x;i<=min(x+y,p);i++){ // cout<<i<<" "<<c[y][i-x]<<" "<<b[i][p]<<" "<<b[i-1][p]<<endl; ans+=c[y][i-x]*((b[i][p]-b[i-1][p]+M)%M)%M;ans%=M; } return ans; } int slv(int op){ int ANS=0; //!0 for(int j=I;j<=n-1;j++){ANS=(ANS+c[9][I]*fil(j,I,1))%M;} //0 for(int j=I;j<=n-1;j++){ANS=(ANS+c[9][I-1]*fil(j,I,0))%M;} // 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)continue; bool flag=0; for(int i=0;i<a[j+1][op];i++){ if(vis[i]){ // cout<<"!!"<<endl; flag=1; ANS+=c[10-cnt][I-cnt]*fll(n-j-1,I-cnt,cnt); } } 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)*c[10-cnt-1][I-cnt-1]*fll(n-j-1,I-cnt-1,cnt+1); else {ANS+=a[j+1][op]*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(){ for(int i=1;i<=9;i++){ b[i][0]=1; for(int j=1;j<=N-5;j++){ b[i][j]=b[i][j-1]*i%M; } } jc[0]=1;ny[0]=1; for(int i=1;i<=9;i++){jc[i]=jc[i-1]*i%M;ny[i]=ksm(jc[i],M-2);} for(int i=0;i<=9;i++){ for(int j=0;j<=i;j++){ c[i][j]=((jc[i]*ny[i-j])%M)*ny[j]%M; } } scanf("%lld",&n); 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'; cin>>I; // cout<<slv(1)<<" "<<slv(0)<<endl; int ans=slv(1)-slv(0);//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; }