#include<bits/stdc++.h> using namespace std; const int mod=1e9+7,N=2e5+10; int qp(int a,int b){ int x=1; while(b){ if(b&1) x=1ll*x*a%mod; b>>=1;a=1ll*a*a%mod; }return x; } int fac[N],inv[N]; int C(int u,int d){ return 1ll*fac[d]*inv[u]%mod*inv[d-u]%mod; }int vis[15];int a,n; int calc(string s){ s=' '+s;memset(vis,0,sizeof(vis)); long long ans=0; for(int i=1;i<=n;i++){ int di=s[i]-'0'; int bi=(i==1); for(int j=bi;j<di;j++){ int x=0; vis[j]++; for(int k=0;k<=9;k++){ if(vis[k]!=0) x++; }int nd=a-x; vis[j]--; if(nd<0) continue; long long now=0; for(int k=0;k<=nd;k++){ now+=1ll*C(k,nd)*qp(mod-1,k)%mod*qp(a-k,n-i)%mod*C(nd,10-x)%mod; //cout<<C(k,nd)<<endl; }//cout<<now<<' '<<i<<' '<<j<<endl; ans+=now%mod; //cout<<ans<<' '; }vis[di]++; }int x=0; for(int i=0;i<=9;i++) if(vis[i]!=0) x++; //cout<<x<<' '; if(x==a) ans++; //cout<<ans%mod<<endl; return ans%mod; }void slv(){ cin>>n; string l,r;cin>>l>>r;cin>>a; int ans=(calc(r)+mod-calc(l))%mod; memset(vis,0,sizeof(vis)); for(int i=0;i<n;i++) vis[l[i]-'0']++; int x=0;for(int i=0;i<=9;i++) if(vis[i]!=0) x++; if(x==a) ans=(ans+1)%mod; cout<<ans; } int main(){ int LM=55; fac[0]=1;for(int i=1;i<=LM;i++) fac[i]=1ll*fac[i-1]*i%mod; inv[LM]=qp(fac[LM],mod-2);for(int i=LM-1;i>=0;i--) inv[i]=1ll*inv[i+1]*(i+1)%mod; slv(); return 0; }