#include<bits/stdc++.h> #define ll long long #define lson pos<<1 #define rson pos<<1|1 using namespace std; const int maxn=3e5+10; const ll mod=1e9+7; const ll inf=1e10; ll n,m,k,t,ans=0; ll a[maxn],vis[20][5],C[20][20],A[20][20],f[maxn][10]; char c[maxn],s[maxn]; int main(){ // freopen("test.in","r",stdin); // freopen("math.out","w",stdout); scanf("%lld",&n); scanf("%s",c+1); scanf("%s",s+1); scanf("%lld",&m); memset(f,0,sizeof(f)); f[0][0]=1; for(int i=1;i<=n;i++){ for(ll j=1;j<=min(10,i);j++){ f[i][j]=(f[i-1][j-1]+f[i-1][j]*j%mod)%mod; } } C[0][0]=1ll; A[0][0]=1ll; for(ll i=1;i<=10;i++){ C[i][0]=1ll; A[i][0]=1ll; for(ll j=1;j<=i;j++){ C[i][j]=C[i-1][j]+C[i-1][j-1]; A[i][j]=A[i][j-1]*(i-j+1ll)%mod; } } memset(vis,0,sizeof(vis)); int cnt=0,cnt1=0; bool fg=0; for(int i=1;i<=n;i++){ if(i==1){ ans=(s[i]-c[i])*C[9][m-1]%mod*((f[n-1][m]*A[m][m])%mod+f[n-1][m-1]*A[m-1][m-1]%mod)%mod; // cout<<ans<<" "<<s[i]-c[i]<<" "<<C[9][m-1]<<" "<<f[n-1][m]*A[m][m]<<" "<<f[n-1][m-1]*A[m-1][m-1]<<" "<<endl; } else{ for(int j=0;j<s[i]-'0'&&cnt<=m;j++){ int tmp=cnt+(!vis[j][0]); // cout<<vis[j][0]<<" "<<cnt<<endl; if(tmp>m) continue; for(int k=0;k<=tmp;k++){ // cout<<C[10-tmp][m-tmp]<<" "<<f[n-i][m-k]<<" "<<k<<" "<<j<<endl; ans=(ans+C[10-tmp][m-tmp]*f[n-i][m-k]%mod*A[m-k][m-tmp]%mod*A[tmp][tmp-k]%mod)%mod; } } for(int j=0;j<c[i]-'0'&&cnt1<=m;j++){ int tmp=cnt1+(!vis[j][1]); if(tmp>m) continue; for(int k=0;k<=tmp;k++){ // cout<<i<<" "<<j<<" "<<k<<" "<<ans<<" "<<C[10-tmp][m-tmp]<<" "<<f[n-i][m-k]<<" "<<A[m-k][m-tmp]<<" "<<A[tmp][tmp-k]<<endl; ans=(ans-C[10-tmp][m-tmp]*f[n-i][m-k]%mod*A[m-k][m-tmp]%mod*A[tmp][tmp-k]%mod+mod)%mod; } } } if(!vis[s[i]-'0'][0]) vis[s[i]-'0'][0]=1,cnt++; if(!vis[c[i]-'0'][1]) vis[c[i]-'0'][1]=1,cnt1++; // cout<<i<<" "<<cnt<<" "<<ans<<endl; } // cout<<cnt<<" "<<m<<endl; if(cnt==m) ans++; printf("%lld",ans); fclose(stdin); fclose(stdout); return 0; }