#include<iostream> #include<string> #include<cstring> #include<ctime> #include<set> #define timeMS (clock()*1000/CLOCKS_PER_SEC) using namespace std; const int N=200100,B=10,P=1000000007; #define int long long int n,A,pop[1<<B],p[B+1][N],binom[B][B]; string L,R; inline int count(const string&lim,int sta){ int res=0; for(int i=0;i<n;i++){ int x=lim[i]-'0'; int cnt=pop[sta&((1<<x)-1)]; res=(res+cnt*p[pop[sta]][n-i-1]); if(!(sta&(1<<x)))break; else if(i==n-1)res++; } return res; } inline int count(const string&lim){ int res=0; for(int i=1;i<(1<<B);i++)if(pop[i]<=A){ if(pop[i]%2==A%2)res=(res+binom[B-pop[i]][A-pop[i]]*count(lim,i))%P; else res=(res-binom[B-pop[i]][A-pop[i]]*count(lim,i))%P; } return res; } void init(){ for(int i=0;i<=B;i++){ p[i][0]=1; for(int j=1;j<N;j++)p[i][j]=p[i][j-1]*i%P; } for(int i=0;i<B;i++){ binom[i][0]=1; for(int j=1;j<=i;j++)binom[i][j]=(binom[i-1][j]+binom[i-1][j-1])%P; } cin>>n>>L>>R>>A; for(int i=1;i<(1<<B);i++)pop[i]=pop[i>>1]+(i&1); } signed main(){ // freopen("math.in","r",stdin); // freopen("math.out","w",stdout); init(); int ans=count(R)-count(L); set<char>s; for(char c:L)s.insert(c); if(s.size()==A)ans++; cout<<(ans+P)%P; // cerr<<timeMS; return 0; }