#include<bits/stdc++.h> using namespace std; #define int long long #define pii pair<int,int> #define fr first #define sc second #define pb push_back #define lson (pos<<1) #define rson (pos<<1|1) #define popcnt __builtin_popcount int read(){int x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x*f;} const int MAXN=200010,MAXM=10010,N=15,Mod=1000000007; int n,k,ans,cnt,a[MAXN],b[MAXN],p[N],c[N],pi[MAXN][N],f[N][2]; void add(int &x,int y){x+=y%Mod;x%=Mod,x+=Mod,x%=Mod;} int check(){ int res=0,cnt=0;; for(int j=0;j<=9;j++)cnt+=p[j],c[j]=j>0?c[j-1]+p[j]:p[j]; int fl=0; for(int i=1;i<=n;i++){ if(!p[a[i]]){ add(res,(((i==1&&p[0])?-1:0)+c[a[i]])*pi[n-i][cnt]%Mod); fl=1; break; } add(res,((a[i]?c[a[i]-1]:0)+((i==1&&p[0])?-1:0))*pi[n-i][cnt]%Mod); } if(!fl)res++; add(res,f[cnt][p[0]]); return res; } int sol(){ int res=0; swap(a,b); add(res,check()); swap(a,b); add(res,Mod-check()); return res; } int G[MAXN],F[MAXN]; void dfs(int now,int sum,int s){ if(now==10){ F[s]=sol(); return; } p[now]=0; dfs(now+1,sum,s<<1); p[now]=1; dfs(now+1,sum+1,s<<1|1); } void slv(){ n=read(); for(int i=1;i<=n;i++){ a[i]=getchar();while(a[i]>'9'||a[i]<'0')a[i]=getchar();a[i]-='0'; } for(int i=1;i<=n;i++){ b[i]=getchar();while(b[i]>'9'||b[i]<'0')b[i]=getchar();b[i]-='0'; } int tmp=n; while(tmp&&!a[tmp])tmp--; a[tmp]--; for(int i=tmp+1;i<=n;i++)a[i]=9; k=read(); for(int j=0;j<=10;j++)pi[0][j]=1; for(int i=1;i<=n;i++)for(int j=0;j<=10;j++)pi[i][j]=pi[i-1][j]*j%Mod; for(int cnt=0;cnt<=10;cnt++)for(int p0=0;p0<=1;p0++) for(int i=1;i<=n;i++)add(f[cnt][p0],p0?(cnt-1)*(n-i>0?pi[n-i-1][cnt]:1):pi[n-i][cnt]); dfs(0,0,0); for(int i=0;i<1<<10;i++)if(popcnt(i)==k){ for(int j=i;j;j=(j-1)&i)add(ans,F[j]*(((k-popcnt(j))&1)?Mod-1:1)%Mod); } printf("%lld",ans); } signed main(){ slv(); return 0; }