#include<bits/stdc++.h> #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define pi pair<int,int> #define p1 first #define p2 second #define m_p make_pair #define p_b push_back using namespace std; typedef long long ll; const int maxn=2e5+10,mod=1e9+7; inline ll read(){ ll x=0;short t=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; } string L,R; int n,A; int jc[maxn],jc_inv[maxn]; int dp[11][maxn][11]; int f(string &s){ set<int>st; for(char ch:s)if(ch!=' ')st.insert(ch); return st.size(); } int C(int n,int m){if(n<0||m<0||m<n)return 0;return jc[m]*1ll*jc_inv[m-n]%mod*1ll*jc_inv[n]%mod;} int qp(int a,int b){ int res=1; while(b){ if(b&1)res=res*1ll*a%mod; a=a*1ll*a%mod;b>>=1; }return res; } int get_ans(string &s){ int res=0; set<int>st; up(i,1,n){ if((int)st.size()<=A){ up(w,0,s[i]-'0'-1){ int sz=(int)st.size()+(!st.count(w)); int rem=A-sz; if(rem>=0)(res+=C(rem,10-sz)*1ll*dp[sz][n-i][rem]%mod)%=mod; } }st.insert(s[i]-'0'); }if(f(s)==A)res++; return res; } void slv(){ cin>>n>>L>>R>>A;L=" "+L,R=" "+R; jc[0]=jc_inv[0]=1;up(i,1,max(n,15))jc[i]=jc[i-1]*1ll*i%mod,jc_inv[i]=qp(jc[i],mod-2); up(i,0,10){ dp[i][0][0]=1; up(j,1,n){ up(k,0,10){ dp[i][j][k]=dp[i][j-1][k]*1ll*(k+i)%mod; if(k)(dp[i][j][k]+=dp[i][j-1][k-1])%=mod; } } } up(i,0,10)up(j,0,n)up(k,0,10)dp[i][j][k]=dp[i][j][k]*1ll*jc[k]%mod; int res=get_ans(R); res=(res+mod-get_ans(L))%mod; if(f(L)==A)(res+=1)%=mod; printf("%d\n",res); } int main(){ //freopen("math.in","r",stdin); //freopen("math.out","w",stdout); slv(); fclose(stdin); fclose(stdout); return 0; }